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

Jason Molenda
2001-09-15T13:08:00Z

On Sat, Sep 15, 2001 at 10:54:06AM -0400, Daniel Berlin wrote:

> Note that combining the solutions I later attempted avoids the problem
> of having
> to show that all the languages gdb supports can't do symbol lookups
> on something that starts with a character strcmp_iw ignores,
> altogether.

I guess you didn't read either of my initial notes in this discusssion.
I provided pointers to them in the patch submission.

> This would be using a hash table for the block array, which we already
> have a hash function ideal for (minsym_hash_iw or whatever it's
> called), and the not actually searching blocks that don't contain the
> symbol.
>
> This would give you O(1) symbol lookup time, effectively (A given
> symbol only searches a constant number of blocks).
> This would certainly make your debugger much faster to respond.

What you're proposing is to ignore the inefficiencies of
lookup_block_symbol by reducing the number of calls to it. Instead,
why don't we fix the inefficiencies in lookup_block_symbol *and*
reduce the number of calls to it? Imagine how the gdb users will
be dancing in the street, thanking buddha for their great fortune of
having such a wonderful debugger.

Concretely. GDB has a number of symtabs, call it 'i', and a number of
_unique_ global blocks, call it 'j'. Every symtab has a link to a global
block, but few of these global blocks are unique. In gdb itself, i is
an order of magnitude larger than j. I expect some programs will have
i two orders of magnitude larger than j. Each global block has a number
of symbols in it, call the average of these 'n'.

In gdb 5.0, looking for an undefined symbol will happen on order of
O(i * lg (n)). In gdb 5.1, that search will be on the order of
O(i * 1/2 * n). Dan's proposal is to change this to O(j * 1/2 * n).
I am looking for at _least_ O(i * lg (n)), but I'd really like to see
us get both of these eventually for O(j * lg (n)).

If we define conservatively as i = j * 10, these become

gdb 5.0 O (j * 10 * lg (n))
gdb 5.1 O (j * 10 * 1/2 * n)
My patch O (j * 10 * lg (n))

What I'd like to see O (j * lg (n))
Dan's block patch alone O (j * 1/2 * n))

Debugging gdb itself, "i" is 330, and "j" is 23. The average number
of symbols was small - I don't have the number here right now, but
I think it was around 10 symbols. All of these numbers are a lot
larger for a C++ program, obviously.

Jason