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

Paul Sandoz paul.sandoz at oracle.com
Fri Jun 14 09:20:14 UTC 2013


On Jun 13, 2013, at 11:56 PM, Remi Forax <forax at univ-mlv.fr> wrote:

> On 06/13/2013 04:47 PM, Paul Sandoz wrote:
>> On Jun 13, 2013, at 4:06 PM, Remi Forax <forax at univ-mlv.fr> wrote:
>>>>> There is a difference between an Iterator/forEach and a spliterator/stream,
>>>>> with a stream you know that the called lambdas will not interfere and mutate the source collection.
>>>>> 
>>>> You do? I don't think there is any conceptual difference between the following w.r.t. interference:
>>>> 
>>>>   ArrayList l = ...
>>>>   l.stream().filter(...).forEach(e -> l.add(e));
>>>>   l.spliterator().forEachRemaining(e -> l.add(e));
>>>> 
>>>> and:
>>>> 
>>>>   ArrayList l = ...
>>>>   l.forEach(e -> l.add(e));
>>>>   l.iterator().forEachRemaining(e -> l.add(e));
>>>> 
>>>> Of course we have (or will have) strong wording saying don't implement interfering lambdas, but we still have to check for co-modification in the traversal methods of ArrayList spliterator.
>>> Isn't it because if you remove an element from an ArrayList while iterating you can see a stale value ?
>>> While with a HashMap, if you have only one thread, you can not see a stale entry ?
>> Assuming just one thread do you agree that in all of the above examples the only way the list can be interfered with is by the Consumer instance e -> l.add(s) ?
> 
> yes, as I said to Mike, what is important IMO is that the semantics of forEach and the semantics of for(:) should be the same.
> 
>> 
>> 
>>> So a spliterator on HashMap can only check the modCount at the end unlike the one on ArrayList that need to check at each step.
>>> 
>> The ArrayList.spliterator.forEachRemaining implementation also checks at the end.
> 
> Given that a spliterator is something new which is weaker than an iterator, the semantics can be relaxed.

In terms of traversal I don't see a spliterator from an ArrayList being weaker than an iterator from an ArrayList. I would argue Iterator has a weaker model of traversal.

The following does not throw CME:

            List<Integer> l = new ArrayList<>(Arrays.asList(1, 2));
            for (Integer i : l) {
                l.remove(1);  // 2 is never encountered
            }

Where as the following does:

            List<Integer> l = new ArrayList<>(Arrays.asList(1, 2, 3));
            for (Integer i : l) {
                l.remove(1);
            }

Because the hasNext implementation does not check for modification. It's sad this also occurs for the default implementation of Iterable.forEach :-(

This behaviour sucks. It would be a shame for overriding forEach/forEachRemaining implementations to conform to such behaviour when they can implement stronger/consistent failure guarantees.


> For ArrayList, because you can see a stale entry if you mutate during a forEachRemaining,
> you have no choice but checking at each step.

A CME does not make any hard guarantees, thus cannot be used for correctness. I think this comes down to a balance of performance and how fast the fail-fast should be. I can definitely see an argument for failing ASAP so as not to report dodgy data.

Paul.

> And because the semantics is not tight to the iterator one,
> I agree that you can also perform a check at the end.
> For HashMap.spliterator.forEachRemaining,  because you can not see stale entry (without concurrency),
> you can only perform a check at the end. It's IMO also a valid semantics.
> 
>> 
>> Paul.
> 
> Rémi
> 




More information about the core-libs-dev mailing list