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

Peter Levart peter.levart at gmail.com
Tue Jul 8 12:20:10 UTC 2014

• Previous message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Next message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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

•     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())

• Previous message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Next message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the core-libs-dev mailing list