Re: [RFA] bug in symtab.c:lookup_block_symbol()'s search method

Daniel Berlin
2001-09-15T13:52:00Z

Since you seem to be having trouble either reading, or understanding,
what I have proposed, and implemented, let me break it down for you, in
simple english, so there is no confusion as to what you *think* i am
proposing (based on god knows what, probably some old email with a patch
from gdb-patches), and what I have proposed, and implemented:

First, you can speed up lookup_block_symbol. I sent you a patch hours
ago that does this.

It turns the linear array of symbols in a block into buckets of a
chained hashtable, adding a "hash_next" member to struct symbol to chain
them together.

The hash function is msymbol_hash_iw.
The hashed key is SYMBOL_SOURCE_NAME.

This turns block lookups, on non-function argument lists (function
argument lists aren't sorted, they have to be kept in the original
order), into O(1).
This makes your max symbol lookup time, O (j), where j is the number of
globally unique blocks.

Second, you can take lookup_symbol, and modify it to only call
lookup_block_symbol once.

This is done by providing a mapping from names to blocks they exist in,
using a hash table with SYMBOL_SOURCE_NAME keys, and sparse bitmaps as
the data, with a bit set per block it exists in.

Now, for undefined symbols, the cost is O(1), total. It won't exist in
the mapping, and thus, we know the symbol exists nowhere in the blocks.
For defined symbols, the cost is O(number of scopes to search), where
number of scopes to search <= all the blocks in the program, worst case
(in reality, it's usually < 20).
We simply test one bit per scope (since each scope is represented by a
single block), and as soon as we get a hit, we call lookup_block_symbol.

This will be O (number of scopes to search).
It will only call lookup_block_symbol *one* time.
Theoretically, number of scopes to search can be J, but this would
require every scope in your program be visible at once, which, unless
i'm mistaken, is pretty much impossible.
number of scopes to search is usually between 7 and 30, and is only
dependent on the nesting structure of your program, not it's size.
Now will you stop mischaracterizing what I have proposed?

It's pretty hard to do better than the above, but possible.
It would require a significant rework of the symbol table structure,
while both of the things above required a few hours each (In fact, I
redid the first one this morning, since I didn't have the source tree
around anymore).