Slow compile - find_symtree_for_symbol()

Janus Weil janus@gcc.gnu.org
Mon Apr 17 09:18:00 GMT 2017 

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

More information about the Fortran mailing list