How Program Reordering Breaks Double-Checked Locking in Java

Speed is one of the most sought-after goals in computing. Whether it be software developers, compiler designers or processor manufacturers, one question that is constantly on their mind is “How can I make this run faster?”. Each performance increment furthers the goals, thus making the strive for speed a never-ending process. One fine technique that has been discovered so far in this process of achieving speed is program reordering. Program reordering is the technique of changing the sequential order of execution of the source code by compilers and processors as a means of optimization.

Of course, as with most good things in life, this enhancement too has a price to pay. It makes the programs and their execution quite complex. With the slightest mistake, our code can end up behaving in rather unexpected ways. But as it turns out, the ease and the comfort of sequential consistency in our code is something we must give up if we want to realize the benefits of program reordering.

Each programming language has come up with its own rule set on how to deal with instruction rearrangement. When it comes to Java, the JVM is no stranger to program reordering. The Java Language Specification has declared a set of rules under the Java Memory Model (JMM) regarding program reordering. These rules are to be followed by the JVM and the JIT compilers. Irrespective of the JVM implementation, these rules are the minimum guarantees that we have and that we must abide by to ensure the accuracy of the code we write.

One assurance is that the result or the output of a single independent thread (whether it was rearranged or not) will always be equal to the result given by its sequential execution. This is called within-thread as-if-serial semantics. However in a multithreaded environment, if there is intervention among the threads, things get a little out of hand. To better understand this let us look at how program reordering works under the hood.

It is simple! If there is no data dependency or control dependency between two statements, then those two statements may be reordered. As easy as that may sound, if you do not know what data/control dependency is, new questions might have bubbled up in your head than there were before. This can all be answered with the following example.

There is a data dependency between the first and the second statement. Why? Because the result of statement two depends on the data assigned to the variable a in the first statement. Similarly, there is a control dependency between statement four and five. The execution of statement five depends on the evaluation of the condition in the fourth statement.

Now let us remind how program reordering works again. If there is no data dependency or control dependency between two statements, then those two statements may be reordered.

If it still is not very clear, let us draw the dependency diagram and see if it helps.

Dependency Diagram

As you can see, the statement b = 1; does not depend on any of the other statements. So, the point of time it is executed within this code snippet does not matter as long as it is run before the end. In other words, the relative order of the execution of b = 1; and the other statements does not change the output as long as there is only one thread. So, the Java compilers or the JVM or the processor may choose to reorder the statement to optimize the program execution.

In practice, reordering can happen when we initialize an object in Java.

Person john = new Person(“John”);

Even though this appears as a single line of code, internally it is run in several steps. Strictly speaking, object initialization is not atomic. It can be outlined in three general steps.

1. Allocate memory for the object
2. Run its constructor
3. Assign the object to its reference

Notice how the second and third actions are independent of each other. They have no data or control dependency. So as the reordering rule permits, the order in which they are actually executed can differ from time to time. However, at this point, things start to get a little shaky. It is because if reordering happens here, that essentially means we have references to objects that have not run their constructor method yet! And that surely is not a good sign.

Where does it all break down? We do not have to look far. Double checked locking is the answer. It is the clever little solution that is used in the lazy initialization of thread-safe Singleton design pattern that makes block level synchronization possible instead of the more expensive method level synchronization. Yes, it is clever, but not thread-safe. Below is its implementation.

public class Singleton {
    private static volatile Singleton instance;
    private Singleton() {}
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Sing;eton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

The mechanics of why double-checked locking does not work is as follows. Let thread A run the getInstance( ) method. It evaluates both the if conditions as true i.e. the instance variable is null. At this point, thread A has acquired the lock for the synchronized block as well. All it has to run is the Singleton initialization code. It runs this line too and the JVM assigns the reference before calling the constructor method. Suddenly, the control is passed on to another thread, thread B. Thread B also gets inside the getInstance( ) method and it sees the instance variable is not null so a Singleton whose constructor is not run is returned!

It is true that eager initialization and method level synchronization does not cause this problem, but we moved from those to the double-checked locking method because it was better. Usually, lazy initialization is preferred over eager initialization in the interest of better memory utilization and reduced loading time. Double-checked locking increased performance by requiring synchronization only once when the Singleton is initialized. So, is there another fix? Well, yes.

First, the instance variable can be made volatile in Java 5 or higher environments. That is because the Java Memory Model guarantees that a write to a volatile variable is visible to all subsequent reads of the same variable. We just have to add the keyword volatile at the variable declaration.

private static volatile Singleton instance;

The other solution is called the initialization-on-demand holder. It is a form of lazy initialization with an additional inner Holder class. As it turns out, this is even more efficient than all the other methods.

public class Singleton {
    private Singleton() {}
    private static class SingletonHolder {
        static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }
}

To sum up, this article explains how program reordering breaks the double-checked locking in Java. Broken double-checked locking is not the only disarray caused by program reordering. For example, reordering may also cause unsafe publication. But that is better left for another discussion of its own.

References

Goetz, B. and Peierls, T., 2006. Java Concurrency In Practice. Upper Saddle River, NJ [etc.]: Addison-Wesley.

Hawkins, D., 2017. Concurrency Concepts In Java.