From mboxrd@z Thu Jan 1 00:00:00 1970 From: Daniel Berlin To: Eli Zaretskii Cc: jason-swarelist@molenda.com, gdb-patches@sources.redhat.com Subject: Re: [RFA] bug in symtab.c:lookup_block_symbol()'s search method Date: Sat, 15 Sep 2001 08:01:00 -0000 Message-id: <87k7z0pkfv.fsf@cgsoftware.com> References: <20010909074800.A8112@shell17.ba.best.com> <3B9D054A.4C3CC2B1@cygnus.com> <20010910113226.A23487@shell17.ba.best.com> <87zo82swwa.fsf@cgsoftware.com> <20010910130347.A5628@shell17.ba.best.com> <8766aq7nki.fsf@cgsoftware.com> <3BA219EF.3000300@cygnus.com> <9003-Fri14Sep2001190223+0300-eliz@is.elta.co.il> <20010914091241.A28921@shell17.ba.best.com> <1659-Fri14Sep2001204927+0300-eliz@is.elta.co.il> <20010915005255.A2369@shell17.ba.best.com> <2110-Sat15Sep2001133818+0300-eliz@is.elta.co.il> X-SW-Source: 2001-09/msg00191.html "Eli Zaretskii" writes: >> Date: Sat, 15 Sep 2001 00:52:56 -0700 >> From: Jason Molenda >> >> 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