I'm reading the book on subject.
In 5.18, Brian Goetz gave an example of semi-efficient memoizer with a non-volatile shared variable cache having the type of ConcurrentHashMap as follows:
public class Memoizer3<A, V> implements Computable<A, V> {
private final Map<A, Future<V>> cache
= new ConcurrentHashMap<A, Future<V>>();
private final Computable<A, V> c;
public Memoizer3(Computable<A, V> c) { this.c = c; }
public V compute(final A arg) throws InterruptedException {
Future<V> f = cache.get(arg);
if (f == null) {
Callable<V> eval = new Callable<V>() {
public V call() throws InterruptedException {
return c.compute(arg);
}
};
FutureTask<V> ft = new FutureTask<V>(eval);
f = ft;
cache.put(arg, ft); // Can it be put at the very beginning of compute?
ft.run();
}
try {
return f.get();
} catch (ExecutionException e) {
throw launderThrowable(e.getCause());
}
}
}
The problem is that I don't understand rules under which cache.put(arg, ft); can be reordered by a compiler to be put ahead of Future<V> f = cache.get(arg); in terms of JLS (Is reordering of cache variable is possible at all?).
Under "reordering", I mean a chance of that lines of complete code may be reordered by a compiler due to enabled optimizations.
The question does not touch the topic of CPU memory reordering, which is highlighted, e.g., in https://stackoverflow.com/a/66973124
CodePudding user response：
Instructions can't be reordered if they violate the sequential semantics of a program.
Simple example (assuming a=b=0):
a=1
b=a
So according to the sequential semantics of the above program, the only allowed outcome is a=1, b=1. If the 2 instructions would be reordered, then we get outcome a=1,b=0. But this outcome is violating the sequential semantics and hence prohibited
This is also informally called within thread as if serial semantics. So the compiler (or CPU) is allowed to reordered instructions. But the most basic constraint is that no reorderings are allowed that would violate the sequential semantics.
If the JVM would be allowed to violate the sequential semantics of a program, I'm going to quit my job as developer today :)
In terms of the JMM: the a=1 is ordered before the b=a in the happens before order due to the program order between these 2 instructions.
Keep in mind that the JMM is not specified in terms of method calls. It is expressed in actions like plain loads/stores volatile loads/stores, monitor lock release/acquire etc.
[Addition]
Imagine you have the following code:
int a,b,c,d=0;
void foo(){
a=1
b=1
}
void bar(){
c=1
d=a
}
void foobar(){
foo();
bar();
}
Then the only allowed result is 'a=1,b=1,c=1,d=1'
Due to inlining we can get rid of the function calls:
void foobar(){
a=1 //foo
b=1 //foo
c=1 //bar
d=a //bar
}
The following execution preserves the sequential semantics:
c=1 //bar
a=1 //foo
b=1 //foo
d=a //bar
Since the outcome is 'a=1,b=1,c=1,d=1'
But the following execution violates the sequential semantics.
d=a //bar
a=1 //foo
b=1 //foo
c=1 //bar
Because we end up with 'a=1,b=1,c=1,d=0', where d is 0 instead of 1.
Instructions from function calls can be reordered under the condition that the sequential semantics of the program is not violated.
CodePudding user response：
After some investigation on ConcurrentHashMap.get, ConcurrentHashMap.putIfAbsent, I can say the understanding of why B.
Goetz' code has such a structure requires knowing the internals of ConcurrentHashmap.
Under "reordering" below, I mean a chance of that lines of a complete code may be reordered by a compiler due to enabled optimizations.
The answer does not touch the topic of CPU memory reordering, which is highlighted, e.g., in https://stackoverflow.com/a/66973124
In his previous example using ordinal Map version, B. Goetz used a synchronized version of compute:
public class Memoizer1<A, V> implements Computable<A, V> {
@GuardedBy("this")
private final Map<A, V> cache = new HashMap<A, V>();
private final Computable<A, V> c;
public Memoizer1(Computable<A, V> c) { this.c = c; }
public synchronized V compute(final A arg) throws InterruptedException {
V result = cache.get(arg);
if (result == null) {
result = c.compute(arg);
cache.put(arg, result);
}
return result;
}
}
Synchronized here was needed to prevent reordering of calls to a HashMap variable as well as thread-interleaving.
As long as synchronized forces it to actually run a store instruction, the value will become visible to other threads just by committing it to the local L1d cache, because it's coherent. (And a memory barrier will block later loads/stores until that happens).
Later, B. Goetz replaced ordinal HashMap with ConcurrentHashMap, which allowed him to remove synchronized keyword.
https://www.burnison.ca/articles/the-concurrency-of-concurrenthashmap clearly explains why ConcurrentHashMap.get is the first instruction here:
In comparisons to the previous methods, the get() and containsKey() methods are fairly mundane. Also unlike the previous methods, both are entirely lock-free. First, a Segment is retrieved from the segments array using the applicable high-order bits of the key's hash. The retrieval is performed using Unsafe.getObjectVolatile(). Next, a HashEntry of the segment's table array is retrieved using the key's hash. This retrieval is also performed using Unsafe.getObjectVolatile. From this head node, the linked list of HashEntry objects is traversed until the specified key is found (or not found) and the applicable value is returned.
Due to its volatile-read semantics, ConcurrentHashMap.get cannot be moved down in code by a compiler. At the same time, it allows moving that up.
However, Volatile reads may be reordered with previous lines so those lines have to be plain and their influence on the code below should be understandable without deep mental analysis.
ConcurrentHashMap.putIfAbsent has an internal lock in its implementation, so it can be moved neither up nor down in code.
The quotation of another author of "Java Concurrency in Practice" below is related to that within thread as if serial semantics is not enough to understand the multithreaded code fragment using shared variables.
The within-thread as-if-serial property is helpful only when only one thread at a time is manipulating variables, due to synchronization, structural exclusion, or pure chance. When multiple threads are all running unsynchronized code that reads and writes common fields, then arbitrary interleavings, atomicity failures, race conditions, and visibility failures may result in execution patterns that make the notion of as-if-serial just about meaningless with respect to any given thread.
Even though JLS addresses some particular legal and illegal reorderings that can occur, interactions with these other issues reduce practical guarantees to saying that the results may reflect just about any possible interleaving of just about any possible reordering. So there is no point in trying to reason about the ordering properties of such code.
(C) Doug Lea