[Bug binutils/28978] New: [2.38 Regression] O(n²) when parsing DWARF2 info

[steinar+sourceware at gunderson dot no]

https://sourceware.org/bugzilla/show_bug.cgi?id=28978

            Bug ID: 28978
           Summary: [2.38 Regression] O(n²) when parsing DWARF2 info
           Product: binutils
           Version: 2.38
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: binutils
          Assignee: unassigned at sourceware dot org
          Reporter: steinar+sourceware at gunderson dot no
  Target Milestone: ---

Hi,

There is a recent significant slowdown in running “perf report” on DWARF debug
info, which seems to be due to

commit ca8f6bc629cb27792ce449e7253c74a3f6f75fda
Author: Nick Clifton <nickc@redhat.com>
Date:   Tue Mar 2 16:08:23 2021 +0000

    Fix the BFD library's parsing of DIEs where specification attributes can
refer to variables that are defined later on.

            PR 27484
            * dwarf2.c (scan_unit_for_symbols): Scan twice, once to accumulate
            function and variable tags and a second time to resolve their
            attributes.

On loading line number information for a compilation unit for the first time,
the second pass calls lookup_func_by_offset() for each function, and
lookup_var_by_offset() for each variable. The problem is that each of these
scan through a linked list containing all functions/variables, which means
there's an O(n²) in the number of functions. With larger C++ projects easily
having 50k+ functions in a compilation unit, this causes significant slowdown.

Mostly, it seems to be completely unneccessary; the functions should be in the
same order for both traversals, so one can probably just keep func through the
iteration and do func = func->prev_func each time an appropriate DW_TAG_* is
seen?

-- 
You are receiving this mail because:
You are on the CC list for the bug.