Mercurial > hg > openjdk > bsd-port > jdk
changeset 8815:23e15121a4a6
6904367: (coll) IdentityHashMap is resized before exceeding the expected maximum size
Reviewed-by: plevart, martin
author | igerasim |
---|---|
date | Thu, 23 Nov 2017 19:50:37 +0000 |
parents | 72f71c6b2bbc |
children | bc316611d450 |
files | src/share/classes/java/util/IdentityHashMap.java test/java/util/IdentityHashMap/Capacity.java |
diffstat | 2 files changed, 288 insertions(+), 66 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/util/IdentityHashMap.java Thu Nov 23 19:33:26 2017 +0000 +++ b/src/share/classes/java/util/IdentityHashMap.java Thu Nov 23 19:50:37 2017 +0000 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2000, 2011, 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 @@ -24,7 +24,6 @@ */ package java.util; -import java.io.*; /** * This class implements the <tt>Map</tt> interface with a hash table, using @@ -69,7 +68,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 @@ -155,6 +154,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; @@ -176,11 +179,6 @@ private transient int modCount; /** - * The next size value at which to resize (capacity * load factor). - */ - private transient int threshold; - - /** * Value representing null keys inside tables. */ private static final Object NULL_KEY = new Object(); @@ -224,27 +222,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)); } /** @@ -257,7 +246,6 @@ // assert initCapacity >= MINIMUM_CAPACITY; // assert initCapacity <= MAXIMUM_CAPACITY; - threshold = (initCapacity * 2)/3; table = new Object[2 * initCapacity]; } @@ -423,51 +411,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) { - 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]; @@ -483,6 +478,7 @@ } } table = newTable; + return true; } /** @@ -497,8 +493,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()); @@ -534,7 +530,6 @@ return null; i = nextKeyIndex(i, len); } - } /** @@ -1168,8 +1163,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 @@ -1197,8 +1192,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 { @@ -1207,9 +1202,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++) { @@ -1224,7 +1220,7 @@ * update modCount, etc. */ private void putForCreate(K key, V value) - throws IOException + throws java.io.StreamCorruptedException { K k = (K)maskNull(key); Object[] tab = table;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/IdentityHashMap/Capacity.java Thu Nov 23 19:50:37 2017 +0000 @@ -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); + } +}