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

Tue, 08 Jul 2014 04:54:08 -0700 


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.


http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.02/
I don't think there's a danger of overflow in capacity() since (expectedMaxSize + (expectedMaxSize << 1)) is evaluated only if expectedMaxSize <= MAXIMUM_CAPACITY / 3; 

Here's a diff to latest Martin's 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 13:05:46.351810826 +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,454 ----

          if (size == MAXIMUM_CAPACITY - 1)
              throw new IllegalStateException("Capacity exhausted.");
+
+ if (size >= len / 3 && 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];

--- 457,473 ----
       *
       * @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 ****
--- 485,491 ----
              }
          }
          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())
--- 500,506 ----
          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())


Regards, Peter

On 07/08/2014 12:41 PM, 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/

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

Reply via email to