PATCH: speed up ar(1)

PATCH: speed up ar(1)

[Ben Elliston]

[-- Attachment #1: Type: text/plain, Size: 4411 bytes --]

The following patch alters the ar cache representation from a singly linked list to a
hash table using the hashtab implementation from libiberty.  When archiving files
with thousands of archive members (eg. libjava), this patch results in a 15-25%
performance improvement.

Tested with an --enable-targets=all build, make check-binutils and a byte-wise
comparison of the libjava libraries built with and without a patched ar.

Okay to commit?

Index: archive.c
===================================================================
RCS file: /home/bje/src-cvs/src/bfd/archive.c,v
retrieving revision 1.34
diff -u -r1.34 archive.c
--- archive.c	3 Mar 2005 11:40:56 -0000	1.34
+++ archive.c	7 Mar 2005 22:48:34 -0000
@@ -133,6 +133,7 @@
  #include "aout/ar.h"
  #include "aout/ranlib.h"
  #include "safe-ctype.h"
+#include "hashtab.h"

  #ifndef errno
  extern int errno;
@@ -146,8 +147,7 @@
     to the front of the contents!  */
  struct ar_cache {
    file_ptr ptr;
-  bfd *arelt;
-  struct ar_cache *next;
+  bfd *arbfd;
  };

  #define ar_padchar(abfd) ((abfd)->xvec->ar_pad_char)
@@ -247,14 +247,36 @@
  bfd *
  _bfd_look_for_bfd_in_cache (bfd *arch_bfd, file_ptr filepos)
  {
-  struct ar_cache *current;
+  struct ar_cache m;
+  m.ptr = filepos;

-  for (current = bfd_ardata (arch_bfd)->cache; current != NULL;
-       current = current->next)
-    if (current->ptr == filepos)
-      return current->arelt;
+  htab_t hash_table = bfd_ardata (arch_bfd)->cache;
+  if (hash_table)
+    {
+      struct ar_cache *entry = (struct ar_cache *) htab_find (hash_table, &m);
+      if (!entry)
+	return NULL;
+      else
+	return entry->arbfd;
+    }
+  else
+    return NULL;
+}
+
+static hashval_t
+hash_file_ptr (const PTR p)
+{
+  return (hashval_t) (((struct ar_cache *) p)->ptr);
+}

-  return NULL;
+/* Returns non-zero if P1 and P2 are equal.  */
+
+static int
+eq_file_ptr (const PTR p1, const PTR p2)
+{
+  struct ar_cache *arc1 = (struct ar_cache *) p1;
+  struct ar_cache *arc2 = (struct ar_cache *) p2;
+  return arc1->ptr == arc2->ptr;
  }

  /* Kind of stupid to call cons for each one, but we don't do too many.  */
@@ -262,25 +284,24 @@
  bfd_boolean
  _bfd_add_bfd_to_archive_cache (bfd *arch_bfd, file_ptr filepos, bfd *new_elt)
  {
-  bfd_size_type amt = sizeof (struct ar_cache);
-
-  struct ar_cache *new_cache = bfd_zalloc (arch_bfd, amt);
-  if (new_cache == NULL)
-    return FALSE;
+  struct ar_cache *cache;
+  htab_t hash_table = bfd_ardata (arch_bfd)->cache;

-  new_cache->ptr = filepos;
-  new_cache->arelt = new_elt;
-  new_cache->next = NULL;
-  if (bfd_ardata (arch_bfd)->cache == NULL)
-    bfd_ardata (arch_bfd)->cache = new_cache;
-  else
+  /* If the hash table hasn't been created, create it.  */
+  if (hash_table == NULL)
      {
-      struct ar_cache *current = bfd_ardata (arch_bfd)->cache;
-
-      while (current->next != NULL)
-	current = current->next;
-      current->next = new_cache;
+      hash_table = htab_create_alloc (16, hash_file_ptr, eq_file_ptr,
+				      NULL, calloc, free);
+      if (hash_table == NULL)
+	return FALSE;
+      bfd_ardata (arch_bfd)->cache = hash_table;
      }
+
+  /* Insert new_elt into the hash table by filepos.  */
+  cache = bfd_zalloc (arch_bfd, sizeof (struct ar_cache));
+  cache->ptr = filepos;
+  cache->arbfd = new_elt;
+  *htab_find_slot (hash_table, (const void *) cache, INSERT) = cache;

    return TRUE;
  }
Index: libbfd-in.h
===================================================================
RCS file: /home/bje/src-cvs/src/bfd/libbfd-in.h,v
retrieving revision 1.46
diff -u -r1.46 libbfd-in.h
--- libbfd-in.h	20 Feb 2005 14:59:07 -0000	1.46
+++ libbfd-in.h	7 Mar 2005 22:48:34 -0000
@@ -23,6 +23,8 @@
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

+#include "hashtab.h"
+
  /* Align an address upward to a boundary, expressed as a number of bytes.
     E.g. align to an 8-byte boundary with argument of 8.  Take care never
     to wrap around if the address is within boundary-1 of the end of the
@@ -57,7 +59,7 @@
  struct artdata {
    file_ptr first_file_filepos;
    /* Speed up searching the armap */
-  struct ar_cache *cache;
+  htab_t cache;
    bfd *archive_head;		/* Only interesting in output routines */
    carsym *symdefs;		/* the symdef entries */
    symindex symdef_count;	/* how many there are */

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: PATCH: speed up ar(1)

[Nick Clifton]

Hi Ben,

> The following patch alters the ar cache representation from a singly linked list to a
> hash table using the hashtab implementation from libiberty.  When archiving files
> with thousands of archive members (eg. libjava), this patch results in a 15-25%
> performance improvement.
> 
> Tested with an --enable-targets=all build, make check-binutils and a byte-wise
> comparison of the libjava libraries built with and without a patched ar.
> 
> Okay to commit?

[Tut tut - no ChangeLog entry...]

Approved for the mainline, but not the 2.16 branch.

Cheers
   Nick

Re: PATCH: speed up ar(1)

[Ben Elliston]

Hi Nick

> [Tut tut - no ChangeLog entry...]

I was posting the patch to test the water.  I wasn't sure how well it was going to be 
received, so I didn't bother to write a ChangeLog entry up front.  I'll write one, of 
course!

> Approved for the mainline, but not the 2.16 branch.

Yep, agreed.  Cheers,

Ben

Re: PATCH: speed up ar(1)

[Mark Kettenis]

   Date: Tue, 08 Mar 2005 10:44:04 +1100
   From: Ben Elliston <bje@au1.ibm.com>

   The following patch alters the ar cache representation from a
   singly linked list to a hash table using the hashtab implementation
   from libiberty.  When archiving files with thousands of archive
   members (eg. libjava), this patch results in a 15-25% performance
   improvement.

   Tested with an --enable-targets=all build, make check-binutils and
   a byte-wise comparison of the libjava libraries built with and
   without a patched ar.

But with a compiler that's far too modern for your own good ;-).

   Okay to commit?

Not really; this isn't proper ISO C90...

   Index: archive.c
   ===================================================================
   RCS file: /home/bje/src-cvs/src/bfd/archive.c,v
   retrieving revision 1.34
   diff -u -r1.34 archive.c
   --- archive.c	3 Mar 2005 11:40:56 -0000	1.34
   +++ archive.c	7 Mar 2005 22:48:34 -0000
   @@ -247,14 +247,36 @@
     bfd *
     _bfd_look_for_bfd_in_cache (bfd *arch_bfd, file_ptr filepos)
     {
   -  struct ar_cache *current;
   +  struct ar_cache m;
   +  m.ptr = filepos;

   -  for (current = bfd_ardata (arch_bfd)->cache; current != NULL;
   -       current = current->next)
   -    if (current->ptr == filepos)
   -      return current->arelt;
   +  htab_t hash_table = bfd_ardata (arch_bfd)->cache;

But since it already went in, I committed the attached obvious patch.

Take care,

Mark


Index: ChangeLog
from  Mark Kettenis  <kettenis@gnu.org>

	* archive.c (_bfd_look_for_bfd_in_cache): Move declaration of
	has_table to the start of the function.

Index: archive.c
===================================================================
RCS file: /cvs/src/src/bfd/archive.c,v
retrieving revision 1.35
diff -u -p -r1.35 archive.c
--- archive.c 10 Mar 2005 00:29:35 -0000 1.35
+++ archive.c 10 Mar 2005 21:25:21 -0000
@@ -247,10 +247,10 @@ bfd_set_archive_head (bfd *output_archiv
 bfd *
 _bfd_look_for_bfd_in_cache (bfd *arch_bfd, file_ptr filepos)
 {
+  htab_t hash_table = bfd_ardata (arch_bfd)->cache;
   struct ar_cache m;
   m.ptr = filepos;
 
-  htab_t hash_table = bfd_ardata (arch_bfd)->cache;
   if (hash_table)
     {
       struct ar_cache *entry = (struct ar_cache *) htab_find (hash_table, &m);

Re: PATCH: speed up ar(1)

[Ben Elliston]

[-- Attachment #1: Type: text/plain, Size: 107 bytes --]

> But with a compiler that's far too modern for your own good ;-).

Bah, thanks for catching this :-(

Ben

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: PATCH: speed up ar(1)

[Steven Bosscher]

On Wednesday 09 March 2005 13:53, Nick Clifton wrote:
> Hi Ben,
>
> > The following patch alters the ar cache representation from a singly
> > linked list to a hash table using the hashtab implementation from
> > libiberty.  When archiving files with thousands of archive members (eg.
> > libjava), this patch results in a 15-25% performance improvement.
> >
> > Tested with an --enable-targets=all build, make check-binutils and a
> > byte-wise comparison of the libjava libraries built with and without a
> > patched ar.
> >
> > Okay to commit?
>
> [Tut tut - no ChangeLog entry...]
>
> Approved for the mainline, but not the 2.16 branch.

Ouch, that's a shame.

I was all cheeded up for the day when I saw this patch and its
effect on ar times for libjava (Ben was my hero  - he does that
sometimes).  As a GCC hacker, I have to build libjava quite
often, and ar time is actually a serious problem for this huge
PITA library.
So the sooner I have a "production" binutils with this patch,
the better ;-)  Is there really no chance that the patch can
go into 2.16?

Gr.
Steven

Re: PATCH: speed up ar(1)

[H. J. Lu]

On Mon, Mar 14, 2005 at 02:05:47AM +0100, Steven Bosscher wrote:
> 
> I was all cheeded up for the day when I saw this patch and its
> effect on ar times for libjava (Ben was my hero  - he does that
> sometimes).  As a GCC hacker, I have to build libjava quite
> often, and ar time is actually a serious problem for this huge
> PITA library.
> So the sooner I have a "production" binutils with this patch,
> the better ;-)  Is there really no chance that the patch can
> go into 2.16?
> 

FWIW, I am planning to make a Linux binutils release from the mainline
within 2 weeks if it is stable enough.


H.J.
next 

Re: PATCH: speed up ar(1)

[Alan Modra]

On Mon, Mar 14, 2005 at 02:05:47AM +0100, Steven Bosscher wrote:
> As a GCC hacker, I have to build libjava quite
> often, and ar time is actually a serious problem for this huge
> PITA library.

Are you sure it's really ar?  libtool takes a lot of time too.

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Re: PATCH: speed up ar(1)

[Nick Clifton]

Hi Steven,

>>Approved for the mainline, but not the 2.16 branch.

> Ouch, that's a shame.

You can try to persuade Daniel that including it in the branch would be 
a good idea, but I doubt if he would agree.  The problem is that the 
patch is too new and has the potential to introduce sublte new bugs 
which are not immediealtey obvious from reviewing the code.  I would 
rather that the 2.16 branch produce a working-but-slow ar than a 
fast-but-broken one.

Cheers
   Nick

Re: PATCH: speed up ar(1)

[Daniel Jacobowitz]

On Mon, Mar 14, 2005 at 09:53:14AM +0000, Nick Clifton wrote:
> Hi Steven,
> 
> >>Approved for the mainline, but not the 2.16 branch.
> 
> >Ouch, that's a shame.
> 
> You can try to persuade Daniel that including it in the branch would be 
> a good idea, but I doubt if he would agree.  The problem is that the 
> patch is too new and has the potential to introduce sublte new bugs 
> which are not immediealtey obvious from reviewing the code.  I would 
> rather that the 2.16 branch produce a working-but-slow ar than a 
> fast-but-broken one.

I am currently inclined to migrate it to 2.16 if no one has reported
problems with it in another week or two.  A lot of GCC developers use
binutils HEAD; I expect any problems in this area will turn up.

-- 
Daniel Jacobowitz
CodeSourcery, LLC