This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
Re: Slow linker with shared C++ libraries
On Thu, Feb 26, 2004 at 07:09:00AM +0100, Jakub Jelinek wrote:
> On Wed, Feb 25, 2004 at 11:42:24PM -0800, H. J. Lu wrote:
> > On Wed, Feb 25, 2004 at 10:19:28PM -0800, H. J. Lu wrote:
> > > If a shared C++ library has many weak data definitions and many
> > > symbols, linking against such libraries can be very slow since
> > > elf_link_add_object_symbols has to go through all symbols for
> > > each referenced weak data definition to search for its aliases,
> > > although in most cases there is no alias. What is the best way
> > > to speed it up? Can we introduce a linker command not to check
> > > aliase for a DSO?
> > >
> >
> > I am thinking about adding a special note section which contains the
> > symbol alias information so that the linker doesn't have to go through
> > the whole symbol list even though a symbol may have no alias at
> > all.
>
> Or you perhaps could when reading symbols qsort them by value and build
> the alias info yourself at symbol read time.
>
This patch seems to solve my problem quite nicely. In one testcase,
link time went from 20 seconds to 3 seconds.
H.J.
-----
2004-02-26 H.J. Lu <hongjiu.lu@intel.com>
* elflink.h (sort_symbol): New.
(elf_link_add_object_symbols): Use a sorted symbol array for
weakdef.
--- bfd/elflink.h.weak 2004-02-24 09:32:07.000000000 -0800
+++ bfd/elflink.h 2004-02-26 12:26:15.000000000 -0800
@@ -392,6 +392,18 @@ elf_link_add_archive_symbols (bfd *abfd,
return FALSE;
}
+/* Sort symbol by value. */
+static int
+sort_symbol (const void *arg1, const void *arg2)
+{
+ const struct elf_link_hash_entry *h1
+ = *(const struct elf_link_hash_entry **) arg1;
+ const struct elf_link_hash_entry *h2
+ = *(const struct elf_link_hash_entry **) arg2;
+
+ return h1->root.u.def.value - h2->root.u.def.value;
+}
+
/* Add symbols from an ELF object file to the linker hash table. */
static bfd_boolean
@@ -1493,63 +1505,129 @@ elf_link_add_object_symbols (bfd *abfd,
assembler code, handling it correctly would be very time
consuming, and other ELF linkers don't handle general aliasing
either. */
- while (weaks != NULL)
+ if (weaks != NULL)
{
- struct elf_link_hash_entry *hlook;
- asection *slook;
- bfd_vma vlook;
struct elf_link_hash_entry **hpp;
struct elf_link_hash_entry **hppend;
+ struct elf_link_hash_entry **sorted_sym_hash;
+ struct elf_link_hash_entry *h;
+ size_t sym_count;
- hlook = weaks;
- weaks = hlook->weakdef;
- hlook->weakdef = NULL;
-
- BFD_ASSERT (hlook->root.type == bfd_link_hash_defined
- || hlook->root.type == bfd_link_hash_defweak
- || hlook->root.type == bfd_link_hash_common
- || hlook->root.type == bfd_link_hash_indirect);
- slook = hlook->root.u.def.section;
- vlook = hlook->root.u.def.value;
-
+ amt = extsymcount * sizeof (struct elf_link_hash_entry *);
+ sorted_sym_hash = bfd_malloc (amt);
+ if (sorted_sym_hash == NULL)
+ goto error_return;
+ sym_hash = sorted_sym_hash;
hpp = elf_sym_hashes (abfd);
hppend = hpp + extsymcount;
+ sym_count = 0;
for (; hpp < hppend; hpp++)
{
- struct elf_link_hash_entry *h;
-
h = *hpp;
- if (h != NULL && h != hlook
+ if (h != NULL
&& h->root.type == bfd_link_hash_defined
- && h->root.u.def.section == slook
- && h->root.u.def.value == vlook)
+ && h->type != STT_FUNC)
{
- hlook->weakdef = h;
+ *sym_hash = h;
+ sym_hash++;
+ sym_count++;
+ }
+ }
- /* If the weak definition is in the list of dynamic
- symbols, make sure the real definition is put there
- as well. */
- if (hlook->dynindx != -1
- && h->dynindx == -1)
+ qsort (sorted_sym_hash, sym_count,
+ sizeof (struct elf_link_hash_entry *),
+ sort_symbol);
+
+ while (weaks != NULL)
+ {
+ struct elf_link_hash_entry *hlook;
+ asection *slook;
+ bfd_vma vlook;
+ int diff, k, ilook;
+ size_t i, j, idx;
+
+ hlook = weaks;
+ weaks = hlook->weakdef;
+ hlook->weakdef = NULL;
+
+ BFD_ASSERT (hlook->root.type == bfd_link_hash_defined
+ || hlook->root.type == bfd_link_hash_defweak
+ || hlook->root.type == bfd_link_hash_common
+ || hlook->root.type == bfd_link_hash_indirect);
+ slook = hlook->root.u.def.section;
+ vlook = hlook->root.u.def.value;
+
+ ilook = -1;
+ i = 0;
+ j = sym_count;
+ while (i < j)
+ {
+ idx = (i + j) / 2;
+ h = sorted_sym_hash [idx];
+ diff = vlook - h->root.u.def.value;
+ if (diff < 0)
+ j = idx;
+ else if (diff > 0)
+ i = idx + 1;
+ else
{
- if (! _bfd_elf_link_record_dynamic_symbol (info, h))
- goto error_return;
+ ilook = idx;
+ break;
}
+ }
+
+ /* We didn't find a value match. */
+ if (ilook == -1)
+ continue;
+
+ /* We have to start at the first value match since section
+ may be different. */
+ for (k = ilook - 1; k >= 0; k--)
+ {
+ h = sorted_sym_hash [k];
+ if (vlook != h->root.u.def.value)
+ break;
+ }
- /* If the real definition is in the list of dynamic
- symbols, make sure the weak definition is put there
- as well. If we don't do this, then the dynamic
- loader might not merge the entries for the real
- definition and the weak definition. */
- if (h->dynindx != -1
- && hlook->dynindx == -1)
+ /* We need to check if section matches or not. */
+ for (i = k + 1; i < sym_count; i++)
+ {
+ h = sorted_sym_hash [i];
+
+ /* Stop if value doesn't match. */
+ if (h->root.u.def.value != vlook)
+ break;
+ else if (h != hlook && h->root.u.def.section == slook)
{
- if (! _bfd_elf_link_record_dynamic_symbol (info, hlook))
- goto error_return;
+ hlook->weakdef = h;
+
+ /* If the weak definition is in the list of dynamic
+ symbols, make sure the real definition is put
+ there as well. */
+ if (hlook->dynindx != -1 && h->dynindx == -1)
+ {
+ if (! _bfd_elf_link_record_dynamic_symbol (info,
+ h))
+ goto error_return;
+ }
+
+ /* If the real definition is in the list of dynamic
+ symbols, make sure the weak definition is put
+ there as well. If we don't do this, then the
+ dynamic loader might not merge the entries for the
+ real definition and the weak definition. */
+ if (h->dynindx != -1 && hlook->dynindx == -1)
+ {
+ if (! _bfd_elf_link_record_dynamic_symbol (info,
+ hlook))
+ goto error_return;
+ }
+ break;
}
- break;
}
}
+
+ free (sorted_sym_hash);
}
/* If this object is the same format as the output object, and it is