On 07/13/2014 12:41 AM, Peter Levart wrote:
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.
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))
)
);
Incorporated in new webrev:
http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.08/
Also in this webrev: changing the condition by which putAll() decides to
call resize() makes a boolean return from resize() unnecessary again,
since it's only called when resize is actually needed (from put() when
3*size reaches 2*capacity, from putAll(), when capacity calculated from
argument map's size is greater than current capacity). Retry loop in
put() can be simplified consequently.
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
