[Bug binutils/29010] New: libbfd has quadratic processing time for large debug info

[travis.downs at gmail dot com]

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.