From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27386 invoked by alias); 28 Nov 2017 15:13:38 -0000 Mailing-List: contact gdb-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sourceware.org Received: (qmail 27371 invoked by uid 89); 28 Nov 2017 15:13:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.7 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KB_WAM_FROM_NAME_SINGLEWORD,SPF_HELO_PASS,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=15th, 3.7, 8646, 3.86 X-HELO: hqemgate16.nvidia.com Received: from hqemgate16.nvidia.com (HELO hqemgate16.nvidia.com) (216.228.121.65) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 28 Nov 2017 15:13:36 +0000 Received: from hqpgpgate101.nvidia.com (Not Verified[216.228.121.13]) by hqemgate16.nvidia.com id ; Tue, 28 Nov 2017 07:13:38 -0800 Received: from HQMAIL101.nvidia.com ([172.20.161.6]) by hqpgpgate101.nvidia.com (PGP Universal service); Tue, 28 Nov 2017 07:13:34 -0800 X-PGP-Universal: processed; by hqpgpgate101.nvidia.com on Tue, 28 Nov 2017 07:13:34 -0800 Received: from UKMAIL102.nvidia.com (10.26.138.15) by HQMAIL101.nvidia.com (172.20.187.10) with Microsoft SMTP Server (TLS) id 15.0.1293.2; Tue, 28 Nov 2017 15:13:34 +0000 Received: from localhost.localdomain (10.21.38.99) by UKMAIL102.nvidia.com (10.26.138.15) with Microsoft SMTP Server (TLS) id 15.0.1293.2; Tue, 28 Nov 2017 15:13:30 +0000 Subject: Re: Note on choosing string hash functions To: Pedro Alves CC: References: <33c45098-17a4-4c8a-fb14-137e70c7bb3f@nvidia.com> <4fc8cd33-a362-ddf5-9a7c-e69eab385587@redhat.com> <2ae7734e-3ea1-e017-4a87-65a3af25d0c0@redhat.com> From: Dmitry Antipov Message-ID: <05be76c3-56ff-36bf-ec57-e1339684381d@nvidia.com> Date: Tue, 28 Nov 2017 15:13:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.4.0 MIME-Version: 1.0 In-Reply-To: <2ae7734e-3ea1-e017-4a87-65a3af25d0c0@redhat.com> Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: UKMAIL102.nvidia.com (10.26.138.15) To UKMAIL102.nvidia.com (10.26.138.15) X-IsSubscribed: yes X-SW-Source: 2017-11/txt/msg00030.txt.bz2 On 11/28/2017 03:00 PM, Pedro Alves wrote: > Anyway, this is just a brain dump from a little investigation I did this = past > weekend, and I think that this area has a lot of scope for improvements, = but > I won't be able to follow up on any of this myself in the next following > weeks at least, with several gdb 8.1 issues on my plat=D0=B5. Just for the record, I have a brain dump around this area too :-). Instead = of optimizing htab_hash_string itself, we can try to reduce number of calls (a= nd drop a few calls to strcmp as well if lucky): --- gdb/symtab.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/gdb/symtab.c b/gdb/symtab.c index ebb7fbe1e0..c9dab4d575 100644 --- a/gdb/symtab.c +++ b/gdb/symtab.c @@ -673,6 +673,7 @@ symbol_set_language (struct general_symbol_info *gsymbo= l, struct demangled_name_entry { const char *mangled; + hashval_t hashval; char demangled[1]; }; @@ -684,7 +685,7 @@ hash_demangled_name_entry (const void *data) const struct demangled_name_entry *e =3D (const struct demangled_name_entry *) data; - return htab_hash_string (e->mangled); + return e->hashval; } /* Equality function for the demangled name hash. */ @@ -697,7 +698,8 @@ eq_demangled_name_entry (const void *a, const void *b) const struct demangled_name_entry *db =3D (const struct demangled_name_entry *) b; - return strcmp (da->mangled, db->mangled) =3D=3D 0; + return (da->hashval !=3D db->hashval) ? 0 + : (strcmp (da->mangled, db->mangled) =3D=3D 0); } /* Create the hash table used for demangled names. Each hash entry is @@ -816,6 +818,8 @@ symbol_set_names (struct general_symbol_info *gsymbol, linkage_name_copy =3D linkage_name; entry.mangled =3D linkage_name_copy; + entry.hashval =3D htab_hash_string (linkage_name_copy); + slot =3D ((struct demangled_name_entry **) htab_find_slot (per_bfd->demangled_names_hash, &entry, INSERT)); @@ -848,6 +852,7 @@ symbol_set_names (struct general_symbol_info *gsymbol, offsetof (struct demangled_name_entry, deman= gled) + demangled_len + 1)); (*slot)->mangled =3D linkage_name; + (*slot)->hashval =3D entry.hashval; } else { @@ -864,6 +869,7 @@ symbol_set_names (struct general_symbol_info *gsymbol, mangled_ptr =3D &((*slot)->demangled[demangled_len + 1]); strcpy (mangled_ptr, linkage_name_copy); (*slot)->mangled =3D mangled_ptr; + (*slot)->hashval =3D entry.hashval; } if (demangled_name !=3D NULL) --=20 This immediately moves htab_hash_string down in reports, from: 9.67% gdb gdb [.] find_pc_sect_psymtab 6.62% gdb gdb [.] bcache_full 5.41% gdb libc-2.25.so [.] tolower 4.44% gdb gdb [.] htab_hash_string = ; 4th place 4.14% gdb gdb [.] htab_find_slot_with_hash 3.86% gdb gdb [.] load_partial_dies 3.56% gdb gdb [.] strcmp_iw_ordered 3.48% gdb gdb [.] read_indirect_string_at= _offset_from 3.26% gdb gdb [.] lookup_minimal_symbol_b= y_pc_name 3.12% gdb gdb [.] cpname_parse 2.77% gdb gdb [.] read_attribute_value 2.72% gdb gdb [.] cpname_lex 2.71% gdb libc-2.25.so [.] __strcmp_sse2_unaligned 2.49% gdb gdb [.] peek_die_abbrev 2.30% gdb libc-2.25.so [.] _int_malloc 2.16% gdb gdb [.] d_print_comp_inner to: 9.78% gdb gdb [.] find_pc_sect_psymtab 6.63% gdb gdb [.] bcache_full 5.00% gdb libc-2.25.so [.] tolower 4.20% gdb gdb [.] htab_find_slot_with_hash 3.79% gdb gdb [.] load_partial_dies 3.68% gdb gdb [.] lookup_minimal_symbol_b= y_pc_name 3.54% gdb gdb [.] read_indirect_string_at= _offset_from 3.47% gdb gdb [.] strcmp_iw_ordered 3.39% gdb gdb [.] cpname_parse 2.71% gdb gdb [.] read_attribute_value 2.53% gdb gdb [.] cpname_lex 2.46% gdb gdb [.] peek_die_abbrev 2.43% gdb gdb [.] d_print_comp_inner 2.43% gdb libc-2.25.so [.] _int_malloc 2.38% gdb gdb [.] htab_hash_string = ; 15th place at the cost of having per_bfd->storage_obstack ~3.7% larger for libxul.so w= ith ~2.3M symbols. Dmitry