This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: dynsym/dynstr sort speedup - patch ...
- From: michael meeks <michael dot meeks at novell dot com>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: binutils at sourceware dot org, Michael Matz <matz at suse dot de>
- Date: Thu, 22 Dec 2005 11:58:50 +0000
- Subject: Re: dynsym/dynstr sort speedup - patch ...
- References: <1135251851.6012.61.camel@linux.site>
- Reply-to: michael dot meeks at novell dot com
Apologies; patch attached.
--
michael.meeks@novell.com <><, Pseudo Engineer, itinerant idiot
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf-bfd.h binutils.current/bfd/elf-bfd.h
--- binutils-2.16.91.0.4/bfd/elf-bfd.h 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elf-bfd.h 2005-12-22 10:42:56.000000000 +0000
@@ -340,6 +340,10 @@
{
struct bfd_link_hash_table root;
+ /* Symbol sort order for final traversal at output */
+ unsigned int sorted_size;
+ struct elf_link_hash_entry **sorted;
+
/* Whether we have created the special dynamic sections required
when linking against or generating a shared object. */
bfd_boolean dynamic_sections_created;
@@ -418,11 +422,16 @@
/* Traverse an ELF linker hash table. */
#define elf_link_hash_traverse(table, func, info) \
- (bfd_link_hash_traverse \
- (&(table)->root, \
- (bfd_boolean (*) (struct bfd_link_hash_entry *, void *)) (func), \
+ (_bfd_elf_link_hash_traverse \
+ ((table), \
+ (bfd_boolean (*) (struct elf_link_hash_entry *, void *)) (func), \
(info)))
+void _bfd_elf_link_hash_traverse
+ (struct elf_link_hash_table *table,
+ bfd_boolean (*func) (struct elf_link_hash_entry *, void *),
+ void *info);
+
/* Get the ELF linker hash table from a link_info structure. */
#define elf_hash_table(p) ((struct elf_link_hash_table *) ((p)->hash))
@@ -1593,7 +1602,7 @@
extern bfd_boolean _bfd_elf_strtab_emit
(bfd *, struct elf_strtab_hash *);
extern void _bfd_elf_strtab_finalize
- (struct elf_strtab_hash *);
+ (struct elf_strtab_hash *, size_t);
extern bfd_boolean _bfd_elf_discard_section_eh_frame
(bfd *, struct bfd_link_info *, asection *,
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf.c binutils.current/bfd/elf.c
--- binutils-2.16.91.0.4/bfd/elf.c 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elf.c 2005-12-22 10:42:56.000000000 +0000
@@ -1560,6 +1560,8 @@
table->tls_size = 0;
table->loaded = NULL;
table->is_relocatable_executable = FALSE;
+ table->sorted = NULL;
+ table->sorted_size = 0;
ret = _bfd_link_hash_table_init (&table->root, abfd, newfunc);
table->root.type = bfd_link_elf_hash_table;
@@ -2983,7 +2985,7 @@
_bfd_elf_strtab_addref (elf_shstrtab (abfd), t->strtab_hdr.sh_name);
}
- _bfd_elf_strtab_finalize (elf_shstrtab (abfd));
+ _bfd_elf_strtab_finalize (elf_shstrtab (abfd), 0);
t->shstrtab_hdr.sh_size = _bfd_elf_strtab_size (elf_shstrtab (abfd));
elf_numsections (abfd) = section_number;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elflink.c binutils.current/bfd/elflink.c
--- binutils-2.16.91.0.4/bfd/elflink.c 2005-12-22 10:42:52.000000000 +0000
+++ binutils.current/bfd/elflink.c 2005-12-22 10:42:56.000000000 +0000
@@ -3007,7 +3007,8 @@
const struct elf_backend_data *bed;
bfd_byte *extdyn;
- _bfd_elf_strtab_finalize (dynstr);
+ _bfd_elf_strtab_finalize (dynstr,
+ elf_hash_table (info)->bucketcount);
size = _bfd_elf_strtab_size (dynstr);
bed = get_elf_backend_data (dynobj);
@@ -4920,6 +4922,125 @@
return best_size;
}
+void _bfd_elf_link_hash_traverse
+ (struct elf_link_hash_table *table,
+ bfd_boolean (*func) (struct elf_link_hash_entry *, void *),
+ void *info)
+{
+ if (!table->sorted)
+ bfd_link_hash_traverse \
+ (&(table)->root, \
+ (bfd_boolean (*) (struct bfd_link_hash_entry *, void *)) (func), \
+ (info));
+ else
+ {
+ unsigned int i;
+ for (i = 0; i < table->sorted_size; i++)
+ {
+ if (! func (table->sorted[i], info))
+ return;
+ }
+ }
+}
+
+/* Where is the qsort closure ? */
+static size_t give_me_a_bucket_count = 0;
+
+/* Sort by elf hash value % buckets */
+static int
+elf_sort_dynsym_hash (const void *arg1, const void *arg2)
+{
+ size_t h1_bucket, h2_bucket;
+ const struct elf_link_hash_entry *h1;
+ const struct elf_link_hash_entry *h2;
+
+ h1 = *(const struct elf_link_hash_entry **) arg1;
+ h2 = *(const struct elf_link_hash_entry **) arg2;
+
+ h1_bucket = h1->u.elf_hash_value % give_me_a_bucket_count;
+ h2_bucket = h2->u.elf_hash_value % give_me_a_bucket_count;
+
+ if (h1_bucket > h2_bucket)
+ return 1;
+ if (h1_bucket < h2_bucket)
+ return -1;
+
+ return 0;
+}
+
+struct elf_dynsym_sort_info
+{
+ bfd_boolean do_dynsym;
+ unsigned int alloc_size;
+ unsigned int sorted_size;
+ struct elf_link_hash_entry **sorted_syms;
+};
+
+/* collect sym entries into an array for later sorting */
+static bfd_boolean
+elf_sort_collect_dynsyms (struct elf_link_hash_entry *h, void *data)
+{
+ struct elf_dynsym_sort_info *sinfo = data;
+
+ if ((sinfo->do_dynsym && h->dynindx < 0) ||
+ (!sinfo->do_dynsym && h->dynindx >= 0))
+ return TRUE;
+
+ if (sinfo->sorted_size >= sinfo->alloc_size)
+ {
+ sinfo->alloc_size *= 2;
+ /* FIXME: need to free this data too ... */
+ sinfo->sorted_syms = bfd_realloc (sinfo->sorted_syms,
+ sizeof (struct elf_link_hash_entry *) *
+ sinfo->alloc_size);
+ }
+ sinfo->sorted_syms [sinfo->sorted_size++] = h;
+
+ return TRUE;
+}
+
+/*
+ * Sort the exported elf symbols by elf_hash % bucketcount to
+ * improve run-time linker cache behavior. Subsequent
+ * elf_link_hash_traverse calls will reflect this new order.
+ */
+static bfd_boolean
+_bfd_elf_sort_dynsyms (struct bfd_link_info *info)
+{
+ struct elf_dynsym_sort_info sinfo;
+
+ sinfo.alloc_size = 8;
+ sinfo.sorted_syms = bfd_malloc (sizeof (struct elf_link_hash_entry *) *
+ sinfo.alloc_size);
+ if (!sinfo.sorted_syms)
+ return FALSE;
+
+ sinfo.sorted_size = 0;
+
+ /* append dynsyms for sorting */
+ sinfo.do_dynsym = TRUE;
+ elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
+
+ /* sort them ... */
+ if (getenv ("DO_SORT_SYMS")) {
+ fprintf (stderr, "Sorting dynsym\n");
+ give_me_a_bucket_count = elf_hash_table (info)->bucketcount;
+ qsort (sinfo.sorted_syms, sinfo.sorted_size,
+ sizeof (struct elf_link_hash_entry *),
+ elf_sort_dynsym_hash);
+ }
+
+ /* append everything else */
+ sinfo.do_dynsym = FALSE;
+ elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
+
+ /* transfer to the elf hash: FIXME - leaks ... */
+ elf_hash_table (info)->sorted = sinfo.sorted_syms;
+ elf_hash_table (info)->sorted_size = sinfo.sorted_size;
+
+ return TRUE;
+}
+
/* Set up the sizes and contents of the ELF dynamic sections. This is
called by the ELF linker emulation before_allocation routine. We
must set the sizes of the sections before the linker sets the
@@ -5686,6 +5807,7 @@
section symbol for each output section, which come first.
Next come all of the back-end allocated local dynamic syms,
followed by the rest of the global symbols. */
+ /* To sort these optimally we need the correct bucketcount */
dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,
§ion_sym_count);
@@ -5756,6 +5878,15 @@
for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)
if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))
return FALSE;
+
+ /* Sort .dynsym to accelerate runtime linking */
+ { /* FIXME - make this conditional (?) */
+ if (!_bfd_elf_sort_dynsyms (info))
+ return FALSE;
+ /* reflect the new sorting order */
+ _bfd_elf_link_renumber_dynsyms (output_bfd, info,
+ §ion_sym_count);
+ }
}
return TRUE;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elflink.c~ binutils.current/bfd/elflink.c~
--- binutils-2.16.91.0.4/bfd/elflink.c~ 2005-12-07 11:20:22.000000000 +0000
+++ binutils.current/bfd/elflink.c~ 2005-12-22 09:26:41.000000000 +0000
@@ -3022,7 +3022,8 @@
const struct elf_backend_data *bed;
bfd_byte *extdyn;
- _bfd_elf_strtab_finalize (dynstr);
+ _bfd_elf_strtab_finalize (dynstr,
+ elf_hash_table (info)->bucketcount);
size = _bfd_elf_strtab_size (dynstr);
bed = get_elf_backend_data (dynobj);
@@ -4983,6 +4986,133 @@
return best_size;
}
+void _bfd_elf_link_hash_traverse
+ (struct elf_link_hash_table *table,
+ bfd_boolean (*func) (struct elf_link_hash_entry *, void *),
+ void *info)
+{
+ if (!table->sorted)
+ bfd_link_hash_traverse \
+ (&(table)->root, \
+ (bfd_boolean (*) (struct bfd_link_hash_entry *, void *)) (func), \
+ (info));
+ else
+ {
+ int i;
+ for (i = 0; i < table->sorted_size; i++)
+ {
+ if (! func (table->sorted[i], info))
+ return;
+ }
+ }
+}
+
+/* Where is the qsort closure ? */
+static size_t give_me_a_bucket_count = 0;
+
+/* Sort by elf hash value % buckets */
+static int
+elf_sort_dynsym_hash (const void *arg1, const void *arg2)
+{
+ size_t h1_bucket, h2_bucket;
+ const struct elf_link_hash_entry *h1;
+ const struct elf_link_hash_entry *h2;
+
+ h1 = *(const struct elf_link_hash_entry **) arg1;
+ h2 = *(const struct elf_link_hash_entry **) arg2;
+
+ h1_bucket = h1->u.elf_hash_value % give_me_a_bucket_count;
+ h2_bucket = h2->u.elf_hash_value % give_me_a_bucket_count;
+
+ /* fprintf (stderr, "Sort: '%s'(0x%x) <> '%s'(0x%x) (%d)\n",
+ h1->root.root.string, h1_bucket,
+ h2->root.root.string, h2_bucket,
+ give_me_a_bucket_count); */
+
+ /* Hack to test with objdump */
+ /* return strcmp (h1->root.root.string, h2->root.root.string); */
+
+ if (h1_bucket > h2_bucket)
+ return 1;
+ if (h1_bucket < h2_bucket)
+ return -1;
+
+ return 0;
+}
+
+struct elf_dynsym_sort_info
+{
+ bfd_boolean do_dynsym;
+ unsigned int alloc_size;
+ unsigned int sorted_size;
+ struct elf_link_hash_entry **sorted_syms;
+};
+
+/* collect sym entries into an array for later sorting */
+static bfd_boolean
+elf_sort_collect_dynsyms (struct elf_link_hash_entry *h, void *data)
+{
+ struct elf_dynsym_sort_info *sinfo = data;
+
+ if ((sinfo->do_dynsym && h->dynindx < 0) ||
+ (!sinfo->do_dynsym && h->dynindx >= 0))
+ return TRUE;
+
+ if (sinfo->sorted_size >= sinfo->alloc_size)
+ {
+ sinfo->alloc_size *= 2;
+ /* FIXME: need to free this data too ... */
+ sinfo->sorted_syms = bfd_realloc (sinfo->sorted_syms,
+ sizeof (struct elf_link_hash_entry *) *
+ sinfo->alloc_size);
+ }
+ sinfo->sorted_syms [sinfo->sorted_size++] = h;
+
+ return TRUE;
+}
+
+/*
+ * Sort the exported elf symbols by elf_hash % bucketcount to
+ * improve run-time linker cache behavior. Subsequent
+ * elf_link_hash_traverse calls will reflect this new order.
+ */
+static bfd_boolean
+_bfd_elf_sort_dynsyms (struct bfd_link_info *info)
+{
+ struct elf_dynsym_sort_info sinfo;
+
+ sinfo.alloc_size = 8;
+ sinfo.sorted_syms = bfd_malloc (sizeof (struct elf_link_hash_entry *) *
+ sinfo.alloc_size);
+ if (!sinfo.sorted_syms)
+ return FALSE;
+
+ sinfo.sorted_size = 0;
+
+ /* append dynsyms for sorting */
+ sinfo.do_dynsym = TRUE;
+ elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
+
+ /* sort them ... */
+ if (getenv ("DO_SORT_SYMS")) {
+ fprintf (stderr, "sort dynsym\n");
+ give_me_a_bucket_count = elf_hash_table (info)->bucketcount;
+ qsort (sinfo.sorted_syms, sinfo.sorted_size,
+ sizeof (struct elf_link_hash_entry *),
+ elf_sort_dynsym_hash);
+ }
+
+ /* append everything else */
+ sinfo.do_dynsym = FALSE;
+ elf_link_hash_traverse (elf_hash_table (info), elf_sort_collect_dynsyms, &sinfo);
+
+ /* transfer to the elf hash: FIXME - leaks ... */
+ elf_hash_table (info)->sorted = sinfo.sorted_syms;
+ elf_hash_table (info)->sorted_size = sinfo.sorted_size;
+
+ return TRUE;
+}
+
/* Set up the sizes and contents of the ELF dynamic sections. This is
called by the ELF linker emulation before_allocation routine. We
must set the sizes of the sections before the linker sets the
@@ -5749,6 +5880,7 @@
section symbol for each output section, which come first.
Next come all of the back-end allocated local dynamic syms,
followed by the rest of the global symbols. */
+ /* To sort these optimally we need the correct bucketcount */
dynsymcount = _bfd_elf_link_renumber_dynsyms (output_bfd, info,
§ion_sym_count);
@@ -5837,6 +5969,16 @@
for (dtagcount = 0; dtagcount <= info->spare_dynamic_tags; ++dtagcount)
if (!_bfd_elf_add_dynamic_entry (info, DT_NULL, 0))
return FALSE;
+
+
+ /* Sort the elf symbols to accelerate linking */
+ { /* HACK - FIXME - make this conditional (?) */
+ if (!_bfd_elf_sort_dynsyms (info))
+ return FALSE;
+ /* reflect the new sorting order */
+ _bfd_elf_link_renumber_dynsyms (output_bfd, info);
+ }
+
}
return TRUE;
diff -u -r -x texis -x Makeconfig -x version.h -x '*.o' -x '*.1' -x 'Makefile*' -x 'config*' -x libtool -x '*.info' -x '*.tex' binutils-2.16.91.0.4/bfd/elf-strtab.c binutils.current/bfd/elf-strtab.c
--- binutils-2.16.91.0.4/bfd/elf-strtab.c 2005-05-10 23:46:41.000000000 +0100
+++ binutils.current/bfd/elf-strtab.c 2005-12-22 10:40:32.000000000 +0000
@@ -39,6 +39,7 @@
/* Entry this is a suffix of (if len < 0). */
struct elf_strtab_hash_entry *suffix;
} u;
+ long elf_hash_value;
};
/* The strtab hash table. */
@@ -54,6 +55,8 @@
bfd_size_type sec_size;
/* Array of pointers to strtab entries. */
struct elf_strtab_hash_entry **array;
+ /* Array of pointers to strtab entries. */
+ struct elf_strtab_hash_entry **array_sorted;
};
/* Routine to create an entry in a section merge hashtab. */
@@ -117,6 +120,7 @@
}
table->array[0] = NULL;
+ table->array_sorted = NULL;
return table;
}
@@ -128,6 +132,8 @@
{
bfd_hash_table_free (&tab->table);
free (tab->array);
+ if (tab->array_sorted)
+ free (tab->array_sorted);
free (tab);
}
@@ -170,6 +176,12 @@
entry->u.index = tab->size++;
tab->array[entry->u.index] = entry;
+
+ {
+ if (strrchr (str, ELF_VER_CHR))
+ fprintf (stderr, "FIXME: Invalid hash generated for '%s'\n", str);
+ entry->elf_hash_value = bfd_elf_hash (str);
+ }
}
return entry->u.index;
}
@@ -229,6 +241,12 @@
_bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
{
bfd_size_type off = 1, i;
+ struct elf_strtab_hash_entry **array;
+
+ if (tab->array_sorted != NULL)
+ array = tab->array_sorted;
+ else
+ array = tab->array;
if (bfd_bwrite ("", 1, abfd) != 1)
return FALSE;
@@ -238,18 +256,17 @@
register const char *str;
register unsigned int len;
- BFD_ASSERT (tab->array[i]->refcount == 0);
- len = tab->array[i]->len;
+ BFD_ASSERT (array[i]->refcount == 0);
+ len = array[i]->len;
if ((int) len < 0)
continue;
- str = tab->array[i]->root.string;
+ str = array[i]->root.string;
if (bfd_bwrite (str, len, abfd) != len)
return FALSE;
off += len;
}
-
BFD_ASSERT (off == tab->sec_size);
return TRUE;
}
@@ -278,6 +295,33 @@
return lenA - lenB;
}
+/* Where is the qsort closure ? */
+static size_t give_me_a_bucket_count = 0;
+
+/* Sort by elf hash value % buckets */
+static int
+hash_compare (const void *a, const void *b)
+{
+ size_t h1_bucket, h2_bucket;
+ struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
+ struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
+
+ h1_bucket = A->elf_hash_value % give_me_a_bucket_count;
+ h2_bucket = B->elf_hash_value % give_me_a_bucket_count;
+
+ if (h1_bucket > h2_bucket)
+ return 1;
+ if (h1_bucket < h2_bucket)
+ return -1;
+
+ /* Make qsort faster for lots of identical empty symbols */
+ if (a > b)
+ return 1;
+ if (a < b)
+ return -1;
+ return 0;
+}
+
static inline int
is_suffix (const struct elf_strtab_hash_entry *A,
const struct elf_strtab_hash_entry *B)
@@ -293,9 +337,8 @@
/* This function assigns final string table offsets for used strings,
merging strings matching suffixes of longer strings if possible. */
-
void
-_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
+_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab, size_t bucket_count)
{
struct elf_strtab_hash_entry **array, **a, *e;
bfd_size_type size, amt;
@@ -361,15 +404,27 @@
}
}
-alloc_failure:
- if (array)
- free (array);
+ if (bucket_count && !getenv ("DONTSORT_SYMS"))
+ {
+ fprintf (stderr, "Sorting symbols\n");
+ give_me_a_bucket_count = bucket_count;
+ for (i = 0; i < tab->size; ++i)
+ array[i] = tab->array[i];
+ qsort (array + 1, tab->size - 1, sizeof (struct elf_strtab_hash_entry *), hash_compare);
+ tab->array_sorted = array;
+ }
+ else
+ {
+ free (array);
+ alloc_failure:
+ array = tab->array;
+ }
/* Assign positions to the strings we want to keep. */
size = 1;
for (i = 1; i < tab->size; ++i)
{
- e = tab->array[i];
+ e = array[i];
if (e->refcount && e->len > 0)
{
e->u.index = size;
@@ -382,7 +437,7 @@
/* Adjust the rest. */
for (i = 1; i < tab->size; ++i)
{
- e = tab->array[i];
+ e = array[i];
if (e->refcount && e->len < 0)
e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
}