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); > + } > + } > } > >