Re: [PATCH] Add a trie to map quickly from address range to compilation unit.

["Steinar H. Gunderson" <sesse@google.com>]

On Fri, Mar 25, 2022 at 10:00:29AM +1030, Alan Modra wrote:
> This would be reverting commit 240d6706c6a2.  In
> https://sourceware.org/bugzilla/show_bug.cgi?id=15935#c3 I came to the
> conclusion that the pr15935 testcase had bogus debug info and closed
> the bug as invalid.  The reporter apparently opened another bug,
> https://sourceware.org/bugzilla/show_bug.cgi?id=15994 a month later
> that Nick fixed by making _bfd_dwarf2_find_nearest_line do extra work.
> Which of course is unnecessary with good debug info, but in many cases
> we try to make binutils give the best result even with bad input.  I
> don't know the details beyond that.  It might have been that the
> compiler producing the bad debug info was one supported by RedHat.

Thanks for going through the history here. Note that my patch changes
the equation somewhat; as long as the debug info has been parsed for the
CU (I understand that this is done somewhat incrementally?), the cost of
looking through all CUs instead of stopping at the first one is nearly zero.
Generally, we pay a cost proportional to the number of ranges that
overlap with the given 256-byte region which should be very pretty few
in a well-behaved binary, and not a lot even in a really bad one.
(Well, that's not strictly true; if the number of such ranges is fewer
than 8, we could be testing up to 8 ranges. But it's still cheap.)

But of course, if we want to keep parsing debug info from new CUs,
that has a definite cost. But that cost is per-CU, not per lookup,
so if you're looking up lots of addresses, it's “only” startup cost.
Whether this matters depends on the use case, of course.

In any case, I think the decision here should be more clearly
communicated in the source :-) The existing comment saying that we keep
looking is very useful, but the decision to _not_ keep looking into
not-yet-parsed CUs (in some cases only!) is less clearly articulated.

/* Steinar */