Slow compile - find_symtree_for_symbol()

[Janus Weil]

Hi Paul,

> The reason why the name wass not used is because of the rename
> facility in modules. In this case, the symtree name and the symbol
> names are different.

thanks for the feedback!

Do you understand why Andrew's patch (see
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80440#c0) doesn't show
any testsuite failures then? Not even the test case from the original
r121824 fails (char_array_constructor_2.f90). Don't we have sufficient
coverage of use-renaming?

Looking at the one occurrence of find_symtree_for_symbol in read_module:

      /* If possible recycle the symtree that references the symbol.
     If a symtree is not found and the module does not import one,
     a unique-name symtree is found by read_cleanup.  */
      st = find_symtree_for_symbol (gfc_current_ns->sym_root, sym);
      if (st != NULL)
    {
      info->u.rsym.symtree = st;
      info->u.rsym.referenced = 1;
    }

The comment there sounds a bit like this is just an (optional)
'optimization'? If it actually slows down things in reality, could one
just get away without this piece of code altogether?

Cheers,
Janus



> On 15 April 2017 at 20:56, Andrew Benson <abenson@carnegiescience.edu> wrote:
>> Hi Janus,
>>
>> On Saturday, April 15, 2017 1:48:36 PM PDT Janus Weil wrote:
>>> 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 :(
>>
>> Yeah, definitely slow! For compiling a large project with many modules it's
>> making development painful.
>>
>>> > 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.
>>
>>> > 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 ...
>>
>> If Paul can offer any insight into this that would be great.
>>
>> Cheers,
>> Andrew
>>
>> --
>>
>> * Andrew Benson: http://users.obs.carnegiescience.edu/abenson/contact.html
>>
>> * Galacticus: http://sites.google.com/site/galacticusmodel
>>
>
>
>
> --
> "If you can't explain it simply, you don't understand it well enough"
> - Albert Einstein