Re: PATCH: Use a hash table for 26X linker speedup

[Nick Clifton <nickc at redhat dot com>]

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;
  }