Agree. I also wonder why we just use one buffer. On linux 32, with -Xmx1024m, I have tried to new a identity hash map about the size Integer.MAX_VALUE / 95 by sun 1.6. Bigger size will cause OutofMemory Exception. I believe with a power machine and 64bit system, we can create a identity hash map with much bigger size.
According to the original patch, size bitween 805306367 to Integer.MAX_VALUE will cause overflow, and what we returned is not the right size. Only raising the OutofMemoryException will make our code right. On Fri, May 15, 2009 at 11:56 PM, Sian January <[email protected]>wrote: > Hi Charles, > > Thanks for explaining the issue a bit better. Your patch looks like > it could be a good solution, but I'm wondering if there's a reason why > only one array was used in the first place (maybe performance?). It > would also be good to have some more tests with a range of large > values to check that we do the same as the RI in all situations before > making such a big change - as you say, if the previous fix was a > workaround for one test case and wasn't right then one test case > probably isn't enough. > > Thanks, > > Sian > > 2009/5/15 Charles Lee <[email protected]>: > > Here is my patch. What about this? > > > > diff --git modules/luni/src/main/java/java/util/IdentityHashMap.java > > modules/luni/src/main/java/java/util/IdentityHashMap.java > > index 034ee07..bc26fa5 100644 > > --- modules/luni/src/main/java/java/util/IdentityHashMap.java > > +++ modules/luni/src/main/java/java/util/IdentityHashMap.java > > @@ -44,10 +44,16 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > private static final long serialVersionUID = 8188218128353913216L; > > > > /* > > - * The internal data structure to hold key value pairs This array > holds > > keys > > - * and values in an alternating fashion. > > + * The internal data structure to hold key. This array holds keys > > + * in an alternating fashion. > > */ > > - transient Object[] elementData; > > + transient Object[] keyData; > > + > > + /* > > + * The internal data structure to hold value. This array holds > values > > + * in an alternating fashion. > > + */ > > + transient Object[] valueData; > > > > /* Actual number of key-value pairs. */ > > int size; > > @@ -65,7 +71,10 @@ public class IdentityHashMap<K, V> extends > AbstractMap<K, > > V> implements > > private static final int DEFAULT_MAX_SIZE = 21; > > > > /* Default load factor of 0.75; */ > > - private static final int loadFactor = 7500; > > + private static final int loadFactorNumerator = 3; > > + private static final int loadFactorDenominator = 4; > > + /* 1610612735 */ > > + private static final int barrier = (int)((long)Integer.MAX_VALUE * > > loadFactorNumerator / loadFactorDenominator); > > > > /* > > * modification count, to keep track of structural modifications > > between the > > @@ -136,10 +145,10 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > } > > > > public boolean hasNext() { > > - while (position < associatedMap.elementData.length) { > > + while (position < associatedMap.keyData.length) { > > // if this is an empty spot, go to the next one > > - if (associatedMap.elementData[position] == null) { > > - position += 2; > > + if (associatedMap.keyData[position] == null) { > > + position++; > > } else { > > return true; > > } > > @@ -162,7 +171,7 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > IdentityHashMapEntry<KT, VT> result = associatedMap > > .getEntry(position); > > lastPosition = position; > > - position += 2; > > + position++; > > > > canRemove = true; > > return type.get(result); > > @@ -175,7 +184,7 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > } > > > > canRemove = false; > > - > associatedMap.remove(associatedMap.elementData[lastPosition]); > > + associatedMap.remove(associatedMap.keyData[lastPosition]); > > position = lastPosition; > > expectedModCount++; > > } > > @@ -252,7 +261,9 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > if (maxSize >= 0) { > > this.size = 0; > > threshold = getThreshold(maxSize); > > - elementData = newElementArray(computeElementArraySize()); > > + int length = computeElementArraySize(); > > + keyData = new Object[length]; > > + valueData = new Object[length]; > > } else { > > throw new IllegalArgumentException(); > > } > > @@ -265,18 +276,12 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > } > > > > private int computeElementArraySize() { > > - return (int) (((long) threshold * 10000) / loadFactor) * 2; > > - } > > - > > - /** > > - * Create a new element array > > - * > > - * @param s > > - * the number of elements > > - * @return Reference to the element array > > - */ > > - private Object[] newElementArray(int s) { > > - return new Object[s]; > > + if (threshold >= barrier) { > > + // Could not apply for the factor, we return the max value > > + return Integer.MAX_VALUE; > > + } else { > > + return (int) (((long) threshold * loadFactorDenominator) / > > loadFactorNumerator); > > + } > > } > > > > /** > > @@ -307,8 +312,9 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > @Override > > public void clear() { > > size = 0; > > - for (int i = 0; i < elementData.length; i++) { > > - elementData[i] = null; > > + for (int i = 0; i < keyData.length; i++) { > > + keyData[i] = null; > > + valueData[i] = null; > > } > > modCount++; > > } > > @@ -326,8 +332,8 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > key = NULL_OBJECT; > > } > > > > - int index = findIndex(key, elementData); > > - return elementData[index] == key; > > + int index = findIndex(key, keyData); > > + return keyData[index] == key; > > } > > > > /** > > @@ -345,8 +351,8 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > value = NULL_OBJECT; > > } > > > > - for (int i = 1; i < elementData.length; i = i + 2) { > > - if (elementData[i] == value) { > > + for (int i = 1; i < valueData.length; i++) { > > + if (valueData[i] == value) { > > return true; > > } > > } > > @@ -366,10 +372,10 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > key = NULL_OBJECT; > > } > > > > - int index = findIndex(key, elementData); > > + int index = findIndex(key, keyData); > > > > - if (elementData[index] == key) { > > - Object result = elementData[index + 1]; > > + if (keyData[index] == key) { > > + Object result = valueData[index]; > > return massageValue(result); > > } > > > > @@ -381,8 +387,8 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > key = NULL_OBJECT; > > } > > > > - int index = findIndex(key, elementData); > > - if (elementData[index] == key) { > > + int index = findIndex(key, keyData); > > + if (keyData[index] == key) { > > return getEntry(index); > > } > > > > @@ -395,8 +401,8 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > */ > > @SuppressWarnings("unchecked") > > private IdentityHashMapEntry<K, V> getEntry(int index) { > > - Object key = elementData[index]; > > - Object value = elementData[index + 1]; > > + Object key = keyData[index]; > > + Object value = valueData[index]; > > > > if (key == NULL_OBJECT) { > > key = null; > > @@ -424,7 +430,7 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > */ > > break; > > } > > - index = (index + 2) % length; > > + index = (index + 1) % length; > > } > > return index; > > } > > @@ -455,24 +461,24 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > _value = NULL_OBJECT; > > } > > > > - int index = findIndex(_key, elementData); > > + int index = findIndex(_key, keyData); > > > > // if the key doesn't exist in the table > > - if (elementData[index] != _key) { > > + if (keyData[index] != _key) { > > modCount++; > > if (++size > threshold) { > > rehash(); > > - index = findIndex(_key, elementData); > > + index = findIndex(_key, keyData); > > } > > > > // insert the key and assign the value to null initially > > - elementData[index] = _key; > > - elementData[index + 1] = null; > > + keyData[index] = _key; > > + valueData[index] = null; > > } > > > > // insert value to where it needs to go, return the old value > > - Object result = elementData[index + 1]; > > - elementData[index + 1] = _value; > > + Object result = valueData[index]; > > + valueData[index] = _value; > > > > return massageValue(result); > > } > > @@ -493,26 +499,29 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > } > > > > private void rehash() { > > - int newlength = elementData.length << 1; > > + int newlength = keyData.length << 1; > > if (newlength == 0) { > > newlength = 1; > > } > > - Object[] newData = newElementArray(newlength); > > - for (int i = 0; i < elementData.length; i = i + 2) { > > - Object key = elementData[i]; > > + Object[] newKeyData = new Object[newlength]; > > + Object[] newValueData = new Object[newlength]; > > + for (int i = 0; i < keyData.length; i++) { > > + Object key = keyData[i]; > > if (key != null) { > > // if not empty > > - int index = findIndex(key, newData); > > - newData[index] = key; > > - newData[index + 1] = elementData[i + 1]; > > + int index = findIndex(key, newKeyData); > > + newKeyData[index] = key; > > + newValueData[index] = valueData[i]; > > } > > } > > - elementData = newData; > > + keyData = newKeyData; > > + valueData = newValueData; > > computeMaxSize(); > > } > > > > private void computeMaxSize() { > > - threshold = (int) ((long) (elementData.length / 2) * loadFactor > / > > 10000); > > + // very weird > > + threshold = (int) ((long) keyData.length * loadFactorNumerator / > > loadFactorDenominator); > > } > > > > /** > > @@ -532,21 +541,22 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > boolean hashedOk; > > int index, next, hash; > > Object result, object; > > - index = next = findIndex(key, elementData); > > + index = next = findIndex(key, keyData); > > > > - if (elementData[index] != key) { > > + if (keyData[index] != key) { > > return null; > > } > > > > // store the value for this key > > - result = elementData[index + 1]; > > + result = valueData[index]; > > > > // shift the following elements up if needed > > // until we reach an empty spot > > - int length = elementData.length; > > + int length = keyData.length; > > + boolean forward = false; > > while (true) { > > - next = (next + 2) % length; > > - object = elementData[next]; > > + next = (next + 1) % length; > > + object = keyData[next]; > > if (object == null) { > > break; > > } > > @@ -559,19 +569,24 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > hashedOk = hashedOk && (hash <= next); > > } > > if (!hashedOk) { > > - elementData[index] = object; > > - elementData[index + 1] = elementData[next + 1]; > > + keyData[index] = object; > > + valueData[index] = valueData[next]; > > index = next; > > + keyData[next] = null; > > + valueData[next] = null; > > + forward = true; > > } > > } > > + > > + if (!forward) { > > + // no other has been forwarded, we should delete the key and > > value > > + keyData[index] = null; > > + valueData[index] = null; > > + } > > > > size--; > > modCount++; > > > > - // clear both the key and the value > > - elementData[index] = null; > > - elementData[index + 1] = null; > > - > > return massageValue(result); > > } > > > > @@ -783,7 +798,9 @@ public class IdentityHashMap<K, V> extends > > AbstractMap<K, V> implements > > stream.defaultReadObject(); > > int savedSize = stream.readInt(); > > threshold = getThreshold(DEFAULT_MAX_SIZE); > > - elementData = newElementArray(computeElementArraySize()); > > + int length = computeElementArraySize(); > > + keyData = new Object[length]; > > + valueData = new Object[length]; > > for (int i = savedSize; --i >= 0;) { > > K key = (K) stream.readObject(); > > put(key, (V) stream.readObject()); > > > > > > > > > > On Fri, May 15, 2009 at 8:36 PM, Charles Lee <[email protected]> > wrote: > > > >> Hi, Sian. > >> > >> It seems that this patch is a workaround about the testcase. What if our > >> user really can malloc Integer.MAX_VALUE memorys to hold the hashmap? > And > >> the size is also not right if we just negate the overflow one, it will > cause > >> the potential problem. > >> > >> The root cause of this problem is because we just use one buffer to hold > >> both key and value. What about using two buffers, split the key and > value > >> pair into seperate buffers? > >> > >> > >> On Fri, May 15, 2009 at 5:08 PM, <[email protected]> wrote: > >> > >>> Author: sjanuary > >>> Date: Fri May 15 09:08:28 2009 > >>> New Revision: 775060 > >>> > >>> URL: http://svn.apache.org/viewvc?rev=775060&view=rev > >>> Log: > >>> Apply patch for HARMONY-6204 ([classlib][luni] > >>> java.util.IdentityHashMap.<init>(BigNumber) throws a > >>> NegativeArraySizeException while RI throws OutOfMemoryError) > >>> > >>> Modified: > >>> > >>> > > harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java > >>> > >>> > > harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java > >>> > >>> Modified: > >>> > harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java > >>> URL: > >>> > http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java?rev=775060&r1=775059&r2=775060&view=diff > >>> > >>> > ============================================================================== > >>> --- > >>> > harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java > >>> (original) > >>> +++ > >>> > harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java > >>> Fri May 15 09:08:28 2009 > >>> @@ -267,7 +267,10 @@ > >>> } > >>> > >>> private int computeElementArraySize() { > >>> - return (int) (((long) threshold * 10000) / loadFactor) * 2; > >>> + int arraySize = (int) (((long) threshold * 10000) / > loadFactor) * > >>> 2; > >>> + // ensure arraySize is positive, the above cast from long to > int > >>> type > >>> + // leads to overflow and negative arraySize if threshold is > too > >>> big > >>> + return arraySize < 0 ? -arraySize : arraySize; > >>> } > >>> > >>> /** > >>> > >>> Modified: > >>> > harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java > >>> URL: > >>> > http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java?rev=775060&r1=775059&r2=775060&view=diff > >>> > >>> > ============================================================================== > >>> --- > >>> > harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java > >>> (original) > >>> +++ > >>> > harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java > >>> Fri May 15 09:08:28 2009 > >>> @@ -115,6 +115,15 @@ > >>> assertEquals("Size should be 0", 0, hm2.size()); > >>> } > >>> > >>> + public void test_IdentityHashMap_Constructor_BigSize() { > >>> + try { > >>> + new IdentityHashMap(Integer.MAX_VALUE); > >>> + fail("should throw OutOfMemoryError"); > >>> + } catch (OutOfMemoryError e) { > >>> + // Expected > >>> + } > >>> + } > >>> + > >>> /** > >>> * @tests java.util.IdentityHashMap#clear() > >>> */ > >>> > >>> > >>> > >> > >> > >> -- > >> Yours sincerely, > >> Charles Lee > >> > >> > > > > > > -- > > Yours sincerely, > > Charles Lee > > > > > > -- > Unless stated otherwise above: > IBM United Kingdom Limited - Registered in England and Wales with number > 741598. > Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU > -- Yours sincerely, Charles Lee
