https://sourceware.org/bugzilla/show_bug.cgi?id=29010
Bug ID: 29010
Summary: libbfd has quadratic processing time for large debug
info
Product: binutils
Version: 2.38
Status: UNCONFIRMED
Severity: normal
Priority: P2
Component: binutils
Assignee: unassigned at sourceware dot org
Reporter: travis.downs at gmail dot com
Target Milestone: ---
Empirically, calling addr2line on a single address with a backtrace in a file
with 100,000 DW_TAG_subprogram and/or DW_TAG_inlined_subroutine abbrevs take
more than a minute to generate the line number.
99.5% of the time is spent in lookup_func_by_offset and lookup_var_by_offset:
main
process_file (inlined)
translate_addresses (inlined)
bfd_map_over_sections
find_address_in_section
find_address_in_section
_bfd_elf_find_nearest_line
_bfd_dwarf2_find_nearest_line
comp_unit_find_nearest_line
comp_unit_maybe_decode_line_info
comp_unit_maybe_decode_line_info
- scan_unit_for_symbols (inlined)
90.59% lookup_func_by_offset (inlined)
8.93% lookup_var_by_offset (inlined)
Both of these functions have the same problem: they do a linear search over a
linked list with every abbrev of the given type, and we do this search for
every abbrev, so we have O(n^2) behavior. E.g., for 100,000 abbrevs that's 5
billion "next" operations while traversing the list (1e5^2 times a factor of
0.5 since the average traversal goes through half the list).
Perhaps we could keep some kind of more direct mapping between the abbrevs as
we accumulate them in the first pass, to avoid the quadratic slowdown in the
second pass.
--
You are receiving this mail because:
You are on the CC list for the bug.
