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

[Ivan Gerasimov]

Peter, seems you need to fix capacity():

int capacity = Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));

does not necessarily produces a negative number in the case of overflow.

Why don't you want to use the variant that from the latest Martin's webrev?
It seems to work correctly with your proposal too.

Sincerely yours,
Ivan


On 12.07.2014 22:12, Peter Levart wrote:
>
> On 07/12/2014 05:47 PM, Peter Levart wrote:
>> If we're willing to pay the price of special-casing the 
>> non-power-of-2 MAX_CAPACITY = (1 << 29) + (1 << 28), which amounts to 
>> approx. 4% of performance,
>>
>> Then here's a possible solution:
>>
>> http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.06/
>>
>
> Two fixes:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.07/
>
> One is a fix for possible overflow in resize() + rearrangement (which 
> is specific to my proposal) and the other is replacement of condition 
> that triggers resize in put() from (3*size > length) to (3*size >= 
> length). The later should be applied to Martin's latest version too, I 
> think, if it is decided that my proposal is inadequate.
>
> Why is (3*size >= length) more appropriate condition to trigger 
> resize? Because it is more aligned with capacity(size) function which 
> is basically a clamped Integer.highestOneBit(3 * size).
>
> Map preallocation makes a table with length = 2 * 
> capacity(expectedMaxSize)
>
> (3 * size < 2 * highestOneBit(3*size)) is true for any size, so IHM 
> will never be resized if filled with size elements and table was 
> preallocated with length =
> 2 * highestOneBit(3*size) even if condition for resizing is changed 
> from (3*size > length) to (3*size >= length). Current condition 
> sometimes resizes a little to late when preallocation would already 
> create a bigger table.
>
> Now if we change that, my proposed webrev.07 does not need 
> MAXIMUM_SIZE constant any more. Attempt to insert the 2^29-th element 
> (when size is about to become 2^29) triggers resize since at that time 
> length == 2 * MAXIMUM_CAPACITY which is exactly 3 * 2^29 and this 
> alone can be used as a trigger to throw OOME in resize()...
>
> Regards, Peter
>