Re: parallelized 'ld'?

[DJ Delorie <dj at redhat dot com>]

> > Automatically expanding hashtables when they reach ludicrous overload
> > levels isn't that hard -- I've been doing it without a second thought
> > in everything I've written for the last twenty years.  No?
> 
> Here's a quick patch to implement that, at least in a naive way.  See
> if this makes a difference in link speed (at least for large apps; I
> don't notice a significant speedup for linking cc1) and if it's worth
> the effort I'll document it, clean it up, test it, and commit it.

We never finished with this patch.  I've attached an updated copy
(cosmetic changes only).  Any reason not to apply it?  Nobody had any
complaints before, just a question about using libiberty's hashtab
(bigger change than needed, bfd_hash is used lots of places, etc).

2004-06-09  DJ Delorie  <dj@redhat.com>

	* bfd-in.h (bfd_hash_table): Add count field.
	* bfd-in2.h: Regenerate.
	* hash.c (higher_prime_number): New.
	(bfd_hash_table_inint_n): Init count field.
	(bfd_hash_lookup): Grow table as needed.

Index: bfd-in.h
===================================================================
RCS file: /cvs/uberbaum/./bfd/bfd-in.h,v
retrieving revision 1.80
diff -p -C2 -r1.80 bfd-in.h
*** bfd-in.h	21 May 2004 15:38:01 -0000	1.80
--- bfd-in.h	9 Jun 2004 23:46:39 -0000
*************** struct bfd_hash_table
*** 372,375 ****
--- 372,377 ----
    /* The number of slots in the hash table.  */
    unsigned int size;
+   /* The number of entries in the hash table.  */
+   unsigned int count;
    /* A function used to create new elements in the hash table.  The
       first entry is itself a pointer to an element.  When this
Index: bfd-in2.h
===================================================================
RCS file: /cvs/uberbaum/./bfd/bfd-in2.h,v
retrieving revision 1.279
diff -p -C2 -r1.279 bfd-in2.h
*** bfd-in2.h	28 May 2004 12:32:01 -0000	1.279
--- bfd-in2.h	9 Jun 2004 23:46:40 -0000
*************** struct bfd_hash_table
*** 379,382 ****
--- 379,384 ----
    /* The number of slots in the hash table.  */
    unsigned int size;
+   /* The number of entries in the hash table.  */
+   unsigned int count;
    /* A function used to create new elements in the hash table.  The
       first entry is itself a pointer to an element.  When this
Index: hash.c
===================================================================
RCS file: /cvs/uberbaum/./bfd/hash.c,v
retrieving revision 1.13
diff -p -C2 -r1.13 hash.c
*** hash.c	24 May 2004 07:49:10 -0000	1.13
--- hash.c	9 Jun 2004 23:46:40 -0000
*************** SUBSUBSECTION
*** 301,305 ****
  
  /* The default number of entries to use when creating a hash table.  */
! #define DEFAULT_SIZE 4051
  static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
  
--- 301,371 ----
  
  /* The default number of entries to use when creating a hash table.  */
! #define DEFAULT_SIZE (4093)
! 
! /* The following function returns a nearest prime number which is
!    greater than N, and near a power of two.  Copied from libiberty.  */
! 
! static unsigned long
! higher_prime_number (n)
!      unsigned long n;
! {
!   /* These are primes that are near, but slightly smaller than, a
!      power of two.  */
!   static const unsigned long primes[] = {
!     (unsigned long) 7,
!     (unsigned long) 13,
!     (unsigned long) 31,
!     (unsigned long) 61,
!     (unsigned long) 127,
!     (unsigned long) 251,
!     (unsigned long) 509,
!     (unsigned long) 1021,
!     (unsigned long) 2039,
!     (unsigned long) 4093,
!     (unsigned long) 8191,
!     (unsigned long) 16381,
!     (unsigned long) 32749,
!     (unsigned long) 65521,
!     (unsigned long) 131071,
!     (unsigned long) 262139,
!     (unsigned long) 524287,
!     (unsigned long) 1048573,
!     (unsigned long) 2097143,
!     (unsigned long) 4194301,
!     (unsigned long) 8388593,
!     (unsigned long) 16777213,
!     (unsigned long) 33554393,
!     (unsigned long) 67108859,
!     (unsigned long) 134217689,
!     (unsigned long) 268435399,
!     (unsigned long) 536870909,
!     (unsigned long) 1073741789,
!     (unsigned long) 2147483647,
! 					/* 4294967291L */
!     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
!   };
! 
!   const unsigned long *low = &primes[0];
!   const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
! 
!   while (low != high)
!     {
!       const unsigned long *mid = low + (high - low) / 2;
!       if (n >= *mid)
! 	low = mid + 1;
!       else
! 	high = mid;
!     }
! 
!   /* If we've run out of primes, abort.  */
!   if (n > *low)
!     {
!       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
!       abort ();
!     }
! 
!   return *low;
! }
! 
  static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
  
*************** bfd_hash_table_init_n (table, newfunc, s
*** 333,336 ****
--- 399,403 ----
    memset ((PTR) table->table, 0, alloc);
    table->size = size;
+   table->count = 0;
    table->newfunc = newfunc;
    return TRUE;
*************** bfd_hash_lookup (table, string, create, 
*** 403,406 ****
--- 470,474 ----
    if (hashp == (struct bfd_hash_entry *) NULL)
      return (struct bfd_hash_entry *) NULL;
+   table->count ++;
    if (copy)
      {
*************** bfd_hash_lookup (table, string, create, 
*** 422,425 ****
--- 490,522 ----
    table->table[index] = hashp;
  
+   if (table->count > table->size * 3 / 4)
+     {
+       int newsize = higher_prime_number (table->size);
+       struct bfd_hash_entry **newtable, *he;
+       unsigned int hi;
+       unsigned int alloc;
+ 
+       alloc = newsize * sizeof (struct bfd_hash_entry *);
+ 
+       fprintf(stderr, "dj: expand count %d size %d to %d\n", table->count, table->size, newsize);
+ 
+       newtable = ((struct bfd_hash_entry **)
+ 		  objalloc_alloc ((struct objalloc *) table->memory, alloc));
+       memset ((PTR) newtable, 0, alloc);
+ 
+       for (hi = 0; hi < table->size; hi ++)
+ 	while (table->table[hi])
+ 	  {
+ 	    int index;
+ 	    he = table->table[hi];
+ 	    table->table[hi] = he->next;
+ 	    index = he->hash % newsize;
+ 	    he->next = newtable[index];
+ 	    newtable[index] = he;
+ 	  }
+       table->table = newtable;
+       table->size = newsize;
+     }
+ 
    return hashp;
  }