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

[Daniel Berlin <dan at cgsoftware dot com>]

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).