PR32260: Improve estimate of number of strings

[Alan Modra]

On Wed, Oct 16, 2024 at 03:41:31PM +0200, Michael Matz wrote:
> we want to pre-size the hashtable for mergable strings,
> and so need an estimate for the number of them in one input
> section.  This reduces the over-estimation a little.
> 
> 	bfd/
> 
> 	PR ld/32260
> 	* merge.c (record_section): Throttle down the overestimation
> 	of number of entries in a section.

So this does cut down the estimate, but I think it's still wildly
oversize to use an upper bound here.  You're calculating for an input
section of unique strings (8-bit too, not 7-bit).  How often is that
going to happen in real object files?

The other thing that occurs to me is that the merge.c code doesn't
avoid resizing sinfo->htab.  Can't we delay creation of sinfo->htab
until _bfd_merge_sections, and then make a better estimate of the size
required from the total size of sections that will be added to the
hash table?  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.

> ---
> Tested without regressions on Alans list of targets.  Okay for master?
> 
>  bfd/merge.c | 34 +++++++++++++++++++++++++++++++++-
>  1 file changed, 33 insertions(+), 1 deletion(-)
> 
> diff --git a/bfd/merge.c b/bfd/merge.c
> index c811bc57eae..2b4d2e428d4 100644
> --- a/bfd/merge.c
> +++ b/bfd/merge.c
> @@ -736,10 +736,42 @@ record_section (struct sec_merge_info *sinfo,
>  
>    /* Now populate the hash table and offset mapping.  */
>  
> +  /* We use an upper bounds of the number of strings that can be
> +     possibly contained in this section.  There are a maximum of
> +     NMAX=255^n strings of length n, which then need NMAX*(n+1)
> +     bytes.  We also know that the section size fits into mapofs_type
> +     (i.e. is smaller than 4G).  */
> +  mapofs_type nestimate;
> +  if (sec->flags & SEC_STRINGS)
> +    {
> +      mapofs_type nmax, slen, remaining;
> +      nestimate = 1;
> +      nmax = 255;
> +      slen = 2;
> +      remaining = sec->size;
> +      while (remaining > 0)
> +	{
> +	  mapofs_type fits = remaining / slen;
> +	  if (fits <= nmax)
> +	    {
> +	      nestimate += fits;
> +	      break;
> +	    }
> +	  nestimate += nmax;
> +	  /* Ensure that nmax doesn't overflow.  */
> +	  BFD_ASSERT (slen < 5);
> +	  remaining -= nmax * slen;
> +	  nmax *= 255;
> +	  slen++;
> +	}
> +    }
> +  else
> +    nestimate = sec->size / sec->entsize;
> +
>    /* 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))
> +  if (!sec_merge_maybe_resize (sinfo->htab, nestimate))
>      {
>        free (contents);
>        return 2;
> -- 
> 2.42.0

-- 
Alan Modra