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

[steinar+sourceware at gunderson dot no]

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

--- Comment #4 from Steinar H. Gunderson <steinar+sourceware at gunderson dot 
no> ---
Thanks for applying!

I'm not sure if I understand what you mean. From what I can see, the reversal
is completely, 100% necessary for this patch to do its job. If not, you'll have
a miss every single time as I understand it.

E.g.: Say you have 1000 functions. When we get to the Nth
DW_TAG_{subprogram,entry_point,inlined_subroutine}, we will want them to find
function 0, 1, 2, 3, 4, etc. respectively in the list (since that's the order
they are read in). But since we only have _previous_ pointers, and
unit->function_table points to the _last_ function, it will start at 999 and
search backwards until it finds 0. There's no way for us to say “OK, last one I
saw was number 500, so let me find the pointer to 501”, because we only have a
pointer to 499. This is why I reverse the list -- so that the pointer goes to
the one we want.

>From what I can see, reversing the list takes us from a 0% hit rate to a 100%
hit rate. I'm not even sure whether lookup_func_by_offset() is needed at all
anymore (it should really never be called after the patch, if I understand
correctly), but I don't know all the logic in the function, so I left it in for
safety.

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