[Bug fortran/98426] New: find_symbol in module.c traverses O(N) part of a search tree

[Bug fortran/98426] New: find_symbol in module.c traverses O(N) part of a search tree

[mscfd at gmx dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

            Bug ID: 98426
           Summary: find_symbol in module.c traverses O(N) part of a
                    search tree
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: fortran
          Assignee: unassigned at gcc dot gnu.org
          Reporter: mscfd at gmx dot net
  Target Milestone: ---

Created attachment 49837
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49837&action=edit
patch

Compilation times of top level modules in a large project I am working on are 
abysmal (up to 30 seconds for modules even with little code in it). Those
modules are using other modules whose mod files are up to 500kB. As far as I
can  see the mod files contain all [including private] symbols from any module
in their use-chain.

I used -pg compiler option to compile gcc itself and ran f951 and gprof with
some modules. gprof showed that about 80% or more of the compilation time is
spent in routine "find_symbol" in module.c.

>From the documentation I can see that argument "gfc_symtree *st" of
"find_symbol" should be a balanced binary search tree, ordered by
gfc_symtree->name. It looks like the tree can have different nodes with the
same name, so traversing the tree to check all nodes of the given name might
require to descend both the left and right subtree.

However, "find_symbol" traverses far more nodes than necessary. (Assuming that
all symbol names are unique, it traverses about half of the tree on average,
making the lookup operation O(N) instead of O(log N).)

The attached patch descends only if it can expect a match in the subtree (and
no match was found so far). This brings down the execution time of find_symbol
to almost nothing, speeding up the compilation time by a factor of about 5-10
for my top level modules (makes a difference if a module compiles in 3 instead
of 30 seconds)!


The patch regtests, and also compiles the large project with its big symbol
trees flawlessly and much faster.

Are there any testcases which check that find_symbol works as expected? If I
change find_symbol to always return NULL, then
make -k check-fortran gives
# of expected passes            55911
# of unexpected failures        1
# of expected failures          232
# of unsupported tests          81
with just one unexpected failure I could not locate.

In particular if I compile check use_only_1.f90 by hand (added by PR33541,
which added find_symbol), everything seems to work without a proper return
value from find_symbol.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[mscfd at gmx dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #1 from martin <mscfd at gmx dot net> ---
Created attachment 49846
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49846&action=edit
corrected patch

Comparison with c was wrong.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[mscfd at gmx dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #2 from martin <mscfd at gmx dot net> ---
I further tried to find out what the call to find_symbol (this is the call
which consumed the compilation time) is achieving in read_modules(). Even with
the accidentially wrong patch everything just seems to work (and I have lots of
generic interfaces and submodules etc., for which there are checks in
read_modules following the call to find_symbol).

With some printf's I at least checked the the corrected patch definitely finds
the symbols it is looking for. But I cannot come up with some testcase showing
that find_symbol returns the expected result in read_modules().

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[mscfd at gmx dot net]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #3 from martin <mscfd at gmx dot net> ---
Sorry for the noise, but as this gives big reductions in compilation time it is
quite important to me (and probably other big module based projects).

I just realised that I mixed up gfc_symtree->name and gfc_symtree->n.sym->name.
The reason why find_symbol traverses the whole tree in the worst case is that
it is ordered by gfc_symtree->name but it looks for gfc_symtree->n.sym->name.

So far I got the impression that either gfc_symtree->name is a unique name
("@xxx") or equal to gfc_symtree->n.sym->name (if n.sym!=NULL). In this case,
the following patch should do the trick and traverse only log(N) of the tree:

diff --git a/gcc/fortran/module.c b/gcc/fortran/module.c
index 4c6ff22d5c1..8dc59e25d46 100644
--- a/gcc/fortran/module.c
+++ b/gcc/fortran/module.c
@@ -4659,10 +4659,20 @@ find_symbol (gfc_symtree *st, const char *name,
        return st;
     }

+  c = strcmp (name, st->name);
+  if (c < 0)
+    retval = find_symbol (st->left, name, module, generic);
+  else if (c > 0)
+    retval = find_symbol (st->right, name, module, generic);
+  else
+    retval = NULL;
+
+/* original traverse
   retval = find_symbol (st->left, name, module, generic);

   if (retval == NULL)
     retval = find_symbol (st->right, name, module, generic);
+*/

   return retval;
 }

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[aldot at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

Bernhard Reutner-Fischer <aldot at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldot at gcc dot gnu.org

--- Comment #4 from Bernhard Reutner-Fischer <aldot at gcc dot gnu.org> ---
I'm thinking about switching all these symbol lookups/symtree traversals (i.e.
the whole fortran frontend) to pointer comparison which should _greatly_
speedup any symbol lookup, fyi.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[matthew.thompson at nasa dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

Matt Thompson <matthew.thompson at nasa dot gov> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matthew.thompson at nasa dot gov

--- Comment #5 from Matt Thompson <matthew.thompson at nasa dot gov> ---
I just wanted to come on here and say this is still an issue in GCC 13.2 (on
macOS). I did a profile of my code today and saw that this 56-line file of just
uses:

https://github.com/GEOS-ESM/MAPL/blob/main/base/Base.F90

is our second longest file to compile, see:

https://github.com/GEOS-ESM/MAPL/wiki/Profiling-MAPL-Builds#checking-the-build-times-on-cli

taking longer than a 5600 line (!) file of actual exciting Fortran:

https://github.com/GEOS-ESM/MAPL/blob/main/gridcomps/History/MAPL_HistoryGridComp.F90

Is there anyway I can help move this bug to "CONFIRMED"?

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

Jerry DeLisle <jvdelisle at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jvdelisle at gcc dot gnu.org

--- Comment #6 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
HI Matt, I can try your patch and if all tests clean I will request for it to
be approved and I can push it. We have all been rather busy and short handed.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

Jerry DeLisle <jvdelisle at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-04-24
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #7 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
With the proposed patch, the following test case fails.


! { dg-do compile }
! { dg-options "-fsecond-underscore" }
! PR fortran/95689 - ICE in check_sym_interfaces, at fortran/interface.c:2015

module m2345678901234567890123456789012345678901234567890123456789_123
  type t2345678901234567890123456789012345678901234567890123456789_123
   end type
   interface
      module subroutine
s2345678901234567890123456789012345678901234567890123456789_123 &              
       (x2345678901234567890123456789012345678901234567890123456789_123)
      end
   end interface
end
submodule(m2345678901234567890123456789012345678901234567890123456789_123) &
          t2345678901234567890123456789012345678901234567890123456789_123
end

$ gfc -c -fsecond-underscore pr95689.f90 
pr95689.f90:14:74:

   14 |
submodule(m2345678901234567890123456789012345678901234567890123456789_123) &
      |                                                                        
 1
Error: Name ‘t2345678901234567890123456789012345678901234567890123456789_123’
at (1) is an ambiguous reference to
‘m2345678901234567890123456789012345678901234567890123456789_123.t2345678901234567890123456789012345678901234567890123456789_123’
from current program unit

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #8 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
Martin or Matt,

Can you test the following variation to see if you get better results.

        return st;
    }

  retval = NULL;
  if (c <= 0)
    retval = find_symbol (st->left, name, module, generic);

  if (c > 0 && retval == NULL)
    retval = find_symbol (st->right, name, module, generic);

  if (c > 0 && retval == NULL)
    retval = find_symbol (st->left, name, module, generic);

  if (c <= 0 && retval == NULL)
    retval = find_symbol (st->right, name, module, generic);

  return retval;

This does pass regression testing but I do not think it guarantees better
results.  Apparently the value of c does not guarantee a find going left or
right.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[matthew.thompson at nasa dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #9 from Matt Thompson <matthew.thompson at nasa dot gov> ---
Jerry,

I tried your patch, but it didn't seem to help my reproducer.

Stock GCC13:

Number of Modules | Build Time
----------------- | ----------
               10 |   0.336674
               20 |    2.34525
               30 |    7.37042
               40 |    17.2896
               50 |    33.9653

GCC13 with Jerry Patch:

Number of Modules | Build Time
----------------- | ----------
               10 |   0.378347
               20 |    2.51914
               30 |    8.10597
               40 |     18.982
               50 |    37.3188

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

Jerry DeLisle <jvdelisle at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jvdelisle at gcc dot gnu.org

--- Comment #10 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
Well the experiment did not work.  I think we need to do something a bit more
complex. I will asign to myself so it does fall into a crack and get back here
as we go. I will consult with others on ideas.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #11 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
I am able to run your reproducer and I can see the increasing times as the
number of modules goes up.  I am curious if you could randomize the subroutine
names? These appear fairly repetitive and I wonder if this biases the test.

My results:

Build time for base.F90 in Modules_100: 0.446443 seconds
Number of Modules | Build Time
----------------- | ----------
               10 |  0.0155371
               20 |   0.024554
               30 |   0.041164
               40 |  0.0620602
               50 |   0.092014
               60 |   0.135193
               70 |   0.184979
               80 |   0.255272
               90 |   0.335244
              100 |   0.446443

real    0m27.194s
user    2m27.698s
sys     0m21.231s

The build time presented appears to not be wall time so I wonder what this is.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[matthew.thompson at nasa dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #12 from Matt Thompson <matthew.thompson at nasa dot gov> ---
Jerry,

Actually, I took a look at my reproducer and it's not quite what I was wanting
(I made a mistake in the Jinja templates). I'm going to work on it now to fix
this up. And I'll look at adding the random name option as well. Back soon...

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[matthew.thompson at nasa dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #13 from Matt Thompson <matthew.thompson at nasa dot gov> ---
Okay I have a new reproducer that I'll attach here. It uses the random names.

I see the same behavior:

IFX 2024.1:

Number of Modules | Build Time
----------------- | ----------
               10 |   0.100479
               20 |    0.15462
               30 |   0.209833
               40 |   0.259712
               50 |   0.314469

GCC 13.2:

Number of Modules | Build Time
----------------- | ----------
               10 |    1.55647
               20 |    6.41986
               30 |    12.7215
               40 |    25.4188
               50 |    36.3083

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[matthew.thompson at nasa dot gov]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #14 from Matt Thompson <matthew.thompson at nasa dot gov> ---
Never mind. I'll send attachment to Jerry offline. It's too big for here.

[Bug fortran/98426] find_symbol in module.c traverses O(N) part of a search tree

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98426

--- Comment #15 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
(In reply to Matt Thompson from comment #14)
> Never mind. I'll send attachment to Jerry offline. It's too big for here.

Got it. It works quite well for our purposes.