Patch: Use hash table in section_already_linked

[Steve Chamberlain <sac at transmeta dot com>]

Or: Double the speed of linker for some nasty cases.

I've got a program built from hundreds of bloated c++ files.  It takes
forever to link.  gprof showed some low hanging fruit:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 45.59     11.69    11.69    28038     0.42     0.42  section_already_linked
 37.68     21.35     9.66      676    14.29    17.12  _bfd_link_section_stabs
...


This patch changes the section_already_linked code to use a hash table
rather than a linked list, reducing the user mode time of the linker
from 44 to 16 seconds.  (If I turn off the stab section optimization
to reduce the _bfd_link_section_stabs time, my output file bloats from
26M to just under half a gig, so the savings in user mode thinking
time are swamped by the time to write the image out).


Steve


1999-11-01  Steve Chamberlain  <sac@pobox.com>

	* ldlang.c (section_already_linked): Rework to use hash table.
	(already_linked_newfunc): New function.
	(already_linked_table_init): New function.
	(already_linked_table_free): New function.
	(lang_process): Initialize and free the already_linked hash table.


bash$ cvs diff -c3p ldlang.c
Index: ldlang.c
===================================================================
RCS file: /cvs/binutils/binutils/ld/ldlang.c,v
retrieving revision 1.13
diff -c -3 -p -r1.13 ldlang.c
*** ldlang.c	1999/09/12 16:10:00	1.13
--- ldlang.c	1999/11/01 18:52:24
*************** exp_init_os (exp)
*** 858,873 ****
        break;
      }
  }
! 
  /* Sections marked with the SEC_LINK_ONCE flag should only be linked
!    once into the output.  This routine checks each sections, and
!    arranges to discard it if a section of the same name has already
     been linked.  If the section has COMDAT information, then it uses
     that to decide whether the section should be included.  This code
     assumes that all relevant sections have the SEC_LINK_ONCE flag set;
!    that is, it does not depend solely upon the section name.  This is
!    called via bfd_map_over_sections.  */
  
  /*ARGSUSED*/
  static void
  section_already_linked (abfd, sec, data)
--- 858,895 ----
        break;
      }
  }
! 
  /* Sections marked with the SEC_LINK_ONCE flag should only be linked
!    once into the output.  These routine check each sections, and
!    arrange to discard it if a section of the same name has already
     been linked.  If the section has COMDAT information, then it uses
     that to decide whether the section should be included.  This code
     assumes that all relevant sections have the SEC_LINK_ONCE flag set;
!    that is, it does not depend solely upon the section name.
!    section_already_linked is called via bfd_map_over_sections.  */
! 
! /* This is the shape of the elements inside the already_linked hash
!    table. It maps a name onto a list of already_linked elements with
!    the same name.  It's possible to get more than one element in a
!    list if the COMDAT sections have different names.  */
! 
! struct already_linked_hash_entry 
! {
!   struct bfd_hash_entry root;
!   struct already_linked *entry;
! };
! 
! struct already_linked 
! {
!   struct already_linked *next;
!   asection *sec;
! };
  
+ /* The hash table.  */
+ 
+ static struct bfd_hash_table already_linked_table;
+ 
+ 
  /*ARGSUSED*/
  static void
  section_already_linked (abfd, sec, data)
*************** section_already_linked (abfd, sec, data)
*** 876,890 ****
       PTR data;
  {
    lang_input_statement_type *entry = (lang_input_statement_type *) data;
-   struct sec_link_once
-     {
-       struct sec_link_once *next;
-       asection *sec;
-     };
-   static struct sec_link_once *sec_link_once_list;
    flagword flags;
    const char *name;
!   struct sec_link_once *l;
  
    /* If we are only reading symbols from this object, then we want to
       discard all sections.  */
--- 898,907 ----
       PTR data;
  {
    lang_input_statement_type *entry = (lang_input_statement_type *) data;
    flagword flags;
    const char *name;
!   struct already_linked *l;
!   struct already_linked_hash_entry *already_linked_list;
  
    /* If we are only reading symbols from this object, then we want to
       discard all sections.  */
*************** section_already_linked (abfd, sec, data)
*** 919,930 ****
  
    name = bfd_get_section_name (abfd, sec);
  
!   for (l = sec_link_once_list; l != NULL; l = l->next)
!     {
!       if (strcmp (name, bfd_get_section_name (l->sec->owner, l->sec)) == 0
! 	  && (sec->comdat == NULL
! 	      || l->sec->comdat == NULL
! 	      || strcmp (sec->comdat->name, l->sec->comdat->name) == 0))
  	{
  	  /* The section has already been linked.  See if we should
               issue a warning.  */
--- 936,950 ----
  
    name = bfd_get_section_name (abfd, sec);
  
!   already_linked_list = 
!     (struct already_linked_hash_entry *)
!       bfd_hash_lookup (&already_linked_table, name, true, false);
! 
!   for (l = already_linked_list->entry;  l != NULL; l = l->next)
!     {
!       if (sec->comdat == NULL
! 	  || l->sec->comdat == NULL
! 	  || strcmp (sec->comdat->name, l->sec->comdat->name) == 0)
  	{
  	  /* The section has already been linked.  See if we should
               issue a warning.  */
*************** section_already_linked (abfd, sec, data)
*** 972,985 ****
  	  return;
  	}
      }
  
!   /* This is the first section with this name.  Record it.  */
  
-   l = (struct sec_link_once *) xmalloc (sizeof *l);
    l->sec = sec;
!   l->next = sec_link_once_list;
!   sec_link_once_list = l;
  }
  
  /* The wild routines.
  
--- 992,1036 ----
  	  return;
  	}
      }
+ 
+   /* This is the first section with this name.  Record it.  Allocate
+      the memory from the same obstack as the hash table is kept in.  */
  
!   l = (struct already_linked *) 
!     bfd_hash_allocate (&already_linked_table, sizeof *l);
  
    l->sec = sec;
!   l->next = already_linked_list->entry;
!   already_linked_list->entry = l;
! }
! 
! /* Support routines for the hash table used by section_already_linked,
!    initialize the table, fill in an entry and remove the table.  */
! 
! struct bfd_hash_entry *already_linked_newfunc (entry, table, string)
!      struct bfd_hash_entry *entry ATTRIBUTE_UNUSED;
!      struct bfd_hash_table *table;
!      const char *string ATTRIBUTE_UNUSED;
! {
!   struct already_linked_hash_entry *ret = 
!     bfd_hash_allocate (table, sizeof(struct already_linked_hash_entry));
! 
!   ret->entry = 0;
! 
!   return (struct bfd_hash_entry *) ret;
! }
! 
! static void already_linked_table_init()
! {
!   if (!bfd_hash_table_init_n (&already_linked_table, already_linked_newfunc, 42))
!     einfo (_("%P%F: Failed to create hash table\n"));
! }
! 
! static void already_linked_table_free ()
! {
!   bfd_hash_table_free (&already_linked_table);
  }
+ 
  
  /* The wild routines.
  
*************** lang_process ()
*** 3848,3858 ****
--- 3899,3913 ----
    /* Add to the hash table all undefineds on the command line */
    lang_place_undefineds ();
  
+   already_linked_table_init();
+ 
    /* Create a bfd for each input file */
    current_target = default_target;
    open_input_bfds (statement_list.head, false);
  
    ldemul_after_open ();
+ 
+   already_linked_table_free();
  
    /* Make sure that we're not mixing architectures.  We call this
       after all the input files have been opened, but before we do any