Slow compile - find_symtree_for_symbol()

[Janus Weil]

Hi Andrew,

> 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.

whoa, 3 minutes definitely sounds pretty bad for 700 loc :(


> 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).

Huh, naively I would say it should be possible to use an ordered tree
here as well, like it is done for the symtree-related functions in
symbol.c (e.g. gfc_find_symtree). There is certainly some reason why
this is not done, but I have too little knowledge of the module.c code
to be much of a help here.


> 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.

"svn blame" tells me that find_symtree_for_symbol was introduced by
Paul in this commit in 2007:

https://gcc.gnu.org/viewcvs/gcc?view=revision&revision=121824

see also:

https://gcc.gnu.org/ml/gcc-patches/2007-02/msg00807.html

So I guess Paul is probably the best person to answer your question ...

Cheers,
Janus