ld uses small fixed-size hash table

[Jeff Prothero]

[Apologies for the re-send:  I omitted the diff on the first. :( ]

There appears to be a general problem throughout binutils of
unscalability -- assumptions are made in the implementation
which break badly on programs of 1-10 million lines of code.

This is one such:  'ld' uses a hashtable of fixed size 4000
which on our images results in linearly searching bucket
chains HUNDREDS of entries long.

The idea behind hash table implementation is to avoid such
linear searches. :)

Expanding this table from 4K to 64K entries cut our link time from 3.5
minutes down to 1.5 minutes -- over a 50% saving, over 2 minutes of
CPU time shaved off every debug cycle.

I've attached our diff, but a bigger fixed hashtable size
isn't really a good fix, obviously.

Would it be impossibly difficult for hash tables to
expand in size when overload reaches some level such
as 32 * bucket-count?  Or else to implement an overflow
binary tree to cut in at that point?

Many thanks for all the good work!

 -- Jeff
    address@hidden


    *** bfd/hash.c.orig             Wed Jun  6 20:08:25 2001
    --- bfd/hash.c                  Mon Dec 16 21:17:38 2002
    ***************
    *** 581,586 ****
    --- 581,593 ----
      struct bfd_strtab_hash *
      _bfd_stringtab_init ()
      {
    +   return _bfd_stringtab_init_n(DEFAULT_SIZE);
    + }
    +
    + struct bfd_strtab_hash *
    + _bfd_stringtab_init_n (buckets)
    +   unsigned int buckets;
    + {
        struct bfd_strtab_hash *table;

        table = ((struct bfd_strtab_hash *)
    ***************
    *** 588,594 ****
        if (table == NULL)
          return NULL;

    !   if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc))
          {
            free (table);
            return NULL;
    --- 595,601 ----
        if (table == NULL)
          return NULL;

    !   if (! bfd_hash_table_init_n (&table->table,
    strtab_hash_newfunc,buckets))
          {
            free (table);
            return NULL;
    *** bfd/libbfd.h.orig           Mon Jun 11 03:04:17 2001
    --- bfd/libbfd.h                Mon Dec 16 21:16:04 2002
    ***************
    *** 464,469 ****
    --- 464,470 ----

      /* Create a string table.  */
      extern struct bfd_strtab_hash *_bfd_stringtab_init PARAMS ((void));
    + extern struct bfd_strtab_hash *_bfd_stringtab_init_n PARAMS ((unsigned int
    buckets));

      /* Create an XCOFF .debug section style string table.  */
      extern struct bfd_strtab_hash *_bfd_xcoff_stringtab_init PARAMS ((void));
    *** bfd/stabs.c.orig            Wed Jun  6 20:08:26 2001
    --- bfd/stabs.c                 Mon Dec 16 21:16:03 2002
    ***************
    *** 227,233 ****
            if (*psinfo == NULL)
            goto error_return;
            sinfo = (struct stab_info *) *psinfo;
    !       sinfo->strings = _bfd_stringtab_init ();
            if (sinfo->strings == NULL)
            goto error_return;
            /* Make sure the first byte is zero.  */
    --- 227,233 ----
            if (*psinfo == NULL)
            goto error_return;
            sinfo = (struct stab_info *) *psinfo;
    !       sinfo->strings = _bfd_stringtab_init_n (65537);
            if (sinfo->strings == NULL)
            goto error_return;
            /* Make sure the first byte is zero.  */


    ----------