RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

[Doug Lea]

On 07/04/2014 01:33 PM, Ivan Gerasimov wrote:
> On 04.07.2014 8:14, David Holmes wrote:
>> Hi Ivan,
>>
>> I find the change to capacity somewhat obfuscating and I can't see what the
>> actual bug was.
>>
> The bug was in rounding in the expression minCapacity = (3 * expectedMaxSize)/2.
> Suppose, we want the expected size to be 11, then minCapacity becomes (int)(11 *
> 3 / 2) == 16.
> The threshold is calculated later to be (int)(16 * 2 / 3) == 10, which is less
> than expected size 11.

So the bug report was based on someone noticing that with
odd-valued sizes, the undocumented 2/3 target load was
rounded down, not up, which they didn't like?

I don't object to rounding it up and modernizing the size
calculations to use highestOneBit, but it's a weak pretense :-)

>
> To address the issue I combined the division by 2 with the rounding up to the
> nearest power of two.
> I also took a chance to replace a while-loop with a single call to the
> highestOneBit method, which calculates exactly what we need here.
>
>> The recursive call to put after a resize seems very sub-optimal as you will
>> re-search the map for the non-existent key. Can you not just recompute the
>> correct indices and do the store?

The initial rationale for post-insert-resize was to avoid these issues
given the need to preserve at least one empty slot. Which I
expect to remain faster than pre-resize even with your modified patch.
Please provide systematic performance comparisons before committing!

-Doug