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

[Ivan Gerasimov]

On 08.07.2014 14:41, Peter Levart wrote:
> On 07/08/2014 12:12 PM, Peter Levart wrote:
>> On 07/08/2014 09:33 AM, Martin Buchholz wrote:
>>> I've updated the webrev
>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ 
>>>
>>> It now has all my TODOs done.
>>> The test case has been testng-ified.
>>
>> Hi Martin,
>>
>> What happened to the desire that when OOME is thrown on resizing, IHM 
>> is left unchanged?
>>
>> Regards, Peter
>
> Hi Martin,
>
> I took your latest version of the patch and modified it a little:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.01/
>

But isn't it post-insert-resize vs pre-insert-resize problem Doug 
mentioned above?
I've tested a similar fix and it showed slow down of the put() operation.


> Here's a diff to your version:
>
> *** src/share/classes/java/util/IdentityHashMap.java.mb 2014-07-08 
> 12:37:57.267916926 +0200
> --- src/share/classes/java/util/IdentityHashMap.java    2014-07-08 
> 12:34:25.739767669 +0200
> ***************
> *** 437,449 ****
>
>           if (size == MAXIMUM_CAPACITY - 1)
>               throw new IllegalStateException("Capacity exhausted.");
> !         modCount++;
> !         tab[i] = k;
> !         tab[i + 1] = value;
> ! size++;
> !         int x = size + (size << 1); // Optimized form of 3 * size
> !         if (x > len)
> !             resize(len); // len == 2 * current capacity.
>           return null;
> }
>
> --- 437,457 ----
>
>           if (size == MAXIMUM_CAPACITY - 1)
>               throw new IllegalStateException("Capacity exhausted.");
> !
> !         int x = size + (size << 1) + 3; // Optimized form of 3 * 
> (size + 1)
> !         if (x > len) {
> !             if (resize(len)) { // len == 2 * current capacity.
> !                 tab = table;
> !                 len = tab.length;
> !                 i = hash(key, len);
> !                 while (tab[i] != null)
> !                     i = nextKeyIndex(i, len);
> !             }
> !             modCount++;
> !             tab[i] = k;
> !             tab[i + 1] = value;
> !             size++;
> !         }
>           return null;
>       }
>
> ***************
> *** 452,468 ****
>        *
>        * @param newCapacity the new capacity, must be a power of two.
>        */
> !     private void resize(int newCapacity) {
>           // assert (newCapacity & -newCapacity) == newCapacity; // 
> power of 2
>           int newLength = newCapacity * 2;
>
>           Object[] oldTable = table;
>           int oldLength = oldTable.length;
>           if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any 
> further
> !             return;
>           }
>           if (oldLength >= newLength)
> !             return;
>
>           Object[] newTable = new Object[newLength];
>
> --- 460,476 ----
>        *
>        * @param newCapacity the new capacity, must be a power of two.
>        */
> !     private boolean resize(int newCapacity) {
>           // assert (newCapacity & -newCapacity) == newCapacity; // 
> power of 2
>           int newLength = newCapacity * 2;
>
>           Object[] oldTable = table;
>           int oldLength = oldTable.length;
>           if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any 
> further
> !             return false;
>           }
>           if (oldLength >= newLength)
> !             return false;
>
>           Object[] newTable = new Object[newLength];
>
> ***************
> *** 480,485 ****
> --- 488,494 ----
>               }
>           }
>           table = newTable;
> +         return true;
>       }
>
>       /**
>
>
> Regards, Peter
>
>>
>>>
>>> On Mon, Jul 7, 2014 at 6:54 PM, Ivan Gerasimov 
>>> <ivan.gerasimov at oracle.com>
>>> wrote:
>>>
>>>> Unfortunately, x + x << 1 causes the same overflow bug as 3*x:
>>>>
>>> x + (x << 1) is merely supposed to be possibly more efficient than 3*x.
>>>
>>>
>>>> (int)(1431655766 + 1431655766 << 1) == 2
>>>>
>>> OK, I think my latest version doesn't have any overflow bugs.
>>
>
>
>