From mboxrd@z Thu Jan 1 00:00:00 1970 From: Daniel Berlin To: Jason Molenda Cc: gdb-patches@sources.redhat.com Subject: Re: [RFA] bug in symtab.c:lookup_block_symbol()'s search method Date: Sat, 15 Sep 2001 14:21:00 -0000 Message-id: <952C66E6-AA1F-11D5-94ED-0030657B5340@cgsoftware.com> References: <20010915140234.A17079@shell17.ba.best.com> X-SW-Source: 2001-09/msg00200.html 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