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

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 MAXCAPACITY = (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 (3size > length) to (3size >= 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(3size)) is true for any size, so IHM will never be resized if filled with size elements and table was preallocated with length = 2 * highestOneBit(3size) even if condition for resizing is changed from (3size > length) to (3size >= 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