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

[Ivan Gerasimov]

Thanks David for looking at the change!

On 04.07.2014 8:14, David Holmes wrote:
> Hi Ivan,
>
> I find the change to capacity somewhat obfuscating and I can't see 
> what the actual bug was.
>
The bug was in rounding in the expression minCapacity = (3 * 
expectedMaxSize)/2.
Suppose, we want the expected size to be 11, then minCapacity becomes 
(int)(11 * 3 / 2) == 16.
The threshold is calculated later to be (int)(16 * 2 / 3) == 10, which 
is less than expected size 11.

To address the issue I combined the division by 2 with the rounding up 
to the nearest power of two.
I also took a chance to replace a while-loop with a single call to the 
highestOneBit method, which calculates exactly what we need here.

> The recursive call to put after a resize seems very sub-optimal as you 
> will re-search the map for the non-existent key. Can you not just 
> recompute the correct indices and do the store?
>
Okay, I replaced the recursive call with the index recomputation.

As was suggested by Jeff, I added a comment to the MAXIMUM_CAPACITY 
constant.

I also reverted some part of the changes to the resize() function, as it 
turned out that the new code failed to deal correctly with the table of 
maximum capacity.

I wanted to add checking of this behavior to the regression test, but 
faced an obstacle: I used reflection to make the MAXIMUM_CAPACITY 
constant smaller, so it wouldn't be needed to insert 2**29 element to 
fill the table up. The debugger was showing that the constant was 
changed, but the old value was still used in the conditions.

Currently I commented this test out. If anyone could suggest me how I 
can properly change MAXIMUM_CAPACITY in this situation, it would be very 
appreciated.

Here is the updated webrev:
http://cr.openjdk.java.net/~igerasim/6904367/2/webrev/

Would you please help review it?

Sincerely yours,
Ivan.

> Alternatively use the original code and if an exception occurs on 
> resize then simply undo the "put". I'm always worried that inverting 
> the behaviour like you will have some unexpected side effect somewhere 
> - this code has been like this for a very, very long time.
>
> Cheers,
> David
>
> On 4/07/2014 5:38 AM, Ivan Gerasimov wrote:
>> Thank you Jeff!
>>
>>
>> On 03.07.2014 23:07, Jeff Hain wrote:
>>>
>>> Hi.
>>>
>>>
>>> >WEBREV: http://cr.openjdk.java.net/~igerasim/6904367/0/webrev/
>>> <http://cr.openjdk.java.net/%7Eigerasim/6904367/0/webrev/>
>>>
>>> The "while" loop in put(...) supposes that there is at least one free
>>> slot,
>>> which was the case before (that could be added as comment).
>>>
>>> Now if you try to go past max capacity, instead of getting an
>>> IllegalStateException,
>>> you get an infinite loop.
>>>
>> Yes, you're right!
>>
>>> It's easy to test with a loop of 1000 puts and MAX_CAPACITY = 1<<8
>>> (=256, needs to be larger than DEFAULT_CAPACITY, else it can be
>>> "ignored").
>>> With previous version you get IllegalStateException on trying to add
>>> 255th mapping
>>> (on the resize that occurs when just-after-put-size is 255 >=
>>> threshold = 255),
>>> and with new version you get infinite loop on trying to add 257th
>>> mapping.
>>>
>>> Solutions I see would be adding a throw if size >= MAX_CAPACITY
>>> before the loop,
>>>
>> This would break the case when an existing key is added to the already
>> full table.
>> Moreover, the full table without a single empty slot could cause an
>> infinite looping in get(), remove(), etc.
>>
>>> or not adding that overhead and instead throwing when
>>> "size >= MAX_CAPACITY-1" instead of when "size >= MAX_CAPACITY".
>>>
>>
>> This seems appropriate.
>> With the current implementation we can only put MAX_CAPACITY-1 elements
>> anyway.
>>
>>> I would also rather use "==" over ">=" for these tests, to underline
>>> the fact
>>> that size is not supposed to be larger, but there might be some
>>> reasons not to.
>>>
>> I think it makes the code a bit more stable from the perspective of the
>> future changes.
>>
>> Here's the updated webrev:
>> http://cr.openjdk.java.net/~igerasim/6904367/1/webrev/
>>
>> Sincerely yours,
>> Ivan
>>
>>
>>>
>>> -Jeff
>>>
>>>
>>>
>>
>
>