Immutability and reordering

Question

The code below (Java Concurrency in Practice listing 16.3) is not thread safe for obvious reasons:

public class UnsafeLazyInitialization {
    private static Resource resource;

    public static Resource getInstance() {
        if (resource == null)
            resource = new Resource();  // unsafe publication
        return resource;
    }
}

However, a few pages later, in section 16.3, they state:

UnsafeLazyInitialization is actually safe if Resource is immutable.

I don't understand that statement:

• If Resource is immutable, any thread observing the resource variable will either see it null or fully constructed (thanks to the strong guarantees of final fields provided by the Java Memory Model)
• However, nothing prevents instruction reordering: in particular the two reads of resource could be reordered (there is one read in the if and one in the return). So a thread could see a non null resource in the if condition but return a null reference (*).

I think UnsafeLazyInitialization.getInstance() can return null even if Resource is immutable. Is it the case and why (or why Not)?

---

(*) To better understand my point about reordering, this blog post by Jeremy Manson, who is one of the authors of the Chapter 17 of the JLS on concurrency, explains how String's hashcode is safely published via a benign data race and how removing the use of a local variable can lead to hashcode incorrectly returning 0, due to a possible reordering very similar to what I describe above:

What I've done here is to add an additional read: the second read of hash, before the return. As odd as it sounds, and as unlikely as it is to happen, the first read can return the correctly computed hash value, and the second read can return 0! This is allowed under the memory model because the model allows extensive reordering of operations. The second read can actually be moved, in your code, so that your processor does it before the first!

Answer 1

UPDATE Feb10

I'm getting convinced that we should separate 2 phases: compilation and execution.

I think that the decision factor whether it is allowed to return null or not is what the bytecode is. I made 3 examples:

Example 1:

The original source code, literally translated to bytecode:

if (resource == null)
    resource = new Resource();  // unsafe publication
return resource;

The bytecode:

public static Resource getInstance();
Code:
0:   getstatic       #20; //Field resource:LResource;
3:   ifnonnull       16
6:   new             #22; //class Resource
9:   dup
10:  invokespecial   #24; //Method Resource."<init>":()V
13:  putstatic       #20; //Field resource:LResource;
16:  getstatic       #20; //Field resource:LResource;
19:  areturn

This is the most interesting case, because there are 2 reads (Line#0 and Line#16), and there is 1 write inbetween (Line#13). I claim that it is not possible to reorder, but let's examine it below.

Example 2:

The "complier optimized" code, which can be literally re-converted to java as follows:

Resource read = resource;
if (resource==null)
    read = resource = new Resource();
return read;

The byte code for that (actually I produced this by compiling the above code snippet):

public static Resource getInstance();
Code:
0:   getstatic       #20; //Field resource:LResource;
3:   astore_0
4:   getstatic       #20; //Field resource:LResource;
7:   ifnonnull       22
10:  new     #22; //class Resource
13:  dup
14:  invokespecial   #24; //Method Resource."<init>":()V
17:  dup
18:  putstatic       #20; //Field resource:LResource;
21:  astore_0
22:  aload_0
23:  areturn

It is obvious, that if the compiler "optimizes", and the byte code like above is produced, a null read can occur (for example, I refer to Jeremy Manson's blog)

It is also interesting to see that how a = b = c is working: the reference to new instance (Line#14) is duplicated (Line#17), and the same reference is stored then, first to b (resource, (Line#18)) then to a (read, (Line#21)).

Example 3:

Let's make an even slighter modification: read the resource only once! If the compiler starts to optimize (and using registers, as others mentioned), this is better optimization than above, because Line#4 here is a "register access" rather than a more expensive "static access" in Example 2.

Resource read = resource;
if (read == null)   // reading the local variable, not the static field
    read = resource = new Resource();
return read;

The bytecode for Example 3 (also created with literally compiling the above):

public static Resource getInstance();
Code:
0:   getstatic       #20; //Field resource:LResource;
3:   astore_0
4:   aload_0
5:   ifnonnull       20
8:   new     #22; //class Resource
11:  dup
12:  invokespecial   #24; //Method Resource."<init>":()V
15:  dup
16:  putstatic       #20; //Field resource:LResource;
19:  astore_0
20:  aload_0
21:  areturn

It is also easy to see, that it is not possible to get null from this bytecode since it is constructed the same way as String.hashcode(), having only 1 read of the static variable of resource.

Now let's examine Example 1:

0:   getstatic       #20; //Field resource:LResource;
3:   ifnonnull       16
6:   new             #22; //class Resource
9:   dup
10:  invokespecial   #24; //Method Resource."<init>":()V
13:  putstatic       #20; //Field resource:LResource;
16:  getstatic       #20; //Field resource:LResource;
19:  areturn

You can see that Line#16 (the read of variable#20 for return) most observe the write from Line#13 (the assignation of variable#20 from the constructor), so it is illegal to place it ahead in any execution order where Line#13 is executed. So, no reordering is possible.

For a JVM it is possible to construct (and take advantage of) a branch that (using certain extra conditions) bypasses the Line#13 write: the condition is that the read from variable#20 must not be null.

So, in neither case for Example 1 is possible to return null.

Conclusion:

Seeing the examples above, a bytecode seen in Example 1 WILL NOT PRODUCE null. An optimized bytecode like in Example 2 WILL PROCUDE null, but there is an even better optimization Example 3, which WILL NOT PRODUCE null.

Because we cannot be prepared for all possible optimization of all the compilers, we can say that in some cases it is possible, some other cases not possible to return null, and it all depends on the byte code. Also, we have shown that there is at least one example for both cases.

---

Older reasoning: Referring for the example of Assylias: The main question is: is it valid (concerning all specs, JMM, JLS) that a VM would reorder the 11 and 14 reads so, that 14 will happen BEFORE 11?

If it could happen, then the independent Thread2could write the resource with 23, so 14 could read null. I state that it is not possible.

Actually, because there is a possible write of 13, it would not be a valid execution order. A VM may optimize the execution order so, that excludes the not-executed branches (remaining just 2 reads, no writes), but to make this decision, it must do the first read (11), and it must read not-null, so the 14 read cannot precede the 11 read. So, it is NOT possible to return null.

---

Immutability

Concerning immutability, I think that this statement is not true:

UnsafeLazyInitialization is actually safe if Resource is immutable.

However, if the constructor is unpredictable, interesting results may come out. Imagine a constructor like this:

public class Resource {
    public final double foo;

    public Resource() {
        this.foo = Math.random();
    }
}

If we have tho Threads, it may result, that the 2 threads will receive a differently-behaving Object. So, the full statement should sound like this:

UnsafeLazyInitialization is actually safe if Resource is immutable and its initialization is consistent.

By consistent I mean that calling the constructor of the Resource twice we will receive two objects that behave exactly the same way (calling the same methods in the same order on both will yield the same results).

Answer 2

The confusion I think you have here is what the author meant by safe publication. He was referring to the safe publication of a non-null Resource, but you seem to get that.

Your question is interesting - is it possible to return a null cached value of resource?

Yes.

The compiler is allowed to reorder the operation like such

public static Resource getInstance(){
   Resource reordered = resource;
   if(resource != null){
       return reordered;
   }
   return (resource = new Resource());
} 

This doesn't violate the rule of sequential consistency but can return a null value.

Whether or not this is the best implementation is up for debate but there is no rules to prevent this type of reordering.

Answer 3

After applying the JLS rules to this example, I have come to the conclusion that getInstance can definitely return null. In particular, JLS 17.4:

The memory model determines what values can be read at every point in the program. The actions of each thread in isolation must behave as governed by the semantics of that thread, with the exception that the values seen by each read are determined by the memory model.

It is then clear that in the absence of synchronization, null is a legal outcome of the method since each of the two reads can observe anything.

---

Proof

Decomposition of reads and writes

The program can be decomposed as follows (to clearly see the reads and writes):

                              Some Thread
---------------------------------------------------------------------
 10: resource = null; //default value                                  //write
=====================================================================
           Thread 1               |          Thread 2                
----------------------------------+----------------------------------
 11: a = resource;                | 21: x = resource;                  //read
 12: if (a == null)               | 22: if (x == null)               
 13:   resource = new Resource(); | 23:   resource = new Resource();   //write
 14: b = resource;                | 24: y = resource;                  //read
 15: return b;                    | 25: return y;                    

What the JLS says

JLS 17.4.5 gives the rules for a read to be allowed to observe a write:

We say that a read r of a variable v is allowed to observe a write w to v if, in the happens-before partial order of the execution trace:

• r is not ordered before w (i.e., it is not the case that hb(r, w)), and
• there is no intervening write w' to v (i.e. no write w' to v such that hb(w, w') and hb(w', r)).

Application of the rule

In our example, let's assume that thread 1 sees null and properly initialises resource. In thread 2, an invalid execution would be for 21 to observe 23 (due to program order) - but any of the other writes (10 and 13) can be observed by either read:

• 10 happens-before all actions so no read is ordered before 10
• 21 and 24 have no hb relationship with 13
• 13 does not happens-before 23 (no hb relationship between the two)

So both 21 and 24 (our 2 reads) are allowed to observe either 10 (null) or 13 (not null).

Execution path that returns null

In particular, assuming that Thread 1 sees a null on line 11 and initialises resource on line 13, Thread 2 could legally execute as follows:

• 24: y = null (reads write 10)
• 21: x = non null (reads write 13)
• 22: false
• 25: return y

Note: to clarify, this does not mean that T2 sees non null and subsequently sees null (which would breach the causality requirements) - it means that from an execution perspective, the two reads have been reordered and the second one was committed before the first one - however it does look as if the later write had been seen before the earlier one based on the initial program order.

UPDATE 10 Feb

Back to the code, a valid reordering would be:

Resource tmp = resource; // null here
if (resource != null) { // resource not null here
    resource = tmp = new Resource();
}
return tmp; // returns null

And because that code is sequentially consistent (if executed by a single thread, it will always have the same behaviour as the original code) it shows that the causality requirements are satisfied (there is a valid execution that produces the outcome).

---

After posting on the concurrency interest list, I got a few messages regarding the legality of that reordering, which confirm that null is a legal outcome:

• The transformation is definitely legal since a single-threaded execution won't tell the difference. [Note that] the transformation doesn't seem sensible - there's no good reason a compiler would do it. However, given a larger amount of surrounding code or perhaps a compiler optimization "bug", it could happen.
• The statement about intra-thread ordering and program order is what made me question the validity of things, but ultimately the JMM relates to the bytecode that gets executed. The transformation could be done by the javac compiler in which case null will be perfectly valid. And there are no rules for how javac has to convert from Java source to Java bytecode so...

Answer 4

There are essentially two questions that you are asking:

1. Can the getInstance() method return null due to reordering?

(which I think is what you are really after, so I'll try to answer it first)

Even though I think designing Java to allow for this is totally insane, it seems like you are in fact correct that getInstance() can return null.

Your example code:

if (resource == null)
    resource = new Resource();  // unsafe publication
return resource;

is logically 100% identical to the example in the blog post you linked to:

if (hash == 0) {
    // calculate local variable h to be non-zero
    hash = h;
}
return hash;

Jeremy Manson then describes that his code can return 0 due to reordering. At first, I didn't believe it as I thought the following "happens-before"-logic must hold:

   "if (resource == null)" happens before "resource = new Resource();"
                                   and
     "resource = new Resource();" happens before "return resource;"
                                therefore
"if (resource == null)" happens before "return resource;", preventing null

But Jeremy gives the following example in a comment to his blog post, how this code could be validly rewritten by the compiler:

read = resource;
if (resource==null)
    read = resource = new Resource();
return read;

This, in a single-threaded environment, behaves exactly identically to the original code, but, in a multi-threaded environment might lead to the following execution order:

Thread 1                        Thread 2
------------------------------- -------------------------------------------------
read = resource;    // null
                                read = resource;                      // null
                                if (resource==null)                   // true
                                    read = resource = new Resource(); // non-null
                                return read;                          // non-null
if (resource==null) // FALSE!!!
return read;        // NULL!!!

Now, from an optimization-standpoint, doing this doesn't make any sense to me, since the whole point of these things would be to reduce multiple reads to the same location, in which case it makes no sense that the compiler wouldn't generate if (read==null) instead, preventing the problem. So, as Jeremy points out in his blog, it is probably highly unlikely that this would ever happen. But it seems that, purely from a language-rules point of view, it is in fact allowed.

This example is actually covered in the JLS:

http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4

The effect observed between the values of r2, r4, and r5 in Table 17.4. Surprising results caused by forward substitution is equivalent to what can happen with the read = resource, the if (resource==null), and the return resource in the example above.

Aside: Why do I reference the blog post as the ultimate source for the answer? Because the guy who wrote it, is also the guy who wrote chapter 17 of the JLS on concurrency! So, he better be right! :)

2. Would making Resource immutable make the getInstance() method thread-safe?

Given the potential null result, which can happen independently of whether Resource is mutable or not, the immediate simple answer to this question is: No (not strictly)

If we ignore this highly unlikely but possible scenario, though, the answer is: Depends.

The obvious threading-problem with the code is that it might lead to the following execution order (without any need for any reordering):

Thread 1                                 Thread 2
---------------------------------------- ----------------------------------------
if (resource==null) // true;  
                                         if (resource==null)          // true
                                             resource=new Resource(); // object 1
                                         return resource;             // object 1
    resource=new Resource(); // object 2
return resource;             // object 2

So, the non-thread-safety is coming from the fact that you might get two different objects back from the function (even though without reordering neither of them will ever be null).

Now, what the book was probably trying to say is the following:

The Java immutable objects like Strings and Integers try to avoid creating multiple objects for the same content. So, if you have "hello" in one spot and "hello" in another spot, Java will give you the same exact object reference. Similarly, if you have new Integer(5) in one spot and new Integer(5) in another. If this were the case with new Resource() as well, you would get the same reference back and object 1 and object 2 in the above example would be the exact same object. This would indeed lead to an effectively thread-safe function (ignoring the reordering problem).

But, if you implement Resource yourself, I don't believe there is even a way to have the constructor return a reference to a previously created object rather than creating a new one. So, it should not be possible for you to make object 1 and object 2 be the exact same object. But, given that you are calling the constructor with the same arguments (none in both cases), it could be likely that, even though your created objects aren't the same exact object, they will, for all intents and purposes, behave as if they were, also effectively making the code thread-safe.

This doesn't necessarily have to be the case, though. Imagine an immutable version of Date, for example. The default constructor Date() uses the current system time as the date's value. So, even though the object is immutable and the constructor is called with the same argument, calling it twice will probably not result in an equivalent object. Therefore the getInstance() method is not thread-safe.

So, as a general statement, I believe the line you quoted from the book is just plain wrong (at least as taken out of context here).

ADDITION Re: reordering

I find the resource==new Resource() example a bit too simplistic to help me understand WHY allowing such reordering by Java would ever make sense. So let me see if I can come up with something where this would actually help optimization:

System.out.println("Found contact:");
System.out.println(firstname + " " + lastname);
if (firstname==null) firstname = "";
if (lastname ==null) lastname  = "";
return firstname + " " + lastname;

Here, in the most likely case that both ifs yield false, it is non-optimal to do the expensive String concatenation firstname + " " + lastname twice, once for the debug message, once for the return. So, it would indeed make sense here to reorder the code to do the following instead:

System.out.println("Found contact:");
String contact = firstname + " " + lastname;
System.out.println(contact);
if ((firstname==null) || (lastname==null)) {
    if (firstname==null) firstname = "";
    if (lastname ==null) lastname  = "";
    contact = firstname + " " + lastname;
}
return contact;

As examples get more complex and as you start thinking about the compiler keeping track of what is already loaded/computed in the processor registers that it uses and intelligently skipping re-calculation of already existing results, this effect might actually become more and more likely to happen. So, even though I never thought I would ever say this when I went to bed last night, thinking about it more, I do actually now believe that this may have been a needed/good decision to truly allow for code optimization to do its most impressive magic. But it does still strike me as quite dangerous as I don't think many people are aware of this and even if they are, it's quite complex to wrap your head around how to write your code correctly without synchronizing everything (which will then do away many times over with any performance benefits gained from more flexible optimization).

I guess if you didn't allow for this reordering, any caching and reuse of intermediate results of a series of process steps would become illegal, thus doing away with one of the most powerful compiler optimizations possible.

Answer 5

Nothing sets the reference to null once it is non-null. It's possible for a thread to see null after another thread has set it to non-null but I don't see how the reverse is possible.

I'm not sure instruction re-ordering is a factor here, but interleaving of instructions by two threads is. The if branch can't somehow be reordered to execute before its condition has been evaluated.

Answer 6

I'm sorry if I'm wrong (because I'm not native-English speaker), but it seems to me, that mentioned statement:

UnsafeLazyInitialization is actually safe if Resource is immutable.

is torn out of the context. This statement is truly regarding to use initialization safety:

The guarantee of initialization safety allows properly constructed immutable objects to be safely shared across threads without synchronization

...

Initialization safety guarantees that for properly constructed objects, all threads will see the correct values of final fields that were set by the constructor

Answer 7

After reading through the post you linked more carefully, you are correct, the example you posted could conceivably (under the current memory model) return null. The relevant example is way down in the comments of the post, but effectively, the runtime can do this:

public class UnsafeLazyInitialization {
    private static Resource resource;

    public static Resource getInstance() {
        Resource tmp = resource;
        if (resource == null)
            tmp = resource = new Resource();  // unsafe publication
        return tmp;
    }
}

This obeys the constraints for a single-thread, but could result in a null return value if multiple threads are calling the method (the first assignment to tmp gets a null value, the if block sees a non-null value, tmp gets returned as null).

In order to make this "safely" unsafe (assuming Resource is immutable), you have to explicitly read resource only once (similar to how you should treat a shared volatile variable:

public class UnsafeLazyInitialization {
    private static Resource resource;

    public static Resource getInstance() {
        Resource cur = resource;
        if (cur == null) {
            cur = new Resource();
            resource = cur;
        }
        return cur;
    }
}

Answer 8

This is now a very long back thread, still given this question discusses many interesting workings of re-ordering and concurrency, I am involving here by though lately.

For a moment, if we do not involve concurrency, the actions and valid reorderings in multi-threaded situation.
"Can JVM use a cached value post write operation in single-thread context". I think no. Given there is a write operation in if condition can caching come in to play at all.
So back to the question, immutability ensure that the object is fully or correctly created before it's reference is accessible or published, so immutability definitely helps. But here there is a write operation after the object creation. So can the second read cache the value from pre-write, in the same thread or another. No. One thread might not know about the write in other thread (given there is no need for immediate visibility between threads). So won't the possibility of returning a false null (i.e after the object creation) be invalid. ( The code in question breaks singleton, but we are not bothered about the here)

Answer 9

It is indeed safe is UnsafeLazyInitialization.resource is immutable, i.e. the field is declared as final:

private static final Resource resource = new Resource();

It might also be considered as thread-safe if the Resource class itself is immutable and does not matter which instance you are using. In that case two calls could return different instances of Resource without issue apart from an increased memory consumption depending on the number of threads calling getInstance() at the same time).

It seems far-fetched though and I believe there is a typo, real sentence should be

UnsafeLazyInitialization is actually safe if *r*esource is immutable.

Answer 10

UnsafeLazyInitialization.getInstance() can never return null.

I'll use @assylias's table.

                              Some Thread
---------------------------------------------------------------------
 10: resource = null; //default value                                  //write
=====================================================================
           Thread 1               |          Thread 2                
----------------------------------+----------------------------------
 11: a = resource;                | 21: x = resource;                  //read
 12: if (a == null)               | 22: if (x == null)               
 13:   resource = new Resource(); | 23:   resource = new Resource();   //write
 14: b = resource;                | 24: y = resource;                  //read
 15: return b;                    | 25: return y;    

I'll use the line numbers for Thread 1. Thread 1 sees the write on 10 before the read on 11, and the read on line 11 before the read on 14. These are intra-thread happens-before relationships and don't say anything about Thread 2. The read on line 14 returns a value defined by the JMM. Depending on the timing, it may be the Resource created on line 13, or it may be any value written by Thread 2. But that write has to happen-after the read on line 11. There is only one such write, the unsafe publish on line 23. The write to null on line 10 is not in scope because it happened before line 11 due to intra-thread ordering.

It doesn't matter if Resource is immutable or not. Most of the discussion so far has focused on inter-thread action where immutability would be relevant, but the reordering that would allow this method to return null is forbidden by intra-thread rules. The relevant section of the spec is JLS 17.4.7.

For each thread t, the actions performed by t in A are the same as would be generated by that thread in program-order in isolation, with each write w writing the value V(w), given that each read r sees the value V(W(r)). Values seen by each read are determined by the memory model. The program order given must reflect the program order in which the actions would be performed according to the intra-thread semantics of P.

This basically means that while reads and writes may be reordered, reads and writes to the same variable have to appear like they happen in order to the Thread that executes the reads and writes.

There's only a single write of null (on line 10). Either Thread can see its own copy of resource or the other Thread's, but it cannot see the earlier write to null after it reads either Resource.

As a side note, the initialization to null takes place in a separate thread. The section on Safe Publication in JCIP states:

Static initializers are executed by the JVM at class initialization time; because of internal synchronization in the JVM, this mechanism is guaranteed to safely publish any objects initialized in this way [JLS 12.4.2].

It may be worth trying to write a test that gets UnsafeLazyInitialization.getInstance() to return null, and that gets some of the proposed equivalent rewrites to return null. You'll see that they're not truly equivalent.

EDIT

Here's an example that separates reads and writes for clarity. Let's say there's a public static variable object.

public static Object object = new Integer(0);

Thread 1 writes to that object:

object = new Integer(1);
object = new Integer(2);
object = new Integer(3);

Thread 2 reads that object:

System.out.println(object);
System.out.println(object);
System.out.println(object);

Without any form of synchronization providing inter-thread happens-before relationships, Thread 2 can print out lots of different things.

1, 2, 3
0, 0, 0
3, 3, 3
1, 1, 3
etc.

But it cannot print out a decreasing sequence like 3, 2, 1. The intra-thread semantics specified in 17.4.7 severely limit reordering here. If instead of using object three times we changed the example to use three separate static variables, many more outputs would be possible because there would be no restrictions on reordering.