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

Peter Levart peter.levart at gmail.com
Sat Jul 12 18:12:17 UTC 2014

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:


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

More information about the core-libs-dev mailing list