[PATCH] Speed up bfd_dwarf2_find_nearest_line for very big binaries.

["=?big5?b?RG91ZyBLd2FuICjD9q62vHcp?=" <dougkwan at google dot com>]

Hi,

    I have implemented an arange set based on the splay tree in
libiberty.  The arange set replaces some uses of the singly linked
list of aranges in dwarf2.c, which is extremely inefficient for big
binaries.  To test the arange set, I also added a testsuite directory
inside bfd and put a test program there.  The test is runnable using
make check, just like tests in other component of binutils.  The test
program uses targeted and randomized tests to exercise various parts
of the arange test implementation.

   This patch brings down the run time of "nm -l -C -S -p" of a 230M+
binaries from over 5 minutes to less than 3 minutes on my machine and
it does not change the output of nm. I also ran a profiled run and
found that now about 74% of time is inside elf_find_function, possibly
inside a loop.  So further speed up is possible but I currently do not
have time to work on that.

   Could someone please review and apply this patch? Thanks.

-Doug

Attachment: ChangeList-arange-set.txt
Description: Text document

Attachment: diffs-arange-set.txt
Description: Text document