Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
On Mar 11, 2015, at 12:34 AM, Brent Christian brent.christ...@oracle.com wrote: Hi, Paul On 3/10/15 8:29 AM, Paul Sandoz wrote: On the Map.compute* methods. Perhaps we can reuse similar language to that we added for Matcher: * The mapping function should not modify this map during computation. * This method will, on a best-effort basis, throw a * ConcurrentModification if such modification is detected. It's tempting to place the second sentence on the @throws ConcurrentModificationException as i believe will not show up for methods on ConcurrentMap, so keeps it somewhat contained documentation wise. The language in Matcher is nice, and we can use it in HashMap. But the default code in Map.compute* won't throw a CME (no iteration). That's ok, we can call that out if necessary in the @implSpec. For the compute* methods in the Map interface, I think we should stick to recommending against modifying the Map during the computation, Yes. and encouraging implementing classes to check for CME. Yes. My suggestion was to try and push much of the CME-related specification onto the @throws CME docs. That way less of this will appear on ConcurrentMap where CME does not make sense. In Map/HashMap, there are already two methods that accept lambdas and throw a CME: forEach(BiConsumer) replaceAll(BiFunction) (The default code does not throw a CME ifitems are added). Right, although the iterator might still be fail-fast. Ahh - I needed to update my test code (if a Map only has a single entry, the iterator doesn't CME when items are added because a second iteration never happens to detect the changed modCount). A Map with = 2 entries is needed for the default code to CME due to items being added during forEach()/replaceAll(). Yeah, it's all best-effort. Paul.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
Hi, Here is an updated treatment of computeIfAbsent(): http://cr.openjdk.java.net/~bchristi/8071667/webrev.1/ There's a webrev, as well as built docs for Map[1], ConcurrentMap[2], and HashMap[3] (and I now realize there should be Hashtable as well). I've made use of @implSpec and friends in a way I thought was sensible (though things could be arranged differently - I can see where some might find the additional headings in the rendered JavaDoc a little distracting ). Let me know what you think. Thanks, -Brent 1. http://cr.openjdk.java.net/~bchristi/8071667/webrev.1/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function- 2. http://cr.openjdk.java.net/~bchristi/8071667/webrev.1/docs/api/java/util/concurrent/ConcurrentMap.html#computeIfAbsent-K-java.util.function.Function- 3. http://cr.openjdk.java.net/~bchristi/8071667/webrev.1/docs/api/java/util/HashMap.html#computeIfAbsent-K-java.util.function.Function- On 3/11/15 2:05 AM, Paul Sandoz wrote: On Mar 11, 2015, at 12:34 AM, Brent Christian brent.christ...@oracle.com wrote: Hi, Paul On 3/10/15 8:29 AM, Paul Sandoz wrote: On the Map.compute* methods. Perhaps we can reuse similar language to that we added for Matcher: * The mapping function should not modify this map during computation. * This method will, on a best-effort basis, throw a * ConcurrentModification if such modification is detected. It's tempting to place the second sentence on the @throws ConcurrentModificationException as i believe will not show up for methods on ConcurrentMap, so keeps it somewhat contained documentation wise. The language in Matcher is nice, and we can use it in HashMap. But the default code in Map.compute* won't throw a CME (no iteration). That's ok, we can call that out if necessary in the @implSpec. For the compute* methods in the Map interface, I think we should stick to recommending against modifying the Map during the computation, Yes. and encouraging implementing classes to check for CME. Yes. My suggestion was to try and push much of the CME-related specification onto the @throws CME docs. That way less of this will appear on ConcurrentMap where CME does not make sense. In Map/HashMap, there are already two methods that accept lambdas and throw a CME: forEach(BiConsumer) replaceAll(BiFunction) (The default code does not throw a CME ifitems are added). Right, although the iterator might still be fail-fast. Ahh - I needed to update my test code (if a Map only has a single entry, the iterator doesn't CME when items are added because a second iteration never happens to detect the changed modCount). A Map with = 2 entries is needed for the default code to CME due to items being added during forEach()/replaceAll(). Yeah, it's all best-effort. Paul.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
Hi Brent,
On the Map.compute* methods.
Perhaps we can reuse similar language to that we added for Matcher:
The mapping function should not modify this map during computation. This
method will, on a best-effort basis, throw a
ConcurrentModification if such modification is detected.
It's tempting to place the second sentence on the @throws
ConcurrentModificationException as i believe will not show up for methods on
ConcurrentMap, so keeps it somewhat contained documentation wise.
On Mar 6, 2015, at 8:08 PM, Brent Christian brent.christ...@oracle.com wrote:
Hi. I'm picking this back up now.
In Map/HashMap, there are already two methods that accept lambdas and throw a
CME:
forEach(BiConsumer)
replaceAll(BiFunction)
The Map interface documents these methods to state that Exceptions are
relayed to the caller, and has an @throws CME tag if an entry is found to
be removed. (The default code does not throw a CME if items are added).
Right, although the iterator might still be fail-fast.
HashMap adds no additional documentation on these methods. It has code to
check the modCount, and throws a CME if it changes.
The Map/HashMap methods I would like to update with this fix are:
compute(Key, BiFunction)
computeIfAbsent(Key, Function)
computeIfPresent(Key, BiFunction)
merge(Key, Value, BiFunction)
I would like to update the docs code as follows:
Map:
Docs: discourage modifying the map from function code; encourage
implementing classes to detect/throw CME
Code: no change
HashMap/Hashtable:
Docs: document that structural modifications will result in a CME; add
@throws CME
Code: check modCount throw CME
ConcurrentMap:
Docs: discourage modifying the map from function code
Code: no change
My first draft for the docs change, on computeIfAbsent():
diff -r 330dcd651f3b src/java.base/share/classes/java/util/Map.java
--- a/src/java.base/share/classes/java/util/Map.javaMon Feb 02 12:35:18
2015 -0800
+++ b/src/java.base/share/classes/java/util/Map.javaFri Feb 06 12:49:19
2015 -0800
@@ -925,6 +925,11 @@
* }
* }/pre
*
+ * pThe mappingFunction itself should not make changes to this map.
+ * Implementing classes are encouraged to detect such modifications and
+ * throw ConcurrentModificationException. The default implementation does
+ * not do so.
+ *
* pThe default implementation makes no guarantees about synchronization
* or atomicity properties of this method. Any implementation providing
* atomicity guarantees must override this method and document its
diff -r 330dcd651f3b src/java.base/share/classes/java/util/HashMap.java
--- a/src/java.base/share/classes/java/util/HashMap.javaMon Feb 02
12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/HashMap.javaFri Feb 06
12:49:19 2015 -0800
@@ -1082,6 +1082,17 @@
return null;
}
+/**
+ * {@inheritDoc}
+ *
+ * pThe mappingFunction itself should not make changes to this map.
+ * If the function causes a structural modification to the map, a
+ * ConcurrentModificationException will be thrown. As with iterators,
this
+ * exception is thrown on a best-effort basis.
+ *
+ * @throws ConcurrentModificationException if a structural change was
+ * detected while executing the mappingFunction
+ */
@Override
public V computeIfAbsent(K key,
Function? super K, ? extends V
mappingFunction) {
diff -r 330dcd651f3b
src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
--- a/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
Mon Feb 02 12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
Fri Feb 06 12:49:19 2015 -0800
@@ -305,6 +305,8 @@
* threads attempt updates including potentially calling the mapping
* function multiple times.
*
+ * pThe mappingFunction itself should not make changes to this map.
+ *
* pThis implementation assumes that the ConcurrentMap cannot contain
null
* values and {@code get()} returning null unambiguously means the key is
---
If that looks okay, I will apply it to the other methods.
I came across a few methods used by the list classes that I wanted to point
out:
forEach(Consumer) on the Iterable interface
removeIf(Predicate) on the Collection interface
replaceAll(UnaryOperator) on the List interface
They all document that exceptions are relayed to the caller. They do not
have a @throws CME tag. The default code uses iterators (or enhanced for()).
LinkedList uses the default versions. ArrayList overrides the methods,
adds no docs of its own, and has code to check the modCount and throw CME.
Would an @throws CME improve the JavaDoc of these default methods? I'm
leaning toward, not really.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
Hi, Paul On 3/10/15 8:29 AM, Paul Sandoz wrote: On the Map.compute* methods. Perhaps we can reuse similar language to that we added for Matcher: * The mapping function should not modify this map during computation. * This method will, on a best-effort basis, throw a * ConcurrentModification if such modification is detected. It's tempting to place the second sentence on the @throws ConcurrentModificationException as i believe will not show up for methods on ConcurrentMap, so keeps it somewhat contained documentation wise. The language in Matcher is nice, and we can use it in HashMap. But the default code in Map.compute* won't throw a CME (no iteration). For the compute* methods in the Map interface, I think we should stick to recommending against modifying the Map during the computation, and encouraging implementing classes to check for CME. In Map/HashMap, there are already two methods that accept lambdas and throw a CME: forEach(BiConsumer) replaceAll(BiFunction) (The default code does not throw a CME ifitems are added). Right, although the iterator might still be fail-fast. Ahh - I needed to update my test code (if a Map only has a single entry, the iterator doesn't CME when items are added because a second iteration never happens to detect the changed modCount). A Map with = 2 entries is needed for the default code to CME due to items being added during forEach()/replaceAll(). Thanks, -Brent
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
Nevermind, sorry somehow I missed the previous emails in the thread. On Friday, March 6, 2015 3:57 PM, Ben Manes ben_ma...@yahoo.com wrote: I'd recommend that the exception thrown should be an IllegalStateException. This is documented in ConcurrentHashMap's computeIfAbsent as, * @throws IllegalStateException if the computation detectably * attempts a recursive update to this map that would * otherwise never complete The detection logic is in Doug's repository to be merged in for JDK-8062841. It is also unexpected to have a concurrent data structure throw a ConcurrentModificationException, which is why I believe that IllegalStateException was chosen for ConcurrentHashMap.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
I'd recommend that the exception thrown should be an IllegalStateException. This is documented in ConcurrentHashMap's computeIfAbsent as, * @throws IllegalStateException if the computation detectably * attempts a recursive update to this map that would * otherwise never complete The detection logic is in Doug's repository to be merged in for JDK-8062841. It is also unexpected to have a concurrent data structure throw a ConcurrentModificationException, which is why I believe that IllegalStateException was chosen for ConcurrentHashMap.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
Hi. I'm picking this back up now.
In Map/HashMap, there are already two methods that accept lambdas and
throw a CME:
forEach(BiConsumer)
replaceAll(BiFunction)
The Map interface documents these methods to state that Exceptions are
relayed to the caller, and has an @throws CME tag if an entry is found
to be removed. (The default code does not throw a CME if items are added).
HashMap adds no additional documentation on these methods. It has code
to check the modCount, and throws a CME if it changes.
The Map/HashMap methods I would like to update with this fix are:
compute(Key, BiFunction)
computeIfAbsent(Key, Function)
computeIfPresent(Key, BiFunction)
merge(Key, Value, BiFunction)
I would like to update the docs code as follows:
Map:
Docs: discourage modifying the map from function code; encourage
implementing classes to detect/throw CME
Code: no change
HashMap/Hashtable:
Docs: document that structural modifications will result in a CME;
add @throws CME
Code: check modCount throw CME
ConcurrentMap:
Docs: discourage modifying the map from function code
Code: no change
My first draft for the docs change, on computeIfAbsent():
diff -r 330dcd651f3b src/java.base/share/classes/java/util/Map.java
--- a/src/java.base/share/classes/java/util/Map.javaMon Feb 02
12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/Map.javaFri Feb 06
12:49:19 2015 -0800
@@ -925,6 +925,11 @@
* }
* }/pre
*
+ * pThe mappingFunction itself should not make changes to this map.
+ * Implementing classes are encouraged to detect such modifications and
+ * throw ConcurrentModificationException. The default
implementation does
+ * not do so.
+ *
* pThe default implementation makes no guarantees about
synchronization
* or atomicity properties of this method. Any implementation
providing
* atomicity guarantees must override this method and document its
diff -r 330dcd651f3b src/java.base/share/classes/java/util/HashMap.java
--- a/src/java.base/share/classes/java/util/HashMap.javaMon Feb
02 12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/HashMap.javaFri Feb
06 12:49:19 2015 -0800
@@ -1082,6 +1082,17 @@
return null;
}
+/**
+ * {@inheritDoc}
+ *
+ * pThe mappingFunction itself should not make changes to this map.
+ * If the function causes a structural modification to the map, a
+ * ConcurrentModificationException will be thrown. As with
iterators, this
+ * exception is thrown on a best-effort basis.
+ *
+ * @throws ConcurrentModificationException if a structural change was
+ * detected while executing the mappingFunction
+ */
@Override
public V computeIfAbsent(K key,
Function? super K, ? extends V
mappingFunction) {
diff -r 330dcd651f3b
src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
---
a/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
Mon Feb 02 12:35:18 2015 -0800
+++
b/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
Fri Feb 06 12:49:19 2015 -0800
@@ -305,6 +305,8 @@
* threads attempt updates including potentially calling the mapping
* function multiple times.
*
+ * pThe mappingFunction itself should not make changes to this map.
+ *
* pThis implementation assumes that the ConcurrentMap cannot
contain null
* values and {@code get()} returning null unambiguously means the
key is
---
If that looks okay, I will apply it to the other methods.
I came across a few methods used by the list classes that I wanted to
point out:
forEach(Consumer) on the Iterable interface
removeIf(Predicate) on the Collection interface
replaceAll(UnaryOperator) on the List interface
They all document that exceptions are relayed to the caller. They do
not have a @throws CME tag. The default code uses iterators (or
enhanced for()). LinkedList uses the default versions. ArrayList
overrides the methods, adds no docs of its own, and has code to check
the modCount and throw CME.
Would an @throws CME improve the JavaDoc of these default methods?
I'm leaning toward, not really. Between the clause about exceptions
being relayed to the caller, and knowing that the default method is
using iterators (mentioned in the JavaDoc), and that iterators will
throw CMEs, one can deduce that modifying the list from the lambda will
result in a CME. It's not clearly spelled out, but then, modifying the
collection this way falls outside the intended usage of these methods.
Thanks for any additional feedback.
-Brent
On 2/6/15 1:12 PM, Brent Christian wrote:
diff -r 330dcd651f3b src/java.base/share/classes/java/util/Map.java
--- a/src/java.base/share/classes/java/util/Map.javaMon Feb 02
12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/Map.javaFri Feb 06
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
On 2/5/15 12:46 AM, Paul Sandoz wrote:
On Feb 5, 2015, at 1:36 AM, Brent Christian
brent.christ...@oracle.com wrote:
I prefer this approach of discouraging/preventing side-effects via
CME, rather than allowing them.
...
Regarding the default methods:
Would we be able to make a best-effort detection of
comodification...
My inclination is to leave these as is and focus on the most common
concrete implementations.
Fair enough. So, spec-wise...
For Map, I'd like to add some words of discouragement regarding
modifying the map from function code. Maybe also encourage implementing
classes to detect and throw CME? (The default method will not do so.)
For HashMap: update the doc to say concurrent mods will results in a
CME, add @throws.
For ConcurrentMap: It does not discourage modifying the map from
function code, but it should IMO. It should not encourage subclasses to
throw CME.
ConcurrentHashMap: Does it need any changes? It already mentions that
one must not attempt to update any other mappings of this map. FWIW,
giving the side-effecty mappingFunction from 8071667 to a CHM hangs for
me; I've not investigated. :\
I don't think any changes are needed for concrete Map impls that inherit
the default Map methods (e.g. TreeMap, IdentityHashMap)
Here's an initial rough cut, for computeIfAbsent():
diff -r 330dcd651f3b src/java.base/share/classes/java/util/Map.java
--- a/src/java.base/share/classes/java/util/Map.javaMon Feb 02
12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/Map.javaFri Feb 06
12:49:19 2015 -0800
@@ -925,6 +925,11 @@
* }
* }/pre
*
+ * pThe mappingFunction itself should not make changes to this map.
+ * Implementing classes are encouraged to detect such modifications and
+ * throw ConcurrentModificationException. The default
implementation does
+ * not do so.
+ *
* pThe default implementation makes no guarantees about
synchronization
* or atomicity properties of this method. Any implementation
providing
* atomicity guarantees must override this method and document its
diff -r 330dcd651f3b src/java.base/share/classes/java/util/HashMap.java
--- a/src/java.base/share/classes/java/util/HashMap.javaMon Feb
02 12:35:18 2015 -0800
+++ b/src/java.base/share/classes/java/util/HashMap.javaFri Feb
06 12:49:19 2015 -0800
@@ -1082,6 +1082,17 @@
return null;
}
+/**
+ * {@inheritDoc}
+ *
+ * pThe mappingFunction itself should not make changes to this map.
+ * If the function causes a structural modification to the map, a
+ * ConcurrentModificationException will be thrown. As with
iterators, this
+ * exception is thrown on a best-effort basis.
+ *
+ * @throws ConcurrentModificationException if a structural change was
+ * detected while executing the mappingFunction
+ */
@Override
public V computeIfAbsent(K key,
Function? super K, ? extends V
mappingFunction) {
diff -r 330dcd651f3b
src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
---
a/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
Mon Feb 02 12:35:18 2015 -0800
+++
b/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java
Fri Feb 06 12:49:19 2015 -0800
@@ -305,6 +305,8 @@
* threads attempt updates including potentially calling the mapping
* function multiple times.
*
+ * pThe mappingFunction itself should not make changes to this map.
+ *
* pThis implementation assumes that the ConcurrentMap cannot
contain null
* values and {@code get()} returning null unambiguously means the
key is
Thanks,
-Brent
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
On Feb 5, 2015, at 1:45 AM, Doug Lea d...@cs.oswego.edu wrote: On 02/04/2015 05:01 AM, Paul Sandoz wrote: So i propose: - the functions should be side-effect free. ... - concurrent map implementations should, on a best-effort basis, detect non-termination situations and fail with ISE. We did this as part of changes to better detect recursive computIfAbsent in https://bugs.openjdk.java.net/browse/JDK-8062841 The best-effort is pretty good and catches most usage errors along these lines. (In principle it cannot catch all possible errors though.) Ah, thanks for the reminder, i forgot that was committed to 166: http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?r1=1.258r2=1.259sortby=date Paul.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
On Feb 5, 2015, at 1:36 AM, Brent Christian brent.christ...@oracle.com wrote: I prefer this approach of discouraging/preventing side-effects via CME, rather than allowing them. Keep the functions functional, as it were. If there are situations where determining the mapping for one key necessitates making additional changes to the Map, that should be coded some other way. IMO, sneaking extra work into computeIfAbsent() is too big a departure from how the method is intended to be used. Regarding the default methods: Would we be able to make a best-effort detection of comodification by checking for a change in size before and after calling mappingFunction? Or are there other reasons we cannot do anything about the default methods? Yes, i suppose we could, of course it would not detect any aliasing when sampling the size. My inclination is to leave these as is and focus on the most common concrete implementations. Paul.
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
Hi,
I think we should as consistent as possible about the functions being
side-effect free when applied to bulk operations. A method such as
computeIfAbsent can be viewed as a bulk operation in that it may perform two or
more dependent actions (they are just not as bulky as forEach).
It's inconsistent if we state the functions should be side-effect free *but*
map implementations tolerate side-effects resulting in state changes for
entries other than that associated with the key under operation. I am not even
sure this can be easily guaranteed with CHM in the face of resizes and keys
hashing to the same bucket.
So i propose:
- the functions should be side-effect free.
- non-concurrent map implementations should, on a best-effort basis, detect
comodification and fail with CME.
- concurrent map implementations should, on a best-effort basis, detect
non-termination situations and fail with ISE.
- document the best-effort behaviour and advise that implementations should
override the default implementations if they want to do better.
Alas we cannot do anything about the default method implementations, but i
don't think we should be constraining general behaviour based on that exact
implementations (just as we do not for concurrent maps, it behaves as if).
Paul.
On Feb 4, 2015, at 4:01 AM, Stuart Marks stuart.ma...@oracle.com wrote:
On 2/3/15 4:01 PM, Brent Christian wrote:
The code in bug 8071667 [1] passes a mappingFunction to computeIfAbsent()
which
itself put()s a sufficient number of additional entries into the HashMap to
cause a resize/rehash. As a result, computeIfAbsent() doesn't add the new
entry
at the proper place in the HashMap.
While one should not (mis)use the mappingFunction in this way,
HashMap.computeIfAbsent() (and similar HashMap methods which accept Lambda
expressions) could check for and throw a ConcurrentModificationException on a
best-effort basis, similar to iterators. This is already done in bulk
operations HashMap.forEach() and HashMap.replaceAll().
I think it's also worth making mention of this in the JavaDoc.
I think we need to have the specification discussion *first* before we decide
what HashMap should do with side-effecty computations that are passed to
computeIfAbsent and friends. Unfortunately the API specification for
Map.computeIfAbsent is largely silent about what should happen. I don't know
whether that means that the result should be undefined, or that passing a
function with side effects is implicitly allowed and should therefore be
defined.
I'd think it would be quite unpleasantly surprising to find that passing a
mapping function with side effects -- especially on keys other than the
current operation -- results in essentially a corrupted map. Then again, I'm
surprised that somebody would think to pass a mapping function that does have
side effects. However, this is what people do, and they expect the library to
behave reasonably.
I can think of an (only moderately contrived) use case that's probably behind
the bug report. Suppose I want to have a map that starts empty but which is
lazily initialized, and when it's initialized, it should contain entries for
all keys A, B, C, D, and E. Furthermore, it should be lazily initialized when
any one of these keys is put into the map. Of course, you can write this out
easily yourself. But hey, there's this new computeIfAbsent() method that
should let me do
map.computeIfAbsent(key, k - {
/* put all entries A..E except k */
return value_for_k;
});
Based on the @implSpec for Map.computeIfAbsent, I'd expect this to work. And
if your map inherits the Map.computeIfAbsent default implementation, it
probably does work. Indeed, the workaround given in the bug report is
essentially to implement your own method that duplicates the logic of the
@implSpec and the default method. So, I'm leaning toward specifying that side
effects should be supported, and that ConcurrentModificationException should
not be thrown.
That implies that HashMap will have to detect the concurrent modification and
deal with it instead of throwing an exception.
If we do clarify the spec to support this case, it probably shouldn't make
any guarantees about what should happen if the mapping function puts the
*same* key. That is, if
map.computeIfAbsent(key, k - {
put(k, value1);
return value2;
});
it seems reasonable that it not be defined which of value1 or value2 ends up
getting mapped to the key.
s'marks
Here's an example of what might be done, using computeIfAbsent() as an
example:
http://cr.openjdk.java.net/~bchristi/8071667/webrev.0/
I would update HashMap and Hashtable. It looks like
ConcurrentHashMap.computeIfAbsent() already forbids such usage, stating that
the
computation must not attempt to update any other mappings of this map.
Comments on this approach?
Thanks,
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
I prefer this approach of discouraging/preventing side-effects via CME,
rather than allowing them. Keep the functions functional, as it were.
If there are situations where determining the mapping for one key
necessitates making additional changes to the Map, that should be coded
some other way. IMO, sneaking extra work into computeIfAbsent() is too
big a departure from how the method is intended to be used.
Regarding the default methods:
Would we be able to make a best-effort detection of comodification by
checking for a change in size before and after calling mappingFunction?
Or are there other reasons we cannot do anything about the default
methods?
Thanks,
-Brent
On 2/4/15 2:01 AM, Paul Sandoz wrote:
Hi,
I think we should as consistent as possible about the functions being
side-effect free when applied to bulk operations. A method such as
computeIfAbsent can be viewed as a bulk operation in that it may
perform two or more dependent actions (they are just not as bulky as
forEach).
It's inconsistent if we state the functions should be side-effect
free *but* map implementations tolerate side-effects resulting in
state changes for entries other than that associated with the key
under operation. I am not even sure this can be easily guaranteed
with CHM in the face of resizes and keys hashing to the same bucket.
So i propose:
- the functions should be side-effect free.
- non-concurrent map implementations should, on a best-effort basis,
detect comodification and fail with CME.
- concurrent map implementations should, on a best-effort basis,
detect non-termination situations and fail with ISE.
- document the best-effort behaviour and advise that implementations
should override the default implementations if they want to do
better.
Alas we cannot do anything about the default method implementations,
but i don't think we should be constraining general behaviour based
on that exact implementations (just as we do not for concurrent maps,
it behaves as if).
Paul.
On Feb 4, 2015, at 4:01 AM, Stuart Marks stuart.ma...@oracle.com
wrote:
On 2/3/15 4:01 PM, Brent Christian wrote:
The code in bug 8071667 [1] passes a mappingFunction to
computeIfAbsent() which itself put()s a sufficient number of
additional entries into the HashMap to cause a resize/rehash. As
a result, computeIfAbsent() doesn't add the new entry at the
proper place in the HashMap.
While one should not (mis)use the mappingFunction in this way,
HashMap.computeIfAbsent() (and similar HashMap methods which
accept Lambda expressions) could check for and throw a
ConcurrentModificationException on a best-effort basis, similar
to iterators. This is already done in bulk operations
HashMap.forEach() and HashMap.replaceAll().
I think it's also worth making mention of this in the JavaDoc.
I think we need to have the specification discussion *first* before
we decide what HashMap should do with side-effecty computations
that are passed to computeIfAbsent and friends. Unfortunately the
API specification for Map.computeIfAbsent is largely silent about
what should happen. I don't know whether that means that the result
should be undefined, or that passing a function with side effects
is implicitly allowed and should therefore be defined.
I'd think it would be quite unpleasantly surprising to find that
passing a mapping function with side effects -- especially on keys
other than the current operation -- results in essentially a
corrupted map. Then again, I'm surprised that somebody would think
to pass a mapping function that does have side effects. However,
this is what people do, and they expect the library to behave
reasonably.
I can think of an (only moderately contrived) use case that's
probably behind the bug report. Suppose I want to have a map that
starts empty but which is lazily initialized, and when it's
initialized, it should contain entries for all keys A, B, C, D, and
E. Furthermore, it should be lazily initialized when any one of
these keys is put into the map. Of course, you can write this out
easily yourself. But hey, there's this new computeIfAbsent() method
that should let me do
map.computeIfAbsent(key, k - { /* put all entries A..E except k
*/ return value_for_k; });
Based on the @implSpec for Map.computeIfAbsent, I'd expect this to
work. And if your map inherits the Map.computeIfAbsent default
implementation, it probably does work. Indeed, the workaround given
in the bug report is essentially to implement your own method that
duplicates the logic of the @implSpec and the default method. So,
I'm leaning toward specifying that side effects should be
supported, and that ConcurrentModificationException should not be
thrown.
That implies that HashMap will have to detect the concurrent
modification and deal with it instead of throwing an exception.
If we do clarify the spec to support this case, it probably
shouldn't make any guarantees about what should happen if the
mapping function puts the *same* key. That is,
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
On 02/04/2015 05:01 AM, Paul Sandoz wrote: So i propose: - the functions should be side-effect free. ... - concurrent map implementations should, on a best-effort basis, detect non-termination situations and fail with ISE. We did this as part of changes to better detect recursive computIfAbsent in https://bugs.openjdk.java.net/browse/JDK-8062841 The best-effort is pretty good and catches most usage errors along these lines. (In principle it cannot catch all possible errors though.) -Doug
Re: RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667
On 2/3/15 4:01 PM, Brent Christian wrote:
The code in bug 8071667 [1] passes a mappingFunction to computeIfAbsent() which
itself put()s a sufficient number of additional entries into the HashMap to
cause a resize/rehash. As a result, computeIfAbsent() doesn't add the new entry
at the proper place in the HashMap.
While one should not (mis)use the mappingFunction in this way,
HashMap.computeIfAbsent() (and similar HashMap methods which accept Lambda
expressions) could check for and throw a ConcurrentModificationException on a
best-effort basis, similar to iterators. This is already done in bulk
operations HashMap.forEach() and HashMap.replaceAll().
I think it's also worth making mention of this in the JavaDoc.
I think we need to have the specification discussion *first* before we decide
what HashMap should do with side-effecty computations that are passed to
computeIfAbsent and friends. Unfortunately the API specification for
Map.computeIfAbsent is largely silent about what should happen. I don't know
whether that means that the result should be undefined, or that passing a
function with side effects is implicitly allowed and should therefore be defined.
I'd think it would be quite unpleasantly surprising to find that passing a
mapping function with side effects -- especially on keys other than the current
operation -- results in essentially a corrupted map. Then again, I'm surprised
that somebody would think to pass a mapping function that does have side
effects. However, this is what people do, and they expect the library to behave
reasonably.
I can think of an (only moderately contrived) use case that's probably behind
the bug report. Suppose I want to have a map that starts empty but which is
lazily initialized, and when it's initialized, it should contain entries for all
keys A, B, C, D, and E. Furthermore, it should be lazily initialized when any
one of these keys is put into the map. Of course, you can write this out easily
yourself. But hey, there's this new computeIfAbsent() method that should let me do
map.computeIfAbsent(key, k - {
/* put all entries A..E except k */
return value_for_k;
});
Based on the @implSpec for Map.computeIfAbsent, I'd expect this to work. And if
your map inherits the Map.computeIfAbsent default implementation, it probably
does work. Indeed, the workaround given in the bug report is essentially to
implement your own method that duplicates the logic of the @implSpec and the
default method. So, I'm leaning toward specifying that side effects should be
supported, and that ConcurrentModificationException should not be thrown.
That implies that HashMap will have to detect the concurrent modification and
deal with it instead of throwing an exception.
If we do clarify the spec to support this case, it probably shouldn't make any
guarantees about what should happen if the mapping function puts the *same* key.
That is, if
map.computeIfAbsent(key, k - {
put(k, value1);
return value2;
});
it seems reasonable that it not be defined which of value1 or value2 ends up
getting mapped to the key.
s'marks
Here's an example of what might be done, using computeIfAbsent() as an example:
http://cr.openjdk.java.net/~bchristi/8071667/webrev.0/
I would update HashMap and Hashtable. It looks like
ConcurrentHashMap.computeIfAbsent() already forbids such usage, stating that the
computation must not attempt to update any other mappings of this map.
Comments on this approach?
Thanks,
-Brent
1. https://bugs.openjdk.java.net/browse/JDK-8071667
HashMap.computeIfAbsent() adds entry that HashMap.get() does not find.
