Slow compile - find_symtree_for_symbol()
Paul Richard Thomas
paul.richard.thomas@gmail.com
Sun Apr 16 18:27:00 GMT 2017
Hi Janus,
I was wondering the self-same question myself :-) Certainly the logic
behind find_symtree_for_symbol was as I describe. If it has been
subverted by some other mystery of module.c, I don't know. The comment
above the call to the function is, perhaps, the clue:
/* 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. */
There have been times, whose duration was measured in milliseconds,
when I understood module.c. This was obviously one of those times!
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?
Paul
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
-------------- next part --------------
Index: gcc/fortran/module.c
===================================================================
*** gcc/fortran/module.c (revision 246928)
--- gcc/fortran/module.c (working copy)
*************** mio_symbol (gfc_symbol *sym)
*** 4292,4322 ****
/************************* Top level subroutines *************************/
- /* Given a root symtree node and a symbol, try to find a symtree that
- references the symbol that is not a unique name. */
-
- static gfc_symtree *
- find_symtree_for_symbol (gfc_symtree *st, gfc_symbol *sym)
- {
- gfc_symtree *s = NULL;
-
- if (st == NULL)
- return s;
-
- s = find_symtree_for_symbol (st->right, sym);
- if (s != NULL)
- return s;
- s = find_symtree_for_symbol (st->left, sym);
- if (s != NULL)
- return s;
-
- if (st->n.sym == sym && !check_unique_name (st->name))
- return st;
-
- return s;
- }
-
-
/* A recursive function to look for a specific symbol by name and by
module. Whilst several symtrees might point to one symbol, its
is sufficient for the purposes here than one exist. Note that
--- 4292,4297 ----
*************** read_module (void)
*** 5119,5134 ****
info->u.rsym.referenced = 1;
continue;
}
-
- /* 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;
- }
}
mio_rparen ();
--- 5094,5099 ----
More information about the Fortran
mailing list