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

Daniel Berlin
2001-09-15T08:01:00Z

"Eli Zaretskii" <eliz@is.elta.co.il> writes:

>> Date: Sat, 15 Sep 2001 00:52:56 -0700
>> From: Jason Molenda <jason-swarelist@molenda.com>
>>
>> With the gdb 5.1 symtab.c, typing "p aWindowPtr" in SimpleText will
>> take 3.5 seconds to complete (as reported by 'maint time 1').
>>
>> With the patches (or with gdb 5.0), typing "p aWindowPtr" in
>> SimpleText takes between 0.01 and 0.00 seconds (as reported by
>> 'maint time 1' -- it's at the limits of maint time's granularity.
>> Hence my earlier characterization as "unmeasurable".)
> [...]
> > Dan's patch dropped the "exits out of linear search" -- now it
>> binary searches to the beginning of plausible ranges, and steps
>> through to the end of the block. It's now an O(1/2*N) algorithm
>> for worst-case, i.e. non-matches.
>
> Are you saying that Dan's change was a gratuitous one, i.e. there was
> no reason whatsoever to make that change?

He would be correct, but only if he can prove that non of the
languages GDB supports, could ever end up calling lookup_block_symbol
(directly or indirectly), or contain symbols, that start with a
character strcmp_iw ignores.

His argument is that if this was true, it would mean a bunch of other
things are broken too.
This is not a good argument, it's quite possible they are broken.
Tons of stuff related to support for more than just C in GDB are
broken, or not in a good state.
It's quite possible I missed removing some other instances of the same
assumption in that routine.
Which, BTW, would slow him down even more.

All i'm asking is that he *prove*, besides using the GDB testsuite
(which isn't a good test here, since it's tests for languages more
than just C are pretty lacking), that his change is correct.
I.E. That such a case would never happen.
This is not easy.
I couldn't do it, which is why i started concentrating on alternate
methods of speeding it up.
His time would be better spent just implementing one of the methods
that doesn't require dealing with this issue at all, then it would
trying to characterize my concern as "vague hand-waving".

I'd estimate it would take him about the same time he's spent arguing
on this mailing list, to implement them. This is based of course, on
how long it took me.
I'd also happily send the patches to him, so he could clean them up
and submit them, or whatever, which would take an absolutely trivial
amount of time.

--Dan

--
"What do batteries run on?
"-Steven Wright