On Jun 13 2013, at 06:21 , Remi Forax wrote: > On 06/13/2013 07:28 AM, 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 > > Hi Mike, > > in TreeMap.forEach (and replaceAll), the check for co-modification should be > done *before* action.accept(...) > and not after because the semantics of the Iterator allows users to modify > the map (hashmap or treemap) > if it's the last element (so we should not check modCount after the last > element).
Not implementing the best "fast-fail" we can to emulate the weaker semantics of iterator seems like a disservice. > Also the code of forEach inside the loop is basically a hand-inlined version > of Treemap.successor(), > I wonder if it's not better to use successor() here ? A little microbenchmark indicates that successor() is not appreciably slower and a lot clearer. > > > in Hashtable.replaceAll(), the cast to K and V in function.apply() is useless. Fixed. I had moved the casts around and didn't notice that these ones were no longer needed. > otherwise, all other codes are ok for me :) > > Rémi > >> >> >> 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); >>> + } >>> + } >>> } >>> >>> >