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

["mscfd at gmx dot net" <gcc-bugzilla@gcc.gnu.org>]

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.