On 07/12/2014 10:46 PM, Ivan Gerasimov wrote:
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.
Good catch. You're right.
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.
Not quite. Martin's version is:
return
(expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
(expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ?
MINIMUM_CAPACITY :
Integer.highestOneBit(expectedMaxSize + (expectedMaxSize <<
1));
My MAXIMUM_CAPACITY is not power of two, but: 3 << 28;
If, for example, expectedMaxSize = (1 << 28) + 1, then Martin's
capacity() would return MAXIMUM_CAPACITY, but I would like it to return
2 ^ 29, since expectedMaxSize is only just past 50% of such capacity.
So here's a better variant:
return Math.min(
MAXIMUM_CAPACITY,
Math.max(
MINIMUM_CAPACITY,
expectedMaxSize > Integer.MAX_VALUE / 3
? MAXIMUM_CAPACITY // 3 * expectedMaxSize would
overflow
: Integer.highestOneBit(expectedMaxSize +
(expectedMaxSize << 1))
)
);
I'll put this and another simplification into a new webrev tomorow.
Regards, Peter
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
