PR32260: Improve estimate of number of strings

[Michael Matz]

Hello,

On Thu, 17 Oct 2024, Alan Modra wrote:

> > 	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.

Yes, it's complete bollocks^W^Wvery very conservative.  

> 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?

Mostly never, of course.  Except in constructed examples that would try to 
trigger this by enumerating all 5-character strings for instance. I 
wanted to get it 100% correct in these cases as well, first, and then see 
how bad it is in practice (on the grounds that the terrible 
over-estimation will usually be used up by further mergable blobs).  
Turns out that it seems to be mostly okay, except in these insane cases 
like in the bug report :-)

So, yeah, I think I'll try to do something more fancy.  There are 
probalistic measures about how many unique things will most likely be 
contained in blobs, and suchlike.  Thing is: when I wrote all that code 
there was really a non-negligible performance impact when trying to do the 
resizing on demand in the hot loop instead of ensuring its not necessary.  

> 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,

Delaying the creation itself doesn't matter much, the resizing and real 
large allocations already happen only from within record_section and 
hence _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?

... but this is possible.  If there's better estimate of course.  Right 
now it conceptually works like this:

  for all input-sections S:
    estimate = foo(S.size);
    resize (estimate);
    do_stuff_without_resizing(S);  // 1

At (1) the potential overestimations from earlier S's will be used up.  If 
we were to instead resize the htab to be completely outside the loop over 
the input blobs:

  foreach S:
    wholesize += S.size;
  resize (estimate (wholesize));
  foreach S:
    do_stuff_without_resizing(S);

then there is no opportunity anymore to use up earlier over-estimates, as 
there's just a single measurement.  So the estimate() really needs to be 
good now, and doing that without reading and interpreting S's contents is hard.

I can see only one way here: do a less conservative estimate, and then 
live with the fact that there needs to be a needs-resize check in the hot 
loop.

> 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.

Anyway, I'll try to rewrite the code a little and see how the performance 
fares.


Ciao,
Michael.