From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 99730 invoked by alias); 8 Aug 2017 20:32:05 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 99637 invoked by uid 89); 8 Aug 2017 20:32:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=admit, unlimited, sacrifice, yyyymmdd X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 08 Aug 2017 20:31:54 +0000 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 27FED4F93B for ; Tue, 8 Aug 2017 20:31:53 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 27FED4F93B Authentication-Results: ext-mx04.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx04.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=keiths@redhat.com Received: from valrhona.uglyboxes.com (ovpn04.gateway.prod.ext.phx2.redhat.com [10.5.9.4]) by smtp.corp.redhat.com (Postfix) with ESMTPS id A351551DF4; Tue, 8 Aug 2017 20:31:52 +0000 (UTC) From: Keith Seitz Subject: Re: [PATCH 26/40] Optimize .gdb_index symbol name searching To: Pedro Alves , gdb-patches@sourceware.org References: <1496406158-12663-1-git-send-email-palves@redhat.com> <1496406158-12663-27-git-send-email-palves@redhat.com> Message-ID: Date: Tue, 08 Aug 2017 20:32:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 In-Reply-To: <1496406158-12663-27-git-send-email-palves@redhat.com> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2017-08/txt/msg00154.txt.bz2 On 06/02/2017 05:22 AM, Pedro Alves wrote: > I got, before the previous patch (-O2, x86-64): > > real 0m1.773s > user 0m1.737s > sys 0m0.040s > > and after this patch: > > real 0m1.361s > user 0m1.315s > sys 0m0.040s The results on my computer are slightly more dramatic, running with no optimization, your test case (using Fedora 21 system gdb w/index debuginfo) goes from about 15 seconds down to about 2.5 seconds. Very nice! > That resulted in 1351355 name_components. Each entry takes 8 bytes, > so that's 10810840 bytes (ignoring std::vector overhead), or ~10.3 MB. > That's IMO too small to worry about, given GDB was using over 7400MB > total at that point. I.e., we're talking about 0.1% increase. Indeed. I'd sacrifice that kind of memory for the kind of speed increase you've achieved -- in a heartbeat! > with only 8-bit and 32-bit tables, that'd be: > > 1349057 * 1 + 2298 * 4 + 4 * 1351355 = 6763669 bytes, or ~6.5MB. > > I don't think we need to bother though. I'm all for memory usage optimization and whatnot, but since the benefit is so small (55% of these new tables saved but only 0.06% of total memory), I prefer simplicity. So you won't get anything but agreement from me on this. > I also timed: > > $ time gdb --batch -q -p `pidof firefox` > $ time gdb --batch -q -p `pidof firefox` -ex "b main" > $ time gdb --batch -q -p `pidof firefox` -ex "set max-completion unlimited" -ex "complete b " I'd like to reproduce this, but my computer is incapable of running this test. I'll take your word for it. ;-) > gdb/ChangeLog: > yyyy-mm-dd Pedro Alves > > * dwarf2read.c > (mapped_index::name_components): New field. > (mapped_index::symbol_name_at): New method. Silly nit: Isn't the form most are using "(tag name) : New field."? I know I've relied on this several times to find changes in the ChangeLog. > (create_addrmap_from_index): Call mapped_index ctor. I don't see any changes to this function in the patch -- attributed to wrong function? > diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c > index f523326..e955131 100644 > --- a/gdb/dwarf2read.c > +++ b/gdb/dwarf2read.c > @@ -178,6 +178,51 @@ DEF_VEC_I (offset_type); [snip] > + > +/* An index into a (C++) symbol name component in a symbol name as > + recorded in the mapped_index's symbol table. For each C++ symbol > + in the symbol table, we record one entry for the start of each > + component in the symbol in a table of name components, and then > + sort the table, in order to be able to binary search symbol names, > + ignoring leading namespaces, both completion and regular look up. > + For example, for symbol "A::B::C", we'll have an entry that points > + to "A::B::C", another that points to "B::C", and another for "C". > + Note that function symbols in GDB index have no parameter > + information, just the function/method names. You can convert a > + name_component to a "const char *" using the > + 'mapped_index::symbol_name_at(offset_type)' method. */ missing nl? > +struct name_component > +{ > + /* Offset in the symbol name where the component starts. Stored as > + a (32-bit) offset instead of a pointer to save memory and improve > + locality on 64-bit architectures. */ > + offset_type name_offset; > + > + /* The symbol's index in the symbol and constant pool tables of a > + mapped_index. */ > + offset_type idx; > +}; > + > /* A description of the mapped index. The file format is described in > a comment by the code that writes the index. */ > struct mapped_index > @@ -3390,6 +3424,7 @@ dwarf2_read_index (struct objfile *objfile) > create_addrmap_from_index (objfile, &local_map); > > map = XOBNEW (&objfile->objfile_obstack, struct mapped_index); > + map = new (map) mapped_index (); > *map = local_map; > > dwarf2_per_objfile->index_table = map; This function (dwarf2_read_index) is not mentioned in the ChangeLog. Could this actually be incorrectly listed in the ChangeLog under create_addrmap_from_index? > @@ -4095,6 +4134,22 @@ gdb_index_symbol_name_matcher::matches (const char *symbol_name) > } > > static void > +dw2_expand_marked_cus > + (mapped_index &index, offset_type idx, > + struct objfile *objfile, > + gdb::function_view file_matcher, > + gdb::function_view expansion_notify, > + search_domain kind); > + > +static void > +dw2_expand_symtabs_matching_symbol > + (mapped_index &index, > + const lookup_name_info &lookup_name_in, > + gdb::function_view symbol_matcher, > + enum search_domain kind, > + gdb::function_view on_match); Isn't it rather unusual for us to have forward decls in the middle of a file? > + > +static void > dw2_expand_symtabs_matching > (struct objfile *objfile, > gdb::function_view file_matcher, > @@ -4186,30 +4239,214 @@ dw2_expand_symtabs_matching [snip] > +static void > +dw2_expand_symtabs_matching_symbol > + (mapped_index &index, > + const lookup_name_info &lookup_name, > + gdb::function_view symbol_matcher, > + enum search_domain kind, > + gdb::function_view match_callback) > +{ [snip] > + > + /* Sort name_comp elements by name. */ I presume that "name_comp" is really "name_components"? [snip] > + std::vector matches; > + matches.reserve (std::distance (lower, upper)); > + > + for (;lower != upper; ++lower) > + { > + const char *qualified = index.symbol_name_at (lower->idx); > + > + if (!lookup_name_matcher.matches (qualified) > + || (symbol_matcher != NULL && !symbol_matcher (qualified))) > continue; > > - /* The name was matched, now expand corresponding CUs that were > - marked. */ > - vec = (offset_type *) (index->constant_pool > - + MAYBE_SWAP (index->symbol_table[idx + 1])); > + matches.push_back (lower->idx); > + } > + > + std::sort (matches.begin (), matches.end ()); > + > + /* Finally call the callback, once per match. */ > + ULONGEST prev = -1; > + for (offset_type idx : matches) > + { > + if (prev != idx) > + { > + match_callback (idx); > + prev = idx; > + } > + } I admit, I'm a little surprised by the number of steps involved here: push every element in the range into a vector, sort, then de-dup & perform callback. Had I implemented this, my initial attempt would have been to use a htab_up and take the sorting time on insertion. I can imagine that for very large ranges, your approach could outperform an htab; do you expect these ranges to be that large? Have I overlooked something? [I'm just curious. Not suggesting any changes need to be made.] > + > + /* Above we use a type wider than idx's for 'prev', since 0 and > + (offset_type)-1 are both possible values. */ > + static_assert (sizeof (prev) > sizeof (offset_type), ""); > +} > + [snip] Keith