From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 90588 invoked by alias); 17 Nov 2017 09:50:20 -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 89353 invoked by uid 89); 17 Nov 2017 09:48:17 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.8 required=5.0 tests=BAYES_00,KAM_LAZY_DOMAIN_SECURITY,KAM_STOCKGEN,KB_WAM_FROM_NAME_SINGLEWORD,RP_MATCHES_RCVD,SPF_HELO_PASS autolearn=no version=3.3.2 spammy=1.28 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; Fri, 17 Nov 2017 09:48:16 +0000 Received: from hqpgpgate101.nvidia.com (Not Verified[216.228.121.13]) by hqemgate16.nvidia.com id ; Fri, 17 Nov 2017 01:48:09 -0800 Received: from HQMAIL107.nvidia.com ([172.20.161.6]) by hqpgpgate101.nvidia.com (PGP Universal service); Fri, 17 Nov 2017 01:48:08 -0800 X-PGP-Universal: processed; by hqpgpgate101.nvidia.com on Fri, 17 Nov 2017 01:48:08 -0800 Received: from UKMAIL102.nvidia.com (10.26.138.15) by HQMAIL107.nvidia.com (172.20.187.13) with Microsoft SMTP Server (TLS) id 15.0.1293.2; Fri, 17 Nov 2017 09:48:08 +0000 Received: from localhost.localdomain (10.21.38.65) by UKMAIL102.nvidia.com (10.26.138.15) with Microsoft SMTP Server (TLS) id 15.0.1293.2; Fri, 17 Nov 2017 09:48:05 +0000 To: From: Dmitry Antipov Subject: Note on choosing string hash functions Message-ID: <33c45098-17a4-4c8a-fb14-137e70c7bb3f@nvidia.com> Date: Fri, 17 Nov 2017 09:50:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.4.0 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit 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/msg00009.txt.bz2 I'm curious why 'htab_hash_string' (libiberty/hashtab.c) uses: r = r * 67 + c - 113 but 'SYMBOL_HASH_NEXT' (gdb/minsyms.h) prefers an extra 'tolower' with: ((hash) * 67 + tolower ((unsigned char) (c)) - 113) Everyone assumes that 'tolower' is simple, fast, and usually implemented as a macro. But when >1M of mangled C++ symbols should be hashed, results may be somewhat surprising ('perf report'): 8.94% gdb libc-2.25.so [.] tolower 8.45% gdb gdb [.] d_print_comp_inner 5.29% gdb gdb [.] htab_hash_string 4.16% gdb gdb [.] minimal_symbol_reader::install 3.72% gdb libc-2.25.so [.] __memmove_sse2_unaligned_erms 3.63% gdb gdb [.] msymbol_hash_iw 3.24% gdb gdb [.] htab_find_slot 3.07% gdb gdb [.] rust_is_mangled 2.57% gdb gdb [.] eq_demangled_name_entry 2.42% gdb gdb [.] d_print_comp 2.36% gdb gdb [.] compare_minimal_symbols 2.32% gdb gdb [.] default_search_name_hash 2.20% gdb gdb [.] skip_spaces 2.13% gdb gdb [.] rust_demangle_sym 2.02% gdb gdb [.] hash_demangled_name_entry 2.00% gdb gdb [.] tolower@plt 1.90% gdb gdb [.] d_count_templates_scopes 1.89% gdb gdb [.] ada_decode 1.87% gdb libc-2.25.so [.] msort_with_tmp.part.0 1.48% gdb libc-2.25.so [.] strlen 1.46% gdb gdb [.] htab_expand 1.39% gdb [kernel.kallsyms] [.] native_irq_return_iret 1.34% gdb libc-2.25.so [.] __strchr_sse2 1.27% gdb gdb [.] d_name 1.17% gdb gdb [.] cplus_demangle_type 1.11% gdb libc-2.25.so [.] _int_malloc ... Dropping the 'tolower' from SYMBOL_HASH_NEXT immediately shows: 9.26% gdb gdb [.] d_print_comp_inner 6.97% gdb gdb [.] minimal_symbol_reader::install 5.80% gdb gdb [.] htab_hash_string 3.59% gdb libc-2.25.so [.] __memmove_sse2_unaligned_erms 3.41% gdb gdb [.] htab_find_slot 3.37% gdb gdb [.] rust_is_mangled 3.13% gdb libc-2.25.so [.] isspace 2.91% gdb gdb [.] eq_demangled_name_entry 2.75% gdb gdb [.] d_print_comp 2.56% gdb gdb [.] compare_minimal_symbols 2.42% gdb gdb [.] msymbol_hash_iw 2.37% gdb gdb [.] skip_spaces 2.33% gdb gdb [.] default_search_name_hash 2.32% gdb gdb [.] rust_demangle_sym 2.14% gdb gdb [.] ada_decode 2.14% gdb gdb [.] d_count_templates_scopes 2.05% gdb gdb [.] hash_demangled_name_entry 1.97% gdb libc-2.25.so [.] msort_with_tmp.part.0 1.72% gdb libc-2.25.so [.] strlen 1.61% gdb [kernel.kallsyms] [.] native_irq_return_iret 1.56% gdb gdb [.] htab_expand 1.55% gdb libc-2.25.so [.] __strchr_sse2 1.45% gdb gdb [.] d_name 1.41% gdb libc-2.25.so [.] _int_malloc 1.28% gdb gdb [.] cplus_demangle_type 1.03% gdb gdb [.] minimal_symbol_reader::record_full 1.02% gdb gdb [.] internal_cplus_demangle 1.01% gdb gdb [.] elf_symtab_read ... Observed on current binutils-gdb trunk, glibc 2.25, gcc 7.2.1, -g -O3 -march=native -mtune=native, "remote" (both gdb and gdbserver on the same system) debugging Firefox debug build, reports was generated with 'perf record -F 10000 gdb -batch --readnever -q -ex "set sysroot /" -ex "set pagination off" \ -ex "target extended-remote :5555" -ex "thread apply all bt" -ex "quit"'. Dmitry