ld: Avoid overflows in string merging

[Jan Beulich]

On 09.11.2023 17:27, Michael Matz wrote:
> 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 :-)

Hmm, I see. I will admit that I didn't look at the hash lookup function
at all. Instead when seeing "hash" I assumed "hash" in the (to me) more
conventional sense, where lookup speed doesn't depend on how full the
hash table is, but merely on how long the collision chains are that
hang off of every table entry (and them growing to long then typically
being a sign of a not overly good hash function).

Jan