RFR : 8016446 : (m) Add override forEach/replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap

Mike Duigou mike.duigou at oracle.com
Mon Jun 17 23:30:13 UTC 2013


On Jun 17 2013, at 03:09 , Paul Sandoz wrote:

> On Jun 14, 2013, at 11:57 PM, Mike Duigou <mike.duigou at oracle.com> wrote:
>> I have updated the webrev again. In addition to moving the modification checks to be consistently after the operation for the most complete "fast-fail" behaviour I've also slightly enhanced the Map default to detect ISE thrown by setValue as a CME condition.
>> 
>> http://cr.openjdk.java.net/~mduigou/JDK-8016446/2/webrev/
>> 
> 
> There are some places where the indentation looks wonky e.g. HashMap & LinkedHashMap changes.

I have restyled all of the diffs to make sure they are clean.

> 
> The LinkedHashMap.forEach/replaceAll methods are checking modCount and throwing CME before the action is called.

Corrected.

> 
> The WeakHashMap.replaceAll method is checking the modCount per bucket, not-per element.

Corrected.

> 
> Are there existing tests for the overriding methods?

I had believed so in Map/Defaults.java but replaceAll was absent. Now corrected in updated webrev

http://cr.openjdk.java.net/~mduigou/JDK-8016446/3/webrev/

I had to add the improved default for ConcurrentMap which was present in the lambda repo in order to have correct behaviour. Since getOrDefault is already in ConcurrentMap I will include this but we have to be careful when we do a jsr 166 syncup to make sure that the defaults don't get lost.

Mike


> Otherwise looks OK.
> 
> Paul.
> 
> 
>> For interference detection the strategy I am advocating is :
>> 
>> - serial non-stream operations (Collection.forEach/Iterator.forEachRemaining): per-element post-operation ("fast-fail", "best-efforts"). As Remi has pointed out the failure modes for collection.forEach() and for(:collection) will differ and it is a conscious choice to provide superior fast-fail than to match behaviour.
>> 
>> - stream terminal operations, both serial and parallel : at completion if at all. Having the serial and parallel stream interference detection behaviours consistent is prioritized over making serial stream behaviour match behaviour of non-stream iteration methods.
>> 
>> Mike
>> 
>> On Jun 12 2013, at 22:28 , Mike Duigou wrote:
>> 
>>> I have updated my webrev with Remi's improvements and some other improvements to the fast-fail concurrent modification checking.
>>> 
>>> Revised webrev:
>>> 
>>> http://cr.openjdk.java.net/~mduigou/JDK-8016446/1/webrev/
>>> 
>>> Mike
>>> 
>>> 
>>> On Jun 12 2013, at 15:49 , Remi Forax wrote:
>>> 
>>>> On 06/12/2013 11:23 PM, Mike Duigou wrote:
>>>>> Hello all;
>>>>> 
>>>>> This patch adds optimized implementations of Map.forEach and Map.replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap
>>>>> 
>>>>> http://cr.openjdk.java.net/~mduigou/JDK-8016446/0/webrev/
>>>>> 
>>>>> The implementations traverse the map more efficiently than the default iterator implementation and sometimes avoid creation of transient Map.Entry instances. The fast-fail behaviour of the default implementation is retained.
>>>>> 
>>>>> Mike
>>>> 
>>>> Hi Mike,
>>>> funnily I was writing HashMap.forEach/LinkedHashMap.forEach at the same time.
>>>> (you need also to override forEach in LinkedHashMap because the one you inherits from HashMap doesn't use the linked list of entries).
>>>> 
>>>> My code is slightly different from yours because I've moved the cases where the item is a red/black tree out of the fast path
>>>> (the tree is created either if you are unlucky, if hashCode is badly written or if someone forge keys to have collisions)
>>>> and does the modCount check for each element because a call to the consumer can change the underlying map
>>>> so you can not do a modCount check only at the end.
>>>> 
>>>> RĂ©mi
>>>> 
>>>> Here is the diff.
>>>> diff -r 6df79b7bae6f src/share/classes/java/util/HashMap.java
>>>> --- a/src/share/classes/java/util/HashMap.java    Wed Jun 12 09:44:34 2013 +0100
>>>> +++ b/src/share/classes/java/util/HashMap.java    Thu Jun 13 00:46:05 2013 +0200
>>>> @@ -28,6 +28,7 @@
>>>> import java.io.*;
>>>> import java.lang.reflect.ParameterizedType;
>>>> import java.lang.reflect.Type;
>>>> +import java.util.function.BiConsumer;
>>>> import java.util.function.Consumer;
>>>> import java.util.function.BiFunction;
>>>> import java.util.function.Function;
>>>> @@ -2615,6 +2616,54 @@
>>>>  int   capacity()     { return table.length; }
>>>>  float loadFactor()   { return loadFactor;   }
>>>> 
>>>> +
>>>> +    @Override
>>>> +    public void forEach(BiConsumer<? super K, ? super V> action) {
>>>> +        Objects.requireNonNull(action);
>>>> +        final int expectedModCount = modCount;
>>>> +        if (nullKeyEntry != null) {
>>>> +            forEachNullKey(expectedModCount, action);
>>>> +        }
>>>> +        Object[] table = this.table;
>>>> +        for(int index = 0; index < table.length; index++) {
>>>> +            Object item = table[index];
>>>> +            if (item == null) {
>>>> +                continue;
>>>> +            }
>>>> +            if (item instanceof HashMap.TreeBin) {
>>>> +                eachTreeNode(expectedModCount, ((TreeBin)item).first, action);
>>>> +                continue;
>>>> +            }
>>>> +            @SuppressWarnings("unchecked")
>>>> +            Entry<K,V> entry = (Entry<K,V>)item;
>>>> +            for (;entry != null; entry = (Entry<K,V>)entry.next) {
>>>> +                if (expectedModCount != modCount) {
>>>> +                    throw new ConcurrentModificationException();
>>>> +                }
>>>> +                action.accept(entry.key, entry.value);
>>>> +            }
>>>> +        }
>>>> +    }
>>>> +
>>>> +    private void eachTreeNode(int expectedModCount, TreeNode<K,V> node, BiConsumer<? super K, ? super V> action) {
>>>> +        while (node != null) {
>>>> +            if (expectedModCount != modCount) {
>>>> +                throw new ConcurrentModificationException();
>>>> +            }
>>>> +            @SuppressWarnings("unchecked")
>>>> +            Entry<K,V> entry = (Entry<K,V>)node.entry;
>>>> +            action.accept(entry.key, entry.value);
>>>> +            node = (TreeNode<K,V>)entry.next;
>>>> +        }
>>>> +    }
>>>> +
>>>> +    private void forEachNullKey(int expectedModCount, BiConsumer<? super K, ? super V> action) {
>>>> +        if (expectedModCount != modCount) {
>>>> +            throw new ConcurrentModificationException();
>>>> +        }
>>>> +        action.accept(null, nullKeyEntry.value);
>>>> +    }
>>>> +
>>>>  /**
>>>>   * Standin until HM overhaul; based loosely on Weak and Identity HM.
>>>>   */
>>>> diff -r 6df79b7bae6f src/share/classes/java/util/LinkedHashMap.java
>>>> --- a/src/share/classes/java/util/LinkedHashMap.java    Wed Jun 12 09:44:34 2013 +0100
>>>> +++ b/src/share/classes/java/util/LinkedHashMap.java    Thu Jun 13 00:46:05 2013 +0200
>>>> @@ -24,7 +24,8 @@
>>>> */
>>>> 
>>>> package java.util;
>>>> -import java.io.*;
>>>> +
>>>> +import java.util.function.BiConsumer;
>>>> 
>>>> /**
>>>> * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
>>>> @@ -470,4 +471,16 @@
>>>>  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
>>>>      return false;
>>>>  }
>>>> +
>>>> +    @Override
>>>> +    public void forEach(BiConsumer<? super K, ? super V> action) {
>>>> +        Objects.requireNonNull(action);
>>>> +        int expectedModCount = modCount;
>>>> +        for (Entry<K,V> entry = header.after; entry != header; entry = entry.after) {
>>>> +            if (expectedModCount != modCount) {
>>>> +                throw new ConcurrentModificationException();
>>>> +            }
>>>> +            action.accept(entry.key, entry.value);
>>>> +        }
>>>> +    }
>>>> }
>>>> 
>>>> 
>>> 
>> 
> 




More information about the core-libs-dev mailing list