* Re: Slow compile - find_symtree_for_symbol()
[not found] ` <CAKwh3qheDAK7W+7NRPyf9cPWN0nMBJSvTHYKtb5AVPYu6vN=yQ@mail.gmail.com>
@ 2017-04-17 18:32 ` Paul Richard Thomas
2017-04-17 19:26 ` Andrew Benson
0 siblings, 1 reply; 2+ messages in thread
From: Paul Richard Thomas @ 2017-04-17 18:32 UTC (permalink / raw)
To: Janus Weil; +Cc: Andrew Benson, fortran, gcc-patches
Committed as revision 246952.
Thanks for finding this deadwood.
Cheers
Paul
On 16 April 2017 at 20:18, 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
--
"If you can't explain it simply, you don't understand it well enough"
- Albert Einstein
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: Slow compile - find_symtree_for_symbol()
2017-04-17 18:32 ` Slow compile - find_symtree_for_symbol() Paul Richard Thomas
@ 2017-04-17 19:26 ` Andrew Benson
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Benson @ 2017-04-17 19:26 UTC (permalink / raw)
To: Paul Richard Thomas; +Cc: Janus Weil, fortran, gcc-patches
No problem - I'm making use of the faster compile times already!
Cheers,
Andrew
On Monday, April 17, 2017 7:23:29 PM PDT Paul Richard Thomas wrote:
> Committed as revision 246952.
>
> Thanks for finding this deadwood.
>
> Cheers
>
> Paul
>
> On 16 April 2017 at 20:18, 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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2017-04-17 18:32 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <4977376.LEhxjoMrU2@andrew-precision-3520>
[not found] ` <CAKwh3qgS+K0=rRO5c3UtM4fL7tpfd7gPytu5QH6_mFFDpMg0YA@mail.gmail.com>
[not found] ` <1901992.9vEn70CnpC@andrew-precision-3520>
[not found] ` <CAGkQGi+NpBJ1WV-AAAXqFwcXptWJE+NN9A_a7ExyHj76-5OcmA@mail.gmail.com>
[not found] ` <CAKwh3qgCUxn3TBHDNRFWMvqt9n7aQMtLm_OmBTr=fytMb93ucw@mail.gmail.com>
[not found] ` <CAGkQGiJL5AR=0Ut42HMWQ+5-_yUUrv=3GK3iUzo=NV40MFU4FQ@mail.gmail.com>
[not found] ` <CAKwh3qheDAK7W+7NRPyf9cPWN0nMBJSvTHYKtb5AVPYu6vN=yQ@mail.gmail.com>
2017-04-17 18:32 ` Slow compile - find_symtree_for_symbol() Paul Richard Thomas
2017-04-17 19:26 ` Andrew Benson
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).