ld: Avoid overflows in string merging

[Michael Matz]

Hello,

On Thu, 9 Nov 2023, Jan Beulich wrote:

> > Consider count==1, oldbuckets==0x2000, and added==1<<24.  The above loop 
> > seemed more obvious to me than the other method: bit magic to round up 
> > (count+added)*3/2 to next power of two (which still would need a loop).
> 
> I didn't mean to suggest to remove the loop. What I was getting at is that
> the loop condition is more strict that necessary, as I tried to explain ...
> 
> >> We've doubled once already, and all we care about is that new capacity 
> >> be enough to cover "added". The more that - as the comment there says - 
> >> the caller already overestimates heavily.
> 
> ... here. The "whether" is deliberately at 2/3 aiui, and that's fine. The
> "how much", however, could be reduced to the next power of 2 that fits, to
> avoid excessive growth.

Ah, I see.  So, you had preferred the loop condition (but not the 
if-condition) to be merely
  while (count + added > newnb)
right?  If so, I disagree:
a) on principle grounds: the post-condition of the resize function 
should include that an immediately following resize with same args should 
do nothing.
b) on practical grounds: this is (deliberately) an internal hash 
structure, and that degrades terribly when it's almost full; so the post 
condition of the resize has to be "even if we added this many elements it 
still would only be 66% full".  I.e. no, we don't just care about the new 
capacity covering the newly added stuff, it has to well over-cover it, if 
that's a word :-)

We could talk about the concrete percentage, 75% for instance would still 
be reasonable, maybe even higher given that the hash function itself is 
relatively good.  But the resize function needs to be exited such that the 
bucket list definitely remains reasonably sparse even if all the input 
elements turn out to be distinct.

(When seeing it together with the heavy overestimating I see the point of 
course, but any change in that should tackle the estimation, not the 
resize function).


Ciao,
Michael.