Slow compile - find_symtree_for_symbol()
Andrew Benson
abenson@carnegiescience.edu
Sun Apr 16 23:57:00 GMT 2017
Hi Janus,
Can confirm. Removing the function entirely results in a compile time of 39s
which is very close to what I got using the tree structure to search.
-Andrew
On Sunday, April 16, 2017 9:18:03 PM PDT Janus Weil wrote:
> Hi Paul,
>
> > Prompted by this thread, I have just tried eliminating the call and
> > the function altogether. No problem, the regtesting went through
> > without a problem. Evidently the need for this function has gone away
> > with some subsequent patch(es).
> >
> > OK for trunk?
>
> yes, ok from my side. Removing unneeded code is certainly a good idea,
> even more so if it is responsible for a performance problem.
>
> I assume this should generate a similar (or even larger?) speedup for
> Andrew's case as his earlier patch. Andrew, can you confirm this?
>
> Cheers,
> Janus
>
> > 2017-04-16 Paul Thomas <pault@gcc.gnu.org>
> >
> > PR fortran/80440
> > * module.c (find_symtree_for_symbol): Delete.
> > (read_module): Remove the call to the above.
> >
> > On 16 April 2017 at 14:27, Janus Weil <janus@gcc.gnu.org> wrote:
> >> 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
> >
> > --
> > "If you can't explain it simply, you don't understand it well enough"
> > - Albert Einstein
--
* Andrew Benson: http://users.obs.carnegiescience.edu/abenson/contact.html
* Galacticus: http://sites.google.com/site/galacticusmodel
More information about the Fortran
mailing list