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

[Peter Levart]

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
>>>
>>
>