Re: Another linker performance issue

[Pascal Obry <pascal at obry dot net>]

Kai,

> Hmm, we could also do in the first call for bfd_link_hash_traverse
> build up a table for undefined-symbol names only.
> And then do the actual operations based on this candidate list only?
> 
> We avoid here at least to run over all symbols in hash_table multiple times

Right. This is close to what I was proposing I think. I've gone this
path but not implementing a new hash table. I've created an array with a
key and associated bfd_link_hash_entry. This array is sorted and
searched using bsearch(). In my small test case the time went from 7s to
0.3s. Looks promising.

Please see attached patch. Bear in mind that I've a limited knowledge in
binutils internal. The patch is a first attempt to fix this issue, I'm
still wondering if it is correct and at least equivalent to the previous
code.

Please review and let me know if this is going in the right direction.

Thanks.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|    http://www.obry.net  -  http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B

commit 093041497cc322ecbf0250eacdb469480dd35f8b
Author: Pascal Obry <pascal@obry.net>
Date:   Fri Mar 2 15:17:40 2012 +0100

    ld/
    
        2012-03-02  Pascal Obry  <pascal@obry.net>
    
            * ld/pe-dll.c:
            (found_sym): Remove global variable, not needed anymore
            (undef_count): New variable.
            (undef_search): New routine.
            (pe_find_cdecl_alias_match): Use bsearch instead of traversing
            all symbols. This gives a large speed-up when linking against
            DLL with many symbols.
            (pe_undef_count): New routine.
            (pe_undef_fill): Likewise.
            (pe_create_undef_table): Likewise.
            (pe_process_import_defs): Call pe_create_undef_table.

diff --git a/ld/pe-dll.c b/ld/pe-dll.c
index 6e66131..87e87e6 100644
--- a/ld/pe-dll.c
+++ b/ld/pe-dll.c
@@ -2811,36 +2811,101 @@ pe_dll_generate_implib (def_file *def, const char *impfilename, struct bfd_link_
     }
 }
 
-static struct bfd_link_hash_entry *found_sym;
+static int undef_count = 0;
+
+struct key_value
+{
+  const char *key;
+  struct bfd_link_hash_entry *he;
+};
+
+struct key_value *udef_table;
+
+static int undef_search (const void *m1, const void *m2)
+{
+  const struct key_value *kv1 = m1;
+  const struct key_value *kv2 = m2;
+  return strcmp (kv1->key, kv2->key);
+}
+
+static struct bfd_link_hash_entry *
+pe_find_cdecl_alias_match (char *name)
+{
+  struct bfd_link_hash_entry *found_sym = 0;
+
+  struct bfd_link_hash_entry key;
+  key.root.string = name;
+
+  found_sym = bsearch
+    (&key, udef_table, undef_count,
+     sizeof (struct bfd_link_hash_entry *), undef_search);
+
+  return found_sym;
+}
+
+static bfd_boolean
+pe_undef_count (struct bfd_link_hash_entry *h ATTRIBUTE_UNUSED,
+                void *inf ATTRIBUTE_UNUSED)
+{
+  if (h->type == bfd_link_hash_undefined)
+    undef_count++;
+  return TRUE;
+}
 
 static bfd_boolean
-pe_undef_alias_cdecl_match (struct bfd_link_hash_entry *h, void *inf)
+pe_undef_fill (struct bfd_link_hash_entry *h, void *inf ATTRIBUTE_UNUSED)
 {
-  int sl;
-  char *string = inf;
-  const char *hs = h->root.string;
-
-  sl = strlen (string);
-  if (h->type == bfd_link_hash_undefined
-      && ((*hs == '@' && (!pe_details->underscored || *string == '_')
-	   && strncmp (hs + 1, string + (pe_details->underscored != 0),
-		       sl - (pe_details->underscored != 0)) == 0)
-	  || strncmp (hs, string, sl) == 0)
-      && h->root.string[sl] == '@')
+  if (h->type == bfd_link_hash_undefined)
     {
-      found_sym = h;
-      return FALSE;
+      char *start = (char *)h->root.string;
+      char *stop;
+      char *key;
+      int len;
+
+      /* remove leading '@' */
+      if (*start == '@')
+        start++;
+
+      /* remove stdcall suffix if any */
+      stop = start;
+      while (*stop && (*stop != '@'))
+        stop++;
+
+      len = stop - start + 1;
+      key = xmalloc (len);
+      strncpy (key, start, len);
+      key[len] = '\0';
+
+      udef_table[undef_count].key = key;
+      udef_table[undef_count].he = h;
+      undef_count++;
     }
   return TRUE;
 }
 
-static struct bfd_link_hash_entry *
-pe_find_cdecl_alias_match (char *name)
+static int undef_sort (const void *m1, const void *m2)
 {
-  found_sym = 0;
-  bfd_link_hash_traverse (link_info.hash, pe_undef_alias_cdecl_match,
-			  (char *) name);
-  return found_sym;
+  const struct key_value *kv1 = m1;
+  const struct key_value *kv2 = m2;
+  return strcmp (kv1->key, kv2->key);
+}
+
+static void pe_create_undef_table (void)
+{
+  undef_count = 0;
+
+  /* count undefined symbols */
+
+  bfd_link_hash_traverse (link_info.hash, pe_undef_count, "");
+
+  /* create and fill the corresponding table */
+  udef_table = xmalloc (undef_count * sizeof (struct key_value));
+
+  undef_count = 0;
+  bfd_link_hash_traverse (link_info.hash, pe_undef_fill, "");
+
+  /* sort items */
+  qsort (udef_table, undef_count, sizeof (struct key_value), undef_sort);
 }
 
 static void
@@ -2868,6 +2933,8 @@ pe_process_import_defs (bfd *output_bfd, struct bfd_link_info *linfo)
   if (!pe_def_file)
     return;
 
+  pe_create_undef_table();
+
   for (module = pe_def_file->modules; module; module = module->next)
     {
       int i, do_this_dll;
@@ -2962,6 +3029,7 @@ pe_process_import_defs (bfd *output_bfd, struct bfd_link_info *linfo)
 
       free (dll_symname);
     }
+  free (udef_table);
 }
 
 /* We were handed a *.DLL file.  Parse it and turn it into a set of