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

[Peter Levart]

On 07/08/2014 01:53 PM, Ivan Gerasimov wrote:
> On 08.07.2014 15:25, Peter Levart wrote:
>> Hi again,
>>
>> Here's a version with (3*size > len) replaced with (size > len/3) as 
>> suggested by Ivan Gerasimov to avoid overflow and also fixed if block 
>> if put() that enclosed too much code (in my changed version of 
>> Martin's latest webrev):
>>
> It shouldn't be needed, since size < MAXIMUM_CAPACITY-1 at this point.

That's right. Not in put(). But in putAll() it can overflow, since the 
argument Map can be of any size that fits in int... So here's my 3rd 
variation of Martin's latest version:

http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.03/


And a diff to Martin's latest 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 
14:07:57.782843612 +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,455 ----

           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 && 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];

--- 458,474 ----
        *
        * @param newCapacity the new capacity, must be a power of two.
        */
!     private boolean resize(int newCapacity) {
           // assert (newCapacity & -newCapacity) == newCapacity; // 
power of 2

           Object[] oldTable = table;
           int oldLength = oldTable.length;
           if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any 
further
!             return false;
           }
+         int newLength = newCapacity * 2;
           if (oldLength >= newLength)
!             return false;

           Object[] newTable = new Object[newLength];

***************
*** 480,485 ****
--- 486,492 ----
               }
           }
           table = newTable;
+         return true;
       }

       /**
***************
*** 494,500 ****
           int n = m.size();
           if (n == 0)
               return;
!         if (n + (n << 1) > table.length) // conservatively pre-expand
               resize(capacity(n));

           for (Entry<? extends K, ? extends V> e : m.entrySet())
--- 501,507 ----
           int n = m.size();
           if (n == 0)
               return;
!         if (n > table.length / 3) // conservatively pre-expand
               resize(capacity(n));

           for (Entry<? extends K, ? extends V> e : m.entrySet())