RFR : 8016446 : (m) Add override forEach/replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap
Remi Forax
forax at univ-mlv.fr
Tue Jun 18 18:54:37 UTC 2013
On 06/18/2013 01:30 AM, Mike Duigou wrote:
The webrev looks fine for me.
Nitpicking a little bit, in IdentityHashMap (forEach and replaceAll),
t[index] is processed twice, by example in forEach, it would prefer this
code:
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
Object[] t = table;
for (int index = 0; index < t.length; index += 2) {
Object key = t[index];
if (key != null) {
action.accept((K) unmaskNull(key), (V) t[index + 1]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
Also there is no curly brace around "throw new CME();"
And I have an open question, in ConcurrentMap, the code use entrySet()
but could use forEach,
I wonder which one is better here ?
cheers,
Rémi
> 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