This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
[PATCH] Fix elf-strtab.c performance problem
- From: Jakub Jelinek <jakub at redhat dot com>
- To: binutils at sources dot redhat dot com
- Date: Mon, 17 Dec 2001 19:04:16 +0100
- Subject: [PATCH] Fix elf-strtab.c performance problem
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
Hi!
Alan Modra pointed me during the weekend at a big performance problem in
elf-strtab.c.
The bug was that
c = (unsigned char) e->root.string[e->len - 1];
should have been:
c = (unsigned char) e->root.string[e->len - 2];
(e->len is strlen(string) + 1).
Current code would use hash 0 for all strings, thus the hash table was huge.
Instead of just changing this typo, I rewrote it so that it uses
an array indexed by last string character.
For merge.c, I think it can stay as it is now (there was not this bug which
appeared when I was simplifying merge.c for elf-strtab.c), because it needs
to handle > 1 byte characters too and because the hash comparison function
never compares anything for longer strings than 4 chars, so it is just
inserted into the table.
Ok to commit (bootstrapped, make check shows no regressions)?
2001-12-17 Jakub Jelinek <jakub@redhat.com>
* elf-strtab.c (struct elf_strtab_hash_entry): Add u.next.
(last_eq): Remove.
(_bfd_elf_strtab_finalize): Don't use a hash table for last
character chains, instead use an array.
--- bfd/elf-strtab.c.jj Tue Nov 13 18:25:56 2001
+++ bfd/elf-strtab.c Mon Dec 17 19:21:03 2001
@@ -37,6 +37,7 @@ struct elf_strtab_hash_entry
bfd_size_type index;
/* Entry this is a suffix of (if len is 0). */
struct elf_strtab_hash_entry *suffix;
+ struct elf_strtab_hash_entry *next;
} u;
};
@@ -59,7 +60,6 @@ static struct bfd_hash_entry *elf_strtab
PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
static int cmplengthentry PARAMS ((const PTR, const PTR));
static int last4_eq PARAMS ((const PTR, const PTR));
-static int last_eq PARAMS ((const PTR, const PTR));
/* Routine to create an entry in a section merge hashtab. */
@@ -313,33 +313,6 @@ last4_eq (a, b)
B->root.string, B->len - 5) == 0;
}
-static int
-last_eq (a, b)
- const PTR a;
- const PTR b;
-{
- struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
- struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
-
- if (B->len >= 5)
- /* Longer strings are just pushed into the hash table,
- they'll be used when looking up for very short strings. */
- return 0;
-
- if (memcmp (A->root.string + A->len - 2, B->root.string + B->len - 2, 1)
- != 0)
- /* This was a hashtable collision. */
- return 0;
-
- if (A->len <= B->len)
- /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
- not to be equal by the hash table. */
- return 0;
-
- return memcmp (A->root.string + (A->len - B->len),
- B->root.string, B->len - 2) == 0;
-}
-
/* This function assigns final string table offsets for used strings,
merging strings matching suffixes of longer strings if possible. */
@@ -348,8 +321,9 @@ _bfd_elf_strtab_finalize (tab)
struct elf_strtab_hash *tab;
{
struct elf_strtab_hash_entry **array, **a, **end, *e;
- htab_t lasttab = NULL, last4tab = NULL;
+ htab_t last4tab = NULL;
bfd_size_type size, amt;
+ struct elf_strtab_hash_entry *last[256], *last_ptr[256];
/* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
@@ -364,6 +338,8 @@ _bfd_elf_strtab_finalize (tab)
if (array == NULL)
goto alloc_failure;
+ memset (last, 0, sizeof (last));
+ memset (last_ptr, 0, sizeof (last_ptr));
for (i = 1, a = array; i < tab->size; ++i)
if (tab->array[i]->refcount)
*a++ = tab->array[i];
@@ -375,8 +351,7 @@ _bfd_elf_strtab_finalize (tab)
qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
last4tab = htab_create (size * 4, NULL, last4_eq, NULL);
- lasttab = htab_create (size * 4, NULL, last_eq, NULL);
- if (lasttab == NULL || last4tab == NULL)
+ if (last4tab == NULL)
goto alloc_failure;
/* Now insert the strings into hash tables (strings with last 4 characters
@@ -416,27 +391,38 @@ _bfd_elf_strtab_finalize (tab)
else
*p = (PTR) e;
}
- c = (unsigned char) e->root.string[e->len - 1];
- p = htab_find_slot_with_hash (lasttab, e, c, INSERT);
- if (p == NULL)
- goto alloc_failure;
- if (*p)
+ else
{
- struct elf_strtab_hash_entry *ent;
+ struct elf_strtab_hash_entry *tem;
+
+ c = e->root.string[e->len - 2] & 0xff;
- ent = (struct elf_strtab_hash_entry *) *p;
- e->u.suffix = ent;
- e->len = 0;
+ for (tem = last[c]; tem; tem = tem->u.next)
+ if (tem->len > e->len
+ && memcmp (tem->root.string + (tem->len - e->len),
+ e->root.string, e->len - 1) == 0)
+ break;
+ if (tem)
+ {
+ e->u.suffix = tem;
+ e->len = 0;
+ continue;
+ }
}
+
+ c = e->root.string[e->len - 2] & 0xff;
+ /* Put longest strings first. */
+ if (last_ptr[c] == NULL)
+ last[c] = e;
else
- *p = (PTR) e;
+ last_ptr[c]->u.next = e;
+ last_ptr[c] = e;
+ e->u.next = NULL;
}
alloc_failure:
if (array)
free (array);
- if (lasttab)
- htab_delete (lasttab);
if (last4tab)
htab_delete (last4tab);
Jakub