6904367: (coll) IdentityHashMap is resized before exceeding the expected maximum size
Reviewed-by: plevart, martin
--- a/jdk/src/share/classes/java/util/IdentityHashMap.java Fri Jul 11 14:06:42 2014 -0700
+++ b/jdk/src/share/classes/java/util/IdentityHashMap.java Sat Jul 12 04:15:56 2014 +0400
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -25,7 +25,6 @@
package java.util;
-import java.io.*;
import java.lang.reflect.Array;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
@@ -74,7 +73,7 @@
* maximum size and the number of buckets is unspecified.
*
* <p>If the size of the map (the number of key-value mappings) sufficiently
- * exceeds the expected maximum size, the number of buckets is increased
+ * exceeds the expected maximum size, the number of buckets is increased.
* Increasing the number of buckets ("rehashing") may be fairly expensive, so
* it pays to create identity hash maps with a sufficiently large expected
* maximum size. On the other hand, iteration over collection views requires
@@ -160,6 +159,10 @@
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<29.
+ *
+ * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
+ * because it has to have at least one slot with the key == null
+ * in order to avoid infinite loops in get(), put(), remove()
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;
@@ -181,11 +184,6 @@
transient int modCount;
/**
- * The next size value at which to resize (capacity * load factor).
- */
- private transient int threshold;
-
- /**
* Value representing null keys inside tables.
*/
static final Object NULL_KEY = new Object();
@@ -229,27 +227,18 @@
}
/**
- * Returns the appropriate capacity for the specified expected maximum
- * size. Returns the smallest power of two between MINIMUM_CAPACITY
- * and MAXIMUM_CAPACITY, inclusive, that is greater than
- * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
- * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
- * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
+ * Returns the appropriate capacity for the given expected maximum size.
+ * Returns the smallest power of two between MINIMUM_CAPACITY and
+ * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
+ * expectedMaxSize)/2, if such a number exists. Otherwise returns
+ * MAXIMUM_CAPACITY.
*/
- private int capacity(int expectedMaxSize) {
- // Compute min capacity for expectedMaxSize given a load factor of 2/3
- int minCapacity = (3 * expectedMaxSize)/2;
-
- // Compute the appropriate capacity
- int result;
- if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
- result = MAXIMUM_CAPACITY;
- } else {
- result = MINIMUM_CAPACITY;
- while (result < minCapacity)
- result <<= 1;
- }
- return result;
+ private static int capacity(int expectedMaxSize) {
+ // assert expectedMaxSize >= 0;
+ return
+ (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
+ (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
+ Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}
/**
@@ -262,7 +251,6 @@
// assert initCapacity >= MINIMUM_CAPACITY;
// assert initCapacity <= MAXIMUM_CAPACITY;
- threshold = (initCapacity * 2)/3;
table = new Object[2 * initCapacity];
}
@@ -429,52 +417,58 @@
* @see #containsKey(Object)
*/
public V put(K key, V value) {
- Object k = maskNull(key);
- Object[] tab = table;
- int len = tab.length;
- int i = hash(k, len);
+ final Object k = maskNull(key);
+
+ retryAfterResize: for (;;) {
+ final Object[] tab = table;
+ final int len = tab.length;
+ int i = hash(k, len);
- Object item;
- while ( (item = tab[i]) != null) {
- if (item == k) {
- @SuppressWarnings("unchecked")
- V oldValue = (V) tab[i + 1];
- tab[i + 1] = value;
- return oldValue;
+ for (Object item; (item = tab[i]) != null;
+ i = nextKeyIndex(i, len)) {
+ if (item == k) {
+ @SuppressWarnings("unchecked")
+ V oldValue = (V) tab[i + 1];
+ tab[i + 1] = value;
+ return oldValue;
+ }
}
- i = nextKeyIndex(i, len);
- }
+
+ final int s = size + 1;
+ // Use optimized form of 3 * s.
+ // Next capacity is len, 2 * current capacity.
+ if (s + (s << 1) > len && resize(len))
+ continue retryAfterResize;
- modCount++;
- tab[i] = k;
- tab[i + 1] = value;
- if (++size >= threshold)
- resize(len); // len == 2 * current capacity.
- return null;
+ modCount++;
+ tab[i] = k;
+ tab[i + 1] = value;
+ size = s;
+ return null;
+ }
}
/**
- * Resize the table to hold given capacity.
+ * Resizes the table if necessary to hold given capacity.
*
* @param newCapacity the new capacity, must be a power of two.
+ * @return whether a resize did in fact take place
*/
- private void resize(int newCapacity) {
+ 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
- if (threshold == MAXIMUM_CAPACITY-1)
+ if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
+ if (size == MAXIMUM_CAPACITY - 1)
throw new IllegalStateException("Capacity exhausted.");
- threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
- return;
+ return false;
}
if (oldLength >= newLength)
- return;
+ return false;
Object[] newTable = new Object[newLength];
- threshold = newLength / 3;
for (int j = 0; j < oldLength; j += 2) {
Object key = oldTable[j];
@@ -490,6 +484,7 @@
}
}
table = newTable;
+ return true;
}
/**
@@ -504,8 +499,8 @@
int n = m.size();
if (n == 0)
return;
- if (n > threshold) // conservatively pre-expand
- resize(capacity(n));
+ if (n > size)
+ resize(capacity(n)); // conservatively pre-expand
for (Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
@@ -542,7 +537,6 @@
return null;
i = nextKeyIndex(i, len);
}
-
}
/**
@@ -1266,8 +1260,8 @@
private static final long serialVersionUID = 8188218128353913216L;
/**
- * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
- * (i.e., serialize it).
+ * Saves the state of the <tt>IdentityHashMap</tt> instance to a stream
+ * (i.e., serializes it).
*
* @serialData The <i>size</i> of the HashMap (the number of key-value
* mappings) (<tt>int</tt>), followed by the key (Object) and
@@ -1295,8 +1289,8 @@
}
/**
- * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
- * deserialize it).
+ * Reconstitutes the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
+ * deserializes it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
@@ -1305,9 +1299,10 @@
// Read in size (number of Mappings)
int size = s.readInt();
-
- // Allow for 33% growth (i.e., capacity is >= 2* size()).
- init(capacity((size*4)/3));
+ if (size < 0)
+ throw new java.io.StreamCorruptedException
+ ("Illegal mappings count: " + size);
+ init(capacity(size));
// Read the keys and values, and put the mappings in the table
for (int i=0; i<size; i++) {
@@ -1324,7 +1319,7 @@
* update modCount, etc.
*/
private void putForCreate(K key, V value)
- throws IOException
+ throws java.io.StreamCorruptedException
{
Object k = maskNull(key);
Object[] tab = table;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/IdentityHashMap/Capacity.java Sat Jul 12 04:15:56 2014 +0400
@@ -0,0 +1,226 @@
+/*
+ * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import java.lang.reflect.Field;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Random;
+
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.*;
+
+/*
+ * @test
+ * @bug 6904367
+ * @summary IdentityHashMap reallocates storage when inserting expected
+ * number of elements
+ * @run testng Capacity
+ */
+
+@Test
+public class Capacity {
+ static final Field tableField;
+ static final Random random = new Random();
+ static final Object[][] sizesData;
+
+ @DataProvider(name="sizes", parallel = true)
+ public Object[][] sizesToTest() { return sizesData; }
+
+ static {
+ try {
+ tableField = IdentityHashMap.class.getDeclaredField("table");
+ tableField.setAccessible(true);
+ } catch (NoSuchFieldException e) {
+ throw new LinkageError("table", e);
+ }
+
+ ArrayList<Object[]> sizes = new ArrayList<>();
+ for (int size = 0; size < 200; size++)
+ sizes.add(new Object[] { size });
+
+ // some numbers known to demonstrate bug 6904367
+ for (int size : new int[] {682, 683, 1365, 2730, 2731, 5461})
+ sizes.add(new Object[] { size });
+
+ // a few more random sizes to try
+ for (int i = 0; i != 128; i++)
+ sizes.add(new Object[] { random.nextInt(5000) });
+
+ sizesData = sizes.toArray(new Object[0][]);
+ }
+
+ static int capacity(IdentityHashMap<?,?> map) {
+ try {
+ return ((Object[]) tableField.get(map)).length / 2;
+ } catch (Throwable t) {
+ throw new LinkageError("table", t);
+ }
+ }
+
+ static void assertCapacity(IdentityHashMap<?,?> map,
+ int expectedCapacity) {
+ assertEquals(capacity(map), expectedCapacity);
+ }
+
+ static void growUsingPut(IdentityHashMap<Object,Object> map,
+ int elementsToAdd) {
+ for (int i = 0; i < elementsToAdd; i++)
+ map.put(new Object(), new Object());
+ }
+
+ static void growUsingPutAll(IdentityHashMap<Object,Object> map,
+ int elementsToAdd) {
+ IdentityHashMap<Object,Object> other = new IdentityHashMap<>();
+ growUsingPut(other, elementsToAdd);
+ map.putAll(other);
+ }
+
+ static void growUsingRepeatedPutAll(IdentityHashMap<Object,Object> map,
+ int elementsToAdd) {
+ for (int i = 0; i < elementsToAdd; i++)
+ map.putAll(Collections.singletonMap(new Object(),
+ new Object()));
+ }
+
+ /**
+ * Checks that expected number of items can be inserted into
+ * the map without resizing of the internal storage
+ */
+ @Test(dataProvider = "sizes")
+ public void canInsertExpectedItemsWithoutResizing(int size)
+ throws Throwable {
+ // First try growing using put()
+ IdentityHashMap<Object,Object> m = new IdentityHashMap<>(size);
+ int initialCapacity = capacity(m);
+ growUsingPut(m, size);
+ assertCapacity(m, initialCapacity);
+
+ // Doubling from the expected size will cause exactly one
+ // resize, except near minimum capacity.
+ if (size > 1) {
+ growUsingPut(m, size);
+ assertCapacity(m, 2 * initialCapacity);
+ }
+
+ // Try again, growing with putAll()
+ m = new IdentityHashMap<>(size);
+ initialCapacity = capacity(m);
+ growUsingPutAll(m, size);
+ assertCapacity(m, initialCapacity);
+
+ // Doubling from the expected size will cause exactly one
+ // resize, except near minimum capacity.
+ if (size > 1) {
+ growUsingPutAll(m, size);
+ assertCapacity(m, 2 * initialCapacity);
+ }
+ }
+
+ /**
+ * Given the expected size, computes such a number N of items that
+ * inserting (N+1) items will trigger resizing of the internal storage
+ */
+ static int threshold(int size) throws Throwable {
+ IdentityHashMap<Object,Object> m = new IdentityHashMap<>(size);
+ int initialCapacity = capacity(m);
+ while (capacity(m) == initialCapacity)
+ growUsingPut(m, 1);
+ return m.size() - 1;
+ }
+
+ /**
+ * Checks that inserting (threshold+1) item causes resizing
+ * of the internal storage
+ */
+ @Test(dataProvider = "sizes")
+ public void passingThresholdCausesResize(int size) throws Throwable {
+ final int threshold = threshold(size);
+ IdentityHashMap<Object,Object> m = new IdentityHashMap<>(threshold);
+ int initialCapacity = capacity(m);
+
+ growUsingPut(m, threshold);
+ assertCapacity(m, initialCapacity);
+
+ growUsingPut(m, 1);
+ assertCapacity(m, 2 * initialCapacity);
+ }
+
+ /**
+ * Checks that 4 methods of requiring capacity lead to the same
+ * internal capacity, unless sized below default capacity.
+ */
+ @Test(dataProvider = "sizes")
+ public void differentGrowthPatternsResultInSameCapacity(int size)
+ throws Throwable {
+ if (size < 21) // 21 is default maxExpectedSize
+ return;
+
+ IdentityHashMap<Object,Object> m;
+ m = new IdentityHashMap<Object,Object>(size);
+ int capacity1 = capacity(m);
+
+ m = new IdentityHashMap<>();
+ growUsingPut(m, size);
+ int capacity2 = capacity(m);
+
+ m = new IdentityHashMap<>();
+ growUsingPutAll(m, size);
+ int capacity3 = capacity(m);
+
+ m = new IdentityHashMap<>();
+ growUsingRepeatedPutAll(m, size);
+ int capacity4 = capacity(m);
+
+ if (capacity1 != capacity2 ||
+ capacity2 != capacity3 ||
+ capacity3 != capacity4)
+ throw new AssertionError("Capacities not equal: "
+ + capacity1 + " "
+ + capacity2 + " "
+ + capacity3 + " "
+ + capacity4);
+ }
+
+ public void defaultExpectedMaxSizeIs21() {
+ assertCapacity(new IdentityHashMap<Long,Long>(), 32);
+ assertCapacity(new IdentityHashMap<Long,Long>(21), 32);
+ }
+
+ public void minimumCapacityIs4() {
+ assertCapacity(new IdentityHashMap<Long,Long>(0), 4);
+ assertCapacity(new IdentityHashMap<Long,Long>(1), 4);
+ assertCapacity(new IdentityHashMap<Long,Long>(2), 4);
+ assertCapacity(new IdentityHashMap<Long,Long>(3), 8);
+ }
+
+ @Test(enabled = false)
+ /** needs too much memory to run normally */
+ public void maximumCapacityIs2ToThe29() {
+ assertCapacity(new IdentityHashMap<Long,Long>(Integer.MAX_VALUE),
+ 1 << 29);
+ }
+}