Re: Improving gcc scalability wrt _extra_ large C files

[Geoff Keating <geoffk at geoffk dot org>]

"Joseph S. Myers" <jsm28 at cam dot ac dot uk> writes:

> On Thu, 13 Mar 2003, Jacques THOMAS wrote:
> 
> > As I said a few days ago, gcc is awfully slow when it comes to compiling 
> > some very large generated C files (several hundred thousands of 
>                             ^
> > 1/ lookup_tag (gcc/cp/decl dot c at line 5239) does, more or less, a linear 
>                      ^^
> Are you talking about C or C++?  Name lookup in C++ is much more complex
> than in C and may have some reason to be slow.

I've looked at that code, and there's plenty of room for improvement.
Consider this loop:

  for (level = binding_level; level; level = level->level_chain)
    {
      register tree tail;
      if (ANON_AGGRNAME_P (name))
        for (tail = level->tags; tail; tail = TREE_CHAIN (tail))
          {
            /* There's no need for error checking here, because
               anon names are unique throughout the compilation.  */
            if (TYPE_IDENTIFIER (TREE_VALUE (tail)) == name)
              POP_TIMEVAR_AND_RETURN (TV_NAME_LOOKUP, TREE_VALUE (tail));
          }

it looks like that's doing a linear search for this (compiler-created)
name through all the tags in all the scopes, in order to find the one
entry for this name.  Even in reasonably sane code, like Apple's
Finder, that can mean a search through tens of thousands of entries.

-- 
- Geoffrey Keating <geoffk at geoffk dot org>