Can instructions in this example from Java Concurrency in Practice be reordered during compiler optimizations

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

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 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.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

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