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

[David Holmes]

Hi Ivan,

I find the change to capacity somewhat obfuscating and I can't see what 
the actual bug was.

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?

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