RFR : 8016446 : (m) Add override forEach/replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap
Remi Forax
forax at univ-mlv.fr
Wed Jun 19 00:17:40 UTC 2013
On 06/19/2013 01:16 AM, Mike Duigou wrote:
> On Jun 18 2013, at 11:54 , Remi Forax wrote:
>
>> 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();
>> }
>> }
>> }
> Corrected in the pushed version.
>
>> Also there is no curly brace around "throw new CME();"
> Also corrected in the pushed version.
>
>> And I have an open question, in ConcurrentMap, the code use entrySet() but could use forEach,
>> I wonder which one is better here ?
> Good suggestion. I opted for the forEach. A capturing BiConsumer lambda is cheaper than the iterator overhead.
>
> Thanks for your patient and thorough feedback on this issue.
>
> Mike
Thanks for having taken my late modifications into account,
and as a user being able to write map.forEach(...) is awesome.
Rémi
>
>> 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