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

Ivan Gerasimov ivan.gerasimov at oracle.com
Sat Jul 12 20:46:20 UTC 2014

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 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(3*size) even if condition for resizing is changed _from (3*size > 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 MAXIMUMSIZE 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 * MAXIMUMCAPACITY 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