Slow compile - find_symtree_for_symbol()
Andrew Benson
abenson@carnegiescience.edu
Mon Apr 17 15:38:00 GMT 2017
Hi Janus,
Yes - it's the worst case (in terms of compile time to size of code) in a
large project. It's one of the "higher-level" components of that project which
make use of many module, many of which are large.
Cheers,
Andrew
On Monday, April 17, 2017 11:18:06 AM PDT Janus Weil wrote:
> Hi Andrew,
>
> > 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.
> nice, thanks for the confirmation.
>
> I just tried the patch on a code base which makes moderate use of
> modules (and also contains some F77 parts without modules), where it
> had little influence on the compile time of ~1:30min.
>
> I assume your 700-loc test case is rather extreme, in that it either
> uses lots of modules, or particularly large ones?
>
> Cheers,
> Janus
>
> > On Sun, Apr 16, 2017, 12:18 PM Janus Weil <janus@gcc.gnu.org> 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