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

[Peter Levart]

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/

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