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

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Jul 8 13:00:30 UTC 2014

On 08.07.2014 14:41, 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/

But isn't it post-insert-resize vs pre-insert-resize problem Doug mentioned above? I've tested a similar fix and it showed slow down of the put() operation.

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