Home Original page

PR32260: Improve estimate of number of strings

Michael Matz matz@suse.de
Mon Oct 21 16:25:21 GMT 2024 
Hey,

On Fri, 18 Oct 2024, Alan Modra wrote:

> On Thu, Oct 17, 2024 at 03:28:58PM +0200, Michael Matz wrote:
> > On Thu, 17 Oct 2024, Alan Modra wrote:
> > > If you used your upper bound then you'd need no resizing.
> > > 
> > > Perhaps even better would be to use a more conservative estimate
> > > based on the total section size, then implement resizing in the normal
> > > fashion on inserting entries.
> > 
> > You mean "less conservative", right?  In the sense of less over-estimation 
> > and hence not all content fitting into the table.
> 
> Yes.

Actually, over the weekend I remembered the original motivation for doing 
the pre-sizing before the hot loop.  It wasn't that it was (much) faster, 
but rather that this way it's easier to do the hashing with multiple 
threads by some clever atomic accesses on a table that is guaranteed to 
not need resizes.

Alas, that multithreading didn't happen yet (though I still somewhat plan 
to tackle that).  So there's currently no reason to not just do the 
obvious thing: resize when necessary without any sort of over-estimation.

So, like below.  Okay if it passes regtesting?

(The only other material change is that I now regard all allocation 
errors, even small ones, as soft errors that will only disable 
deduplication on the current blob, even though it's then likely to not 
succeed on further blobs either.  But if it's really a small allocation 
that doesn't work here, then other parts of the linker will likely still 
result in a linker error.)

> > Anyway, I'll try to rewrite the code a little and see how the 
> > performance fares.
> Thanks.  I'm happy to do a little rewriting myself, but I'll not start
> doing that unless you tell me to go ahead.

Go wild!


Ciao,
Michael.

------

>From ba043810892684578cc5eb213627d3be2a7e4d8c Mon Sep 17 00:00:00 2001
From: Michael Matz <matz@suse.de>
Date: Mon, 21 Oct 2024 17:58:32 +0200
Subject: stringmerge: don't presize hash table
To: binutils@sourceware.org

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.
---
 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)
-- 
2.42.0
More information about the Binutils mailing list