Slow compile - find_symtree_for_symbol()

[Andrew Benson]

Compile times for code that makes extensive USEs of modules seems to be very 
slow in some cases. I've been doing some investigation of the cause of this 
with the hope that I can maybe figure out some way to speed things up.

For example, I have a smallish file - 700 lines of code, which takes around 3 
minutes to compile with a recent build of gfortran. Profiling f951 with 
valgrind I find that 63% of that time is spent in find_symtree_for_symbol(), 
which (if I understand correctly) is searching for a node in the symtree that 
already references some symbol being imported from a module. 

find_symtree_for_symbol() gets called directly 245,658 times in compiling this 
source file (and calls itself recursively almost 19 billion times!).

find_symtree_for_symbol() is just stepping through a binary branching tree 
looking for a reference to a given symbol, but (again, if I understood 
correctly), it can't use the usual bbt search approach because the tree is not 
ordered by the symbol name, so the search is O(n) rather than O(log n). 

So, before I dive in and see if I can sufficiently understand how this works to 
figure out if there's an obvious way to make the search more efficient, I wanted 
to ask if anyone else has looked at this, or if there's an immediately obvious 
way to improve the performance of this search.

Thanks,
Andrew

-- 

* Andrew Benson: http://users.obs.carnegiescience.edu/abenson/contact.html

* Galacticus: http://sites.google.com/site/galacticusmodel