Speedup area - Strings/Identifiers

[Ben White]

 From the GCC Wiki, Speedup Areas page, Strings/identifiers section:

/3.   Replace identifier hash table with a better data structure (have 
already tried a ternary tree, it's not faster; could try to code it even 
cleverer than it already was; B* trees might be worth looking into)/

A different approach:

Separate the "handle identifier characteristics" process from the "which 
identifier is this string?" process.

Identifier characteristics are usually handled as a table, with 
characteristics as fields; e.g. undefined/defined, 
float/double/int/long, structure/not-structure.  The table key is 
usually the row number itself.

As I understand it, in GCC now, when the parser encounters an identifier 
string, it first looks up the string using a hash table, returning the 
internal key for the identifier.  Then it uses the key and the 
identifier table to handle characteristics.

This is costly.  Maintaing a hash table using insertions and deletions 
is costly. 

Stopping all parsing, and using memory storage for hashing and hash 
tables, is also expensive.  If they are used, they will be brought into 
the cache.  Information needed when the identification is over will be 
paged out.  This is true, no matter which method is used - hashing, 
ternary trees, or B* trees.

A two-pass approach might be significantly faster.

In the first pass, each identifier is parsed out, and appended to the 
unsorted list of all identifier instances, matched with its location - 
(a location id might be simply the count of identifier instances, e.g. 
the 1,024th identifier instance , or physical location in the source 
text.) 

The list of identifier instances, with their matching locations, are 
then sorted en-mass.

A unique, numeric, ID is assigned to each unique identifier string, and 
a cross-reference table is populated.  For each identifier instance in 
the source, there is an entry containing the unique identifier ID.

In the second pass, the identifier instance ID is the key to return the 
unique identifier ID.  By its nature, this table will be processed in 
sequence, once.

Collisions are guaranteed.  They are not show stoppers.   When an 
identifier is re-defined in a sub-section, the characteristics for the 
previous definition will have to be temporarily stored somewhere else, 
and restored at the conclusion of the subsection.

Benefits:

1. All the sorting can be done at one time, using the most efficient 
sort - Radix/Bucket.
2. The second parsing pass will be considerably more efficient because 
it will not have to be continually interrupted to do a 
hash-search-insertion.
3.  The larger the program, e.g. whole Kernel compiles, or GCC compiles, 
the more efficient the sort will be.  Compiler perfomance is often 
judged by how fast it compiles the largest programs.

Drawbacks:

1. The unique ID table will be large.
2. Two parsing passes will be assumed to be less efficient, before this 
is ever tried.  


Ben White