Slow compile - find_symtree_for_symbol()

[Andrew Benson]

Hi Paul,

Thanks - that makes sense. I've opened a PR for this:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80440

I can look into what it would take to add a linked list of symtrees for 
symbols - I have some time in the next few weeks that I could spend on this.

Cheers,
Andrew

On Saturday, April 15, 2017 10:43:46 PM PDT Paul Richard Thomas wrote:
> 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


-- 

* Andrew Benson: http://users.obs.carnegiescience.edu/abenson/contact.html

* Galacticus: http://sites.google.com/site/galacticusmodel