[binutils-gdb] stringmerge: don't presize hash table

[Michael Matz]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=8483536dea6e36e9f4a0949ecad0fcaafd62cf54

commit 8483536dea6e36e9f4a0949ecad0fcaafd62cf54
Author: Michael Matz <matz@suse.de>
Date:   Mon Oct 21 17:58:32 2024 +0200

    stringmerge: don't presize hash table
    
    originally the reason for pre-sizing was that that's easier
    for a multi-threaded use of the hash table.  That hasn't materialized
    yet, so there's not much sense in using the very very conservative
    estimates for pre-sizing.  Doing the resize on-demand, whenever we
    actually need to add a new entry doesn't change performance.
    
            bfd/
            merge.c (sec_merge_hash_insert): Resize as needed from here ...
            (record_section): ... not from here.  Don't calculate estimates,
            return bool instead of three-state, regard all errors as soft
            errors.
            (_bfd_merge_sections): Adjust.

Diff:
---
 bfd/merge.c | 70 +++++++++++++++++++++++++++----------------------------------
 1 file changed, 31 insertions(+), 39 deletions(-)

diff --git a/bfd/merge.c b/bfd/merge.c
index abb0269227e..cb8251cb42e 100644
--- a/bfd/merge.c
+++ b/bfd/merge.c
@@ -244,8 +244,23 @@ sec_merge_hash_insert (struct sec_merge_hash *table,
   hashp->alignment = 0;
   hashp->u.suffix = NULL;
   hashp->next = NULL;
-  // We must not need resizing, otherwise the estimation was wrong
-  BFD_ASSERT (!NEEDS_RESIZE (bfdtab->count + 1, table->nbuckets));
+
+  if (NEEDS_RESIZE (bfdtab->count + 1, table->nbuckets))
+    {
+      if (!sec_merge_maybe_resize (table, 1))
+	return NULL;
+      uint64_t *key_lens = table->key_lens;
+      unsigned int nbuckets = table->nbuckets;
+      _index = hash & (nbuckets - 1);
+      while (1)
+	{
+	  uint64_t candlen = key_lens[_index];
+	  if (!(candlen & (uint32_t)-1))
+	    break;
+	  _index = (_index + 1) & (nbuckets - 1);
+	}
+    }
+
   bfdtab->count++;
   table->key_lens[_index] = (hash << 32) | (uint32_t)len;
   table->values[_index] = hashp;
@@ -699,12 +714,11 @@ _bfd_add_merge_section (bfd *abfd, void **psinfo, asection *sec,
 }
 
 /* Record one whole input section (described by SECINFO) into the hash table
-   SINFO.  Returns 0 on hard errors (no sense in continuing link),
-   1 when section is completely recorded, and 2 when the section wasn't
-   recorded but we can continue (e.g. by simply not deduplicating this
-   section).  */
+   SINFO.  Returns true when section is completely recorded, and false when
+   it wasn't recorded but we can continue (e.g. by simply not deduplicating
+   this section).  */
 
-static int
+static bool
 record_section (struct sec_merge_info *sinfo,
 		struct sec_merge_sec_info *secinfo)
 {
@@ -736,15 +750,6 @@ record_section (struct sec_merge_info *sinfo,
 
   /* Now populate the hash table and offset mapping.  */
 
-  /* Presize the hash table for what we're going to add.  We overestimate
-     quite a bit, but if it turns out to be too much then other sections
-     merged into this area will make use of that as well.  */
-  if (!sec_merge_maybe_resize (sinfo->htab, 1 + sec->size / 2))
-    {
-      free (contents);
-      return 2;
-    }
-
   /* Walk through the contents, calculate hashes and length of all
      blobs (strings or fixed-size entries) we find and fill the
      hash and offset tables.  */
@@ -792,14 +797,12 @@ record_section (struct sec_merge_info *sinfo,
   /*printf ("ZZZ %s:%s %u entries\n", sec->owner->filename, sec->name,
 	  (unsigned)secinfo->noffsetmap);*/
 
-  return 1;
+  return true;
 
  error_return:
   free (contents);
   contents = NULL;
-  for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
-    *secinfo->psecinfo = NULL;
-  return 0;
+  return false;
 }
 
 /* qsort comparison function.  Won't ever return zero as all entries
@@ -987,31 +990,20 @@ _bfd_merge_sections (bfd *abfd,
       /* Record the sections into the hash table.  */
       align = 1;
       for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
-	if (secinfo->sec->flags & SEC_EXCLUDE)
+	if (secinfo->sec->flags & SEC_EXCLUDE
+	    || !record_section (sinfo, secinfo))
 	  {
 	    *secinfo->psecinfo = NULL;
 	    if (remove_hook)
 	      (*remove_hook) (abfd, secinfo->sec);
 	  }
-	else
+	else if (align)
 	  {
-	    int e = record_section (sinfo, secinfo);
-	    if (e == 0)
-	      return false;
-	    if (e == 2)
-	      {
-		*secinfo->psecinfo = NULL;
-		if (remove_hook)
-		  (*remove_hook) (abfd, secinfo->sec);
-	      }
-	    else if (align)
-	      {
-		unsigned int opb = bfd_octets_per_byte (abfd, secinfo->sec);
-
-		align = (bfd_size_type) 1 << secinfo->sec->alignment_power;
-		if (((secinfo->sec->size / opb) & (align - 1)) != 0)
-		  align = 0;
-	      }
+	    unsigned int opb = bfd_octets_per_byte (abfd, secinfo->sec);
+
+	    align = (bfd_size_type) 1 << secinfo->sec->alignment_power;
+	    if (((secinfo->sec->size / opb) & (align - 1)) != 0)
+	      align = 0;
 	  }
 
       if (sinfo->htab->first == NULL)