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

[Paul Brook <paul at codesourcery dot com>]

> 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.

It's still quite slow with this patch.  
unrecord_section_with_arm_elf_section_data has the same problem.

The attached patch uses the cache for this as well, and avoids leaving 
last_entry pointing a a free'd object.

Tested with cross to arm-none-eabi.
Ok?

Paul

2005-10-19  Paul Brook  <paul@codesourcery.com>

	* elf32-arm.c (find_arm_elf_section_entry): New function.
	(get_arm_elf_section_data,
	unrecord_section_with_arm_elf_section_data): Use it.

Index: bfd/elf32-arm.c
===================================================================
RCS file: /var/cvsroot/src-cvs/src/bfd/elf32-arm.c,v
retrieving revision 1.58
diff -u -p -r1.58 elf32-arm.c
--- bfd/elf32-arm.c	8 Oct 2005 17:07:15 -0000	1.58
+++ bfd/elf32-arm.c	19 Oct 2005 00:16:11 -0000
@@ -7311,8 +7311,8 @@ record_section_with_arm_elf_section_data
   sections_with_arm_elf_section_data = entry;
 }
 
-static _arm_elf_section_data *
-get_arm_elf_section_data (asection * sec)
+static struct section_list *
+find_arm_elf_section_entry (asection * sec)
 {
   struct section_list * entry;
   static struct section_list * last_entry = NULL;
@@ -7321,27 +7321,37 @@ get_arm_elf_section_data (asection * sec
      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.  */
+  entry = sections_with_arm_elf_section_data;
   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);
-	}
+	entry = last_entry;
+      else if (last_entry->next != NULL
+	       && last_entry->next->sec == sec)
+	entry = last_entry->next;
     }
- 
-  for (entry = sections_with_arm_elf_section_data; entry; entry = entry->next)
+
+  for (; entry; entry = entry->next)
     if (entry->sec == sec)
-      {
-	last_entry = entry;
-	return elf32_arm_section_data (sec);
-      }
+      break;
+
+  if (entry)
+    last_entry = entry->prev;
+
+  return entry;
+}
+
+static _arm_elf_section_data *
+get_arm_elf_section_data (asection * sec)
+{
+  struct section_list * entry;
+
+  entry = find_arm_elf_section_entry (sec);
 
-  return NULL;
+  if (entry)
+    return elf32_arm_section_data (entry->sec);
+  else
+    return NULL;
 }
 
 static void
@@ -7349,18 +7359,18 @@ unrecord_section_with_arm_elf_section_da
 {
   struct section_list * entry;
 
-  for (entry = sections_with_arm_elf_section_data; entry; entry = entry->next)
-    if (entry->sec == sec)
-      {
-	if (entry->prev != NULL)
-	  entry->prev->next = entry->next;
-	if (entry->next != NULL)
-	  entry->next->prev = entry->prev;
-	if (entry == sections_with_arm_elf_section_data)
-	  sections_with_arm_elf_section_data = entry->next;
-	free (entry);
-	break;
-      }
+  entry = find_arm_elf_section_entry (sec);
+
+  if (entry)
+    {
+      if (entry->prev != NULL)
+	entry->prev->next = entry->next;
+      if (entry->next != NULL)
+	entry->next->prev = entry->prev;
+      if (entry == sections_with_arm_elf_section_data)
+	sections_with_arm_elf_section_data = entry->next;
+      free (entry);
+    }
 }
 
 /* Called for each symbol.  Builds a section map based on mapping symbols.