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

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Jul 8 11:53:02 UTC 2014

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 <= MAXIMUMCAPACITY / 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 == MAXIMUMCAPACITY - 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 == MAXIMUMCAPACITY - 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 * MAXIMUMCAPACITY) { // 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 * MAXIMUMCAPACITY) { // 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 == MAXIMUMCAPACITY - 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 == MAXIMUMCAPACITY - 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 * MAXIMUMCAPACITY) { // 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 * MAXIMUMCAPACITY) { // 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.

More information about the core-libs-dev mailing list