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.