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

[Peter Levart]

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