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

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Steven Bosscher-3
Hi,

Can anyone tell what happened to this linker speedup patch?
http://sources.redhat.com/ml/binutils/2005-05/msg00720.html

Gr.
Steven

Reply | Threaded
Open this post in threaded view
|

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

Alan Modra
On Thu, Sep 29, 2005 at 04:23:05PM +0200, Steven Bosscher wrote:
> Can anyone tell what happened to this linker speedup patch?
> http://sources.redhat.com/ml/binutils/2005-05/msg00720.html

I looked at rearranging the orphan code so that this wouldn't be
necessary, and found I needed to pull apart half the linker.  So I left
that job for a rainy day.  Since I haven't provided a more elegant
solution, I suppose HJ's patch ought to go in.

--
Alan Modra
IBM OzLabs - Linux Technology Centre
Reply | Threaded
Open this post in threaded view
|

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

Nick Clifton
Hi H.J.

   Just to make this explicit:

 > Alan Modra wrote:
>>Can anyone tell what happened to this linker speedup patch?
>>http://sources.redhat.com/ml/binutils/2005-05/msg00720.html
>
> I looked at rearranging the orphan code so that this wouldn't be
> necessary, and found I needed to pull apart half the linker.  So I left
> that job for a rainy day.  Since I haven't provided a more elegant
> solution, I suppose HJ's patch ought to go in.

ld/
2005-05-01  H.J. Lu  <[hidden email]>

        * ldlang.c (output_statement_hash_entry): New type.
        (output_statement_table): New variable for hash table.
        (output_statement_newfunc): New function.
        (output_statement_table_init): Likewise.
        (output_statement_table_free): Likewise.
        (lang_init): Call output_statement_table_init.
        (lang_finish): Renamed to ...
        (lang_end): This.
        (lang_process): Updated.
        (lang_finish): New function.
        (lang_output_section_find_1): Use hash table.
        (lang_output_section_statement_lookup_1): Likewise.

        * ldlang.h (lang_finish): New.

        * ldmain.c (main): Call lang_finish.

ld/testsuite/
2005-05-01  H.J. Lu  <[hidden email]>

        * ld-elf/sec64k.exp: Enabled for all ELF targets.

Approved - please apply.

Cheers
   Nick

Reply | Threaded
Open this post in threaded view
|

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

Paul Brook
> ld/testsuite/
> 2005-05-01  H.J. Lu  <[hidden email]>
>
> * 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.

Tests run on a 2GHz amd64, ie. not a slow machine.

A native i386 linker completes the test in a more reasonable time (~20
seconds), so this looks like an arm specific problem.

We should probably figure out what causing this slowness. Until that happens,
the patch below disable the test on arm targets.
Ok?

I'll file a bug in bugzilla to remind me/us that there's something slow in the
arm linker.

Paul

2005-10-01  Paul Brook  <[hidden email]>

        * ld-elf/sec64k.exp: Skip test on arm targets (too slow).

patch.arm_sec64k (704 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Nick Clifton
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  <[hidden email]>

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

Reply | Threaded
Open this post in threaded view
|

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

Paul Brook
> bfd/ChangeLog
> 2005-10-04  Nick Clifton  <[hidden email]>
>
> * 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  <[hidden email]>

        * 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.
Reply | Threaded
Open this post in threaded view
|

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

Nick Clifton
Hi Paul,

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

Good point.

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

Also a very good point.

I have applied your patch together with an extra comment describing why
we set last_found to entry->prev, since I felt that it was not entirely
obvious.

Cheers
   Nick

> 2005-10-19  Paul Brook  <[hidden email]>
>
> * elf32-arm.c (find_arm_elf_section_entry): New function.
> (get_arm_elf_section_data,
> unrecord_section_with_arm_elf_section_data): Use it.