Improving gcc scalability wrt _extra_ large C files

[Jacques THOMAS <jthomas at cs dot purdue dot edu>]

Hi all,

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 
different types and variables in the global lexical scope).

As advised by Zack Weinberg, I did profile the latest cvs version of 
cc1plus, while it was compiling my large files.

Here are the culprits, as shown by gprof :

 %   cumulative   self              self     total          
time   seconds   seconds    calls  ms/call  ms/call  name   
44.68    245.13   245.13   150000     1.63     1.63  clear_anon_tags
41.42    472.38   227.24    50003     4.54     4.55  lookup_tag

Here is my understanding of what these two functions do :

1/ lookup_tag (gcc/cp/decl dot c at line 5239) does, more or less, a linear 
search in a linked list containing all the known names (variable and 
funtion names, typenames) of the current binding level. If the symbol 
looked up for is not found in the current binding level, then the search 
is repeated in the upper binding level.

2/ clear_anon_tags (gcc/cp/decl dot c at line 2786) deletes all the anonymous 
tags that have been used so far ; this operation does also involve a 
linear search on the list of names from the current binding level.

For the moment, I am focused on lookup_tag, as I can modify the code 
generator in order to use less anonymous tags and minimize the 
importance of clear_anon_tags's behavior.

My idea for improving lookup_tag is to use one hash table per binding 
level, with entries pointing to the tags of the binding level. To do 
that I would modify push_tag so that it does insert the symbol in the 
hash table at the same time that it does insert it in the linked list. 
lookup_tag could then use this hash table to do faster lookups.

I will start experimenting this solution very soon. Has anybody heard of 
any other similar work beeing done by someone else ? Any advise is more 
than welcome ! ;-)

Cheers,
Jacques.