harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Charles Lee <littlee1...@gmail.com>
Subject Re: svn commit: r775060 - in /harmony/enhanced/classlib/trunk/modules/luni/src: main/java/java/util/IdentityHashMap.java test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
Date Fri, 15 May 2009 16:11:00 GMT
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
<sianjanuary@googlemail.com>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 <littlee1032@gmail.com>:
> > 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 <littlee1032@gmail.com>
> 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, <sjanuary@apache.org> 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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message