Can instructions in Java Concurrency in Practice 5.18 be reordered during compiler optimizations

Question

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

EDIT:

A reason for this question is the ability of a compiler to damage unsynchronized multithreaded code fragments using shared variables in some cases, another reason is a quotation from an author of this book, Doug Lea:

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.

Per http://gee.cs.oswego.edu/dl/cpj/jmm.html

In other words, not following the JLS constraints regarding "happens-before", locks or volatile semantics may lead to broken results in unsynchronized code which uses shared variables.

P.S. Thanks to Peter Cordes for his comments on this theme.

Answer 1

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.

Answer 2

After some investigation on ConcurrentHashMap.get, ConcurrentHashMap.put, 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 simultaneous access of multiple threads to the hashmap. Since access methods of an ordinal hashmap are not atomic, there might potentially be a situation where one thread rewrites incomplete portions of data made by another thread, thus blocking the latter from completing its work. For the same reason, a reading method could potentially see partially constructed data.

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 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.put has volatile-write semantics so it cannot be reordered with upper operations but can be reordered with operations below. But FutureTask.run (ft.run(); here) internally uses full-fence CompareAndSetState (see How FutureTask is asynchronous computation and compareAndSwap a common member ( non-volatile member ) still has memory semantics of volatile read and write) so it generates full memory barrier and thus cache.put(arg, ft); cannot be reordered with ft.run();.

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

Per http://gee.cs.oswego.edu/dl/cpj/jmm.html