PATCH: Use a hash table for 26X linker speedup
Nick Clifton
nickc@redhat.com
Tue Oct 4 07:23:00 GMT 2005
Hi Paul,
>> * ld-elf/sec64k.exp: Enabled for all ELF targets.
> On an arm-none-eabi cross this test takes about 8 minutes to run on my
> machine. This is about 25 times longer than the whole of the rest of the
> binutils+gas+gdb testsuites put together.
> We should probably figure out what causing this slowness. Until that happens,
> the patch below disable the test on arm targets.
> Ok?
Better I think to find out the cause of the slow down. I did this - it is
the get_arm_elf_section_data() function in elf32-arm.c, which is repeatedly
scanning over a list of ~64K entries trying to match up section
pointers. Since I wrote this function I felt obliged to try to fix it
and I am committing the patch below which does improve things. It is
not the best fix (which would be to use a hash function), but it does
help by noticing that the typical usage is to add sections to the list
in forwards order and then scan for them in backwards order.
Cheers
Nick
bfd/ChangeLog
2005-10-04 Nick Clifton <nickc@redhat.com>
* elf32-arm.c (get_arm_elf_section_data): Cache the last pointer
matched so that the typical case of scanning for the previous
section to last one can be handled quickly.
Index: bfd/elf32-arm.c
===================================================================
RCS file: /cvs/src/src/bfd/elf32-arm.c,v
retrieving revision 1.55
diff -c -3 -p -r1.55 elf32-arm.c
*** bfd/elf32-arm.c 9 Sep 2005 13:10:01 -0000 1.55
--- bfd/elf32-arm.c 4 Oct 2005 07:18:12 -0000
*************** static _arm_elf_section_data *
*** 6563,6572 ****
get_arm_elf_section_data (asection * sec)
{
struct section_list * entry;
for (entry = sections_with_arm_elf_section_data; entry; entry =
entry->next)
if (entry->sec == sec)
! return elf32_arm_section_data (sec);
return NULL;
}
--- 6563,6594 ----
get_arm_elf_section_data (asection * sec)
{
struct section_list * entry;
+ static struct section_list * last_entry = NULL;
+ /* This is a short cut for the typical case where the sections are added
+ to the sections_with_arm_elf_section_data list in forward order and
+ then looked up here in backwards order. This makes a real difference
+ to the ld-srec/sec64k.exp linker test. */
+ if (last_entry != NULL)
+ {
+ if (last_entry->sec == sec)
+ return elf32_arm_section_data (sec);
+
+ if (last_entry->prev != NULL
+ && last_entry->prev->sec == sec)
+ {
+ last_entry = last_entry->prev;
+ return elf32_arm_section_data (sec);
+ }
+ }
+
for (entry = sections_with_arm_elf_section_data; entry; entry =
entry->next)
if (entry->sec == sec)
! {
! last_entry = entry;
! return elf32_arm_section_data (sec);
! }
!
return NULL;
}
More information about the Binutils
mailing list