[Bug binutils/29010] New: libbfd has quadratic processing time for large debug info
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.
[Bug binutils/29010] libbfd has quadratic processing time for large debug info
https://sourceware.org/bugzilla/show_bug.cgi?id=29010 --- Comment #1 from Travis Downs --- Sorry everywhere I said "abbrev" I should have probably said "DIE" instead. -- You are receiving this mail because: You are on the CC list for the bug.
[Bug binutils/29010] libbfd has quadratic processing time for large debug info
https://sourceware.org/bugzilla/show_bug.cgi?id=29010 Travis Downs changed: What|Removed |Added CC||travis.downs at gmail dot com --- Comment #2 from Travis Downs --- I believe this was introduced in: https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=abe2a28aaa7a2bfd0f3061c72a98eb898976b721 https://sourceware.org/bugzilla/show_bug.cgi?id=27484 So it applies in 2.36 forwards. -- You are receiving this mail because: You are on the CC list for the bug.
[Bug binutils/29010] libbfd has quadratic processing time for large debug info
https://sourceware.org/bugzilla/show_bug.cgi?id=29010 Travis Downs changed: What|Removed |Added CC||nickc at redhat dot com -- You are receiving this mail because: You are on the CC list for the bug.
[Bug binutils/29010] addr2line (via libbfd) has quadratic processing time for large debug info
https://sourceware.org/bugzilla/show_bug.cgi?id=29010 Travis Downs changed: What|Removed |Added Summary|libbfd has quadratic|addr2line (via libbfd) has |processing time for large |quadratic processing time |debug info |for large debug info -- You are receiving this mail because: You are on the CC list for the bug.
[Bug binutils/28697] New: objdump doesn't look for separate debug styles using "build-id" style
https://sourceware.org/bugzilla/show_bug.cgi?id=28697 Bug ID: 28697 Summary: objdump doesn't look for separate debug styles using "build-id" style Product: binutils Version: 2.37 Status: UNCONFIRMED Severity: normal Priority: P2 Component: binutils Assignee: unassigned at sourceware dot org Reporter: travis.downs at gmail dot com Target Milestone: --- Created attachment 13856 --> https://sourceware.org/bugzilla/attachment.cgi?id=13856&action=edit uses the debuglink and build-id styles to build and strip a binary Support for the "build ID" style of separate debug lookup was added in 2017: https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=2425a30e406a0523020b7e70abb864a06a45bb97 However, it seems to be used only for a few flags like -S, but it is ignored for others, like --syms. Using strace, one can see that for --syms it is only looks for the old style "debuglink" debug info. It never looks in the `.build-id` based paths even when the note is present. Find below a test program which shows the issue, based on strace output, chmod +x it and run. -- You are receiving this mail because: You are on the CC list for the bug.
[Bug binutils/28697] objdump often doesn't look for separate debug files when using "build-id" style
https://sourceware.org/bugzilla/show_bug.cgi?id=28697 Travis Downs changed: What|Removed |Added Summary|objdump doesn't look for|objdump often doesn't look |separate debug styles using |for separate debug files |"build-id" style|when using "build-id" style -- You are receiving this mail because: You are on the CC list for the bug.
[Bug binutils/28697] objdump often doesn't look for separate debug files when using "build-id" style
https://sourceware.org/bugzilla/show_bug.cgi?id=28697 --- Comment #3 from Travis Downs --- Thanks Nick, that's quite the fast turnaround on this one, thanks very much! Do I understand correctly that things checked into master now will be released in binutils 2.38? -- You are receiving this mail because: You are on the CC list for the bug.
