Java Memory Model and reordering operation

Question

The my question is addressed to the post: https://shipilev.net/blog/2014/safe-public-construction/

public class UnsafeDCLFactory {
  private Singleton instance;

  public Singleton get() {
    if (instance == null) {  // read 1, check 1
      synchronized (this) {
        if (instance == null) { // read 2, check 2
          instance = new Singleton(); // store
        }
      }
    }
    return instance; // read 3
  }
}

And, it is written:

Notice that we do several reads of instance in this code, and at least "read 1" and "read 3" are the reads without any synchronization — that is, those reads are racy. One of the intents of the Java Memory Model is to allow reorderings for ordinary reads, otherwise the performance costs would be prohibitive. Specification-wise, as mentioned in happens-before consistency rules, a read action can observe the unordered write via the race. This is decided for each read action, regardless what other actions have already read the same location. In our example, that means that even though "read 1" could read non-null instance, the code then moves on to returning it, then it does another racy read, and it can read a null instance, which would be returned!

I cannot understand it. I agree that compiler obviously can reorder memory operations. But, doing it, the compiler has to preserve the behaviuor of the original program from the one-thread's point view.

In the above example, the read 1 read non-null. The read 3 read null. It means that read 3 was reorderd by the compiler and read the instance in the precedence to read 1 ( We can skip CPU reordering, because the post raises Java Memory Model).

But, on my eye read 3 cannot overtook read 1 because of store operation- I mean instance = new Singleton();

After all, there is data dependency, it means that the compiler cannot reorder instruction read 3 with store because it changing the meaning of the program ( even one-threaded). The compiler also cannot change order the read 1 because it has to precede the store. Otherwise, the semantic of one-threaded program is different.

Therefore, the order must be: read 1 -> store -> read 3

What do you think about it?

P.S. What does it mean to publish something? Especially, what does it mean to publish somegthing unsafely?

---

It is an re-answer to the @Aleksey Shipilev's answer.

Let me say this again -- failure to construct the example does not disprove the rule.

Yes, it is obvious.

And Java Memory Model allows returning null on the second read.

I agree with that as well. I don't claim that it doesn't allow. ( It is possible because of data race- yes, they are evil). I claim that read 3 cannot overtake read 1. I know you are right, but I would like to understand that. I still claim that Java compiler cannot generate a such bytecode that read 3 take over read 1. I see read3 can read null because of data race, but I cannot imagine how it is possible that read 1 read non-null and read 3 read null while read 3 cannot overtake read 1 because of data dependency.

(We don't consider here memory ordering on the hardware (CPU) level)

Answer 1

But, doing it, the compiler has to preserve the behaviuor of the original program from the one-thread's point view.

Nope. It has to preserve the requirements of the language spec. In this case, JMM. If some transformation is legal under JMM, then it can be performed. "One-thread's point of view" is not a normative language, specification is.

And Java Memory Model allows returning null on the second read. If you cannot construct the actual transformation that does it, it does not mean such transformation is not possible. Let me say this again -- failure to construct the example does not disprove the rule. Now you can see the example transformation in "Benign Data Races are Resilient", and also read this paragraph there:

This may appear counter-intuitive: if we read null from instance, we take a corrective action with storing new instance, and that’s it. Indeed, if we have the intervening store to instance, we cannot see the default value, and we can only see that store (since it happens-before us in all conforming executions where first read returned null), or the store from the other thread (which is not null, just a different object). But the interesting behavior unfolds when we don’t read null from the instance on the first read. No intervening store takes place. The second read tries to read again, and being racy as it is, may read null. Ouch.

That is to say, you can easily transform the program to expose the path without the intervening write, and there trivial read reordering gives the "counter-intuitive" result. Bytecode is not the only "transformation" the program is amenable to. The link above outlines the compiler transformation that exposes the code path without the data dependency on store. I.e. these two programs are subtly different:

// Case 1
Object o1 = instance;
instance = new Object();
Object o2 = instance;

// Case 2
Object o1 = instance;
if (o1 == null)
  instance = new Object();
Object o2 = instance;

In "Case 2", there is a path that avoids the store to instance -- because program has two paths now, due to a branch -- optimizing transformations can expose it.

This is a contrived example of what could go wrong. In real programs, the control and data flows are much more complicated, and optimizing transformations are allowed to (and will eventually) yield similar result, because they operate on the set of derived rules like "no synchronization, no data dependencies -- free to move stuff around", after a metric ton of transformations that expose interesting behaviors.

Data races are evil.

Answer 2

Consider a class

class Foo { String bar = "qux"; }

When reading Foo::bar, you would always expect it to return the string "qux". A constructor call is however not atomic. It can rather be split into two segments:

Foo foo = <init> Foo;
foo.bar = "qux";

With unsafe publication, a thread might have published Foo but not its value of bar from its local memory. As reading a volatile field requires the synchronization of all memory, this problem is resolved by the above pattern.