From: Ben Elliston <bje@au1.ibm.com>
To: binutils@sources.redhat.com
Subject: PATCH: speed up ar(1)
Date: Mon, 07 Mar 2005 23:47:00 -0000 [thread overview]
Message-ID: <422CE744.7070409@au.ibm.com> (raw)
[-- 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 --]
next reply other threads:[~2005-03-07 23:47 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-03-07 23:47 Ben Elliston [this message]
2005-03-09 12:41 ` Nick Clifton
2005-03-10 0:05 ` Ben Elliston
2005-03-14 1:06 ` Steven Bosscher
2005-03-14 1:32 ` H. J. Lu
2005-03-14 1:38 ` Alan Modra
2005-03-14 9:40 ` Nick Clifton
2005-03-14 16:24 ` Daniel Jacobowitz
2005-03-10 21:31 ` Mark Kettenis
2005-03-10 22:40 ` Ben Elliston
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=422CE744.7070409@au.ibm.com \
--to=bje@au1.ibm.com \
--cc=binutils@sources.redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).