Note on choosing string hash functions

Dmitry Antipov
2017-11-17T09:50:20Z

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