Slow compile - find_symtree_for_symbol()

[Paul Richard Thomas]

Dear Andrew,

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.

It has repeatedly crossed my mind that symbols could do with a linked
list of symtrees that point to them.

Cheers

Paul


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