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

[Daniel Berlin <dan@cgsoftware.com>]

On Saturday, September 15, 2001, at 05:02 PM, Jason Molenda wrote:

> On Sat, Sep 15, 2001 at 04:51:35PM -0400, Daniel Berlin wrote:
>
>>
>> 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.
>
> Pretty cool.  I look forward to seeing this submitted, approved,
> and integrated with the gdb sources.
I sent it to you, actually.
I don't have time to submit it, unfortunately, i'm busy with gcc work 
and law school.
It would take an insignificant amount of time to write a changelog 
entry.  It gives no regressions on x86 or powerpc, and has been used for 
people debugging very large C++ programs with no change other than much 
faster lookups.
This was months ago, however.

>
> I'd like to stay focused on the topic on hand for now.  This
> discussion is about gdb currently experiencing a serious performance
> regression wrt the last release of gdb, and I'm submitting a patch
> to fix that.  I'd like to see this problem addressed before 5.1 goes
> out.
>
> Maybe I'm wasting my time, and in three months this work you're
> doing will make symbol searching vastly faster than it currently
> is.
>  But in the mean time, I want to fix the problem at hand.
> I could certainly understand if you're not interested in this
> particluar problem - the work you're doing could represent a major
> step beyond any of these existing algorithms.

> Do you have anything to add regarding this note?
> 	http://sources.redhat.com/ml/gdb-patches/2001-09/msg00195.html
>
Yes.  The reality is that it's likely the search needs to be rewritten.
This is one of the non-performance reasons i hashtable'd the blocks. You 
can just use msymbol_hash_iw on the key, and thus, don't need to worry 
about it at all.

In this case, however, we could just abort if the first character of a 
lookup is not strcmp_iw significant,and add your patch as well. That 
way, if it ever occurs, someone will bitch that their program aborts, 
and we can fix the problem entirely in the meanwhile.
> Jason