RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
Peter Levart
peter.levart at gmail.com
Sat Jul 12 22:41:11 UTC 2014
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
>>
>
More information about the core-libs-dev
mailing list