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

[Daniel Berlin <dan at cgsoftware dot com>]

On Saturday, September 15, 2001, at 04:08 PM, Jason Molenda wrote:

> 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.
Actually, I did.
You are talking about a hack i had added to avoid repeated lookups, not 
the later attempts to make lookup_block_symbol faster.

>
>> 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.
No, I'm not.
Please *read* what i am proposing.


>   Instead,
> why don't we fix the inefficiencies in lookup_block_symbol *and*
> reduce the number of calls to it?
Which is exactly what i propose doing, and in fact, *have done before*.
You are simply going by what appears on gdb-patches years ago, as 
submitted patches.


>   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)).
No, my proposal is not going to make it O(j * 1/2 * n).
It's going to make it O(j) with the patch i sent you a few hours ago, 
and O(log  j) if you combined it with an approach to not look in blocks 
unless the symbol is in there (which can be done in O(1) time.
> 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))
No, actually, it would be O(j).
Each block lookup takes O(1) time, if the block is a hash table.
If you had to search every globally unique block, you'd search j blocks, 
at O(1) time, for a total of O (j).

Combining the patch I sent you a few hours ago, with a patch to not even 
search blocks where the symbol won't be in, makes it O(log j).


Please stop assuming the patch i have sent you is something i had 
submitted already.
It is not, AFAIK.
It was talked about, if you look at the archives.

I have *been down this road before*.
I have *sped up gdb symbol lookups to the point they take effectively 
constant time (O (number of active scopes))*.
The patches to do this are *not* on gdb-patches.

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