add a trie to map quickly from address range to compilation unit
authorSteinar H. Gunderson <sesse@google.com>
Fri, 20 May 2022 14:10:34 +0000 (16:10 +0200)
committerJan Beulich <jbeulich@suse.com>
Fri, 20 May 2022 14:10:34 +0000 (16:10 +0200)
commitb43771b045fb5616da3964f2994eefbe8ae70d32
tree662fc9a36f4b6895e65ca70c81f6f6f28ababf9e
parentbd7d326debef642c0a98f859807d794d8d68afc7
add a trie to map quickly from address range to compilation unit

When using perf to profile large binaries, _bfd_dwarf2_find_nearest_line()
becomes a hotspot, as perf wants to get line number information
(for inline-detection purposes) for each and every sample. In Chromium
in particular (the content_shell binary), this entails going through
475k address ranges, which takes a long time when done repeatedly.

Add a radix-256 trie over the address space to quickly map address to
compilation unit spaces; for content_shell, which is 1.6 GB when some
(but not full) debug information turned is on, we go from 6 ms to
0.006 ms (6 µs) for each lookup from address to compilation unit, a 1000x
speedup.

There is a modest RAM increase of 180 MB in this binary (the existing
linked list over ranges uses about 10 MB, and the entire perf job uses
between 2–3 GB for a medium-size profile); for smaller binaries with few
ranges, there should be hardly any extra RAM usage at all.
bfd/dwarf2.c