Slow compile - find_symtree_for_symbol()

[Janus Weil]

Hi,

>> > 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.
>
> This does seem to work. If I ignore my ignorance of why the ordered tree isn't
> used here and go ahead and search it using the symbol name (ignoring case
> which seems to differ between the symbol name and the name of the symtree
> node) then I certainly get a substantial speed-up (the file I mentioned now
> compiles in 40s), and nothing seems to break. I ran the gfortan test suite
> which shows two FAILs:
>
> gcc/testsuite/gfortran/gfortran.sum:FAIL: gfortran.dg/graphite/pr68279.f90   -
> O  (internal compiler error)
> gcc/testsuite/gfortran/gfortran.sum:FAIL: gfortran.dg/graphite/pr68279.f90   -
> O  (test for excess errors)
>
> but those show up when I run the test suite without any change to module.c
> anyway.

interesting. That sounds a bit like it might just have been an
oversight to not take advantage of the ordering in
find_symtree_for_symbol (or maybe there was a reason for it which is
obsolete by now). Hopefully Paul will be able to remember why it was
implemented like this a decade ago :)

Could you maybe post the patch you used? It might also be useful to
open a PR for this (if there isn't one already) ...

Cheers,
Janus