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
