Slow compile - find_symtree_for_symbol()

[Andrew Benson]

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