One more look at Double-Checked Locking

28

I was talking with my friend at lunch yesterday about the good old days when double-checked locking was all the rage. We’re both in the midst of reading the totally excellent Java Concurrency in Practice by Brian Goetz, et al. (If you haven’t read it yet, go buy it today!)

Double-checked locking

To refresh your memory, double-checked locking was a classic technique (now considered broken, bad, and evil in its original form) to lazily construct a singleton while (usually) avoiding the performance hit of synchronization.

So, say you want only a single PieChucker in your high performance app. You might use double-checked locking like this:

// Old-school double-checked locking – THIS IS BROKEN!!!
public class PieChucker {
// Singleton instance, lazily initialized
private static PieChucker instance;

public static PieChucker getInstance() {
if(instance == null) {
synchronized(PieChucker.class) {
if(instance == null) {
instance = new PieChucker();
}
}
}
return instance;
}

// Private as it’s only constructed by getInstance()
private PieChucker() {
}

public void fling(Target target) {
// … chuck pie at target
}
}

My friend and I were trying to recall precisely why this is broken. We hand-waved around it for awhile but didn’t quite have it nailed, so I went home and looked it up (in the aforementioned book). I thought I would recap it here as this is a point that could serve to be hammered home until I learn it cold.

Happens-before

Consider this scenario: Thread 1 enters getInstance(), sees null on both if checks, and starts constructing the singleton. Thread 2 enters getInstance() and checks the first if check. At this point, thread 2 has not yet entered the synchronized block, so has not established a “happens-before” relationship with Thread 1. It is thus undefined whether Thread 2 will see a fully constructed instance (you got lucky!), a partially constructed instance (probably real bad), or null (causing two singletons to get constructed and breaking the singelton-ness).

So, what do you do instead? Actually, there are a variety of safe alternatives:

  1. Synchronized locking – lazy
  2. Double-checked locking with volatile – lazy
  3. Static initialization – eager
  4. Initialize on demand – lazy

Synchronized locking

One obvious change to the double-checked locking pattern to make it safe is to remove the first if-check and fall back to a fully-synchronized form of getInstance():

// Lazy synchronized locking
public class PieChucker {
// Singleton instance, lazily initialized
private static PieChucker instance;

public static PieChucker getInstance() {
synchronized(PieChucker.class) {
if(instance == null) {
instance = new PieChucker();
}
}
return instance;
}


}

This is guaranteed to be safe due to the synchronized block, which establishes a happens-before relationship. The down-side is that you must enter the synchronized block on every call to getInstance(). However, synchronization on modern JVMs is much faster than it was when double-checked locking was first popular.

Double-checked locking with volatile

If you want to avoid the synchronized block, you can actually fix double-checked locking by using volatile on the instance attribute. The getInstance() method requires no change.

private static volatile PieChucker instance;

Declaring instance volatile basically means that an update of the variable establishes a happens-before relationship. It’s kind of like having the readers and writers of the volatile being enclosed in synchronized blocks such that the reader is guaranteed to see the updated, safely published version written by the writer.

This form of double-checked locking is thread-safe and probably faster than the fully synchronized form, although the differences will be small and vary between platforms. Note: This is not guaranteed to work on JVMs prior to Java 5. Your mileage may vary. As of Java 5, the Java Memory Model was formalized and this behavior is guaranteed.

Static initialization

Another option is to give up the lazy instantiation of the singleton. In cases where singletons have little initialization state and are likely to be used, this will be better than any lazy strategy. So, PieChucker might look like this:

// Static initialization – eager
public class PieChucker {
// Singleton instance, eagerly initialized
private static PieChucker instance = new PieChucker();

public static PieChucker getInstance() {
return instance;
}


}

Static initialization is guaranteed to be thread-safe and no synchronization must be incurred. If your singleton is a candidate for eager initialization, I’d recommend using it as it’s so simple.

Initialize on demand

If you really want lazy initialization, we can do better! Because static classes are not initialized until needed (and the initialization is guaranteed to be thread-safe), the following idiom is safe and incurs no synchronization (plus, it’s shorter):

// Lazy initialization, no synchronization
public class PieChucker {
// Singleton class, lazy initialized
private static class InstanceHolder {
static PieChucker instance = new PieChucker();
}

public static PieChucker getInstance() {
return InstanceHolder.instance;
}


}

I’ve blogged before on one instance where this is used in the JVM itself. Integer.valueOf() lazily caches Integer objects from -128 to 127 (as required by the JVM specification). But, you don’t want to incur the cost of creating the cache unless it’s needed, so the cache is initialized on demand via a private static class.

I must credit Bob Lee with my first introduction to the idiom, although it is probably best documented in Josh Bloch’s Effective Java (#48). You might find this reference or this presentation to be of interest regarding the Java Memory Model, double-checked locking, happens-before, etc.

Comments

28 Responses to “One more look at Double-Checked Locking”
  1. Coincidentally, I was just thinking about double checked locking earlier. I hadn’t realised volatile worked on 1.5+, that’s good to know.

    My problem was slightly different, in that I was able to tweak it so that I could ‘undo’ the operation we were trying to perform only once. So I ended up using the following:

    public class Foo
    {
    private final AtomicReference bar = …
    BarSource baz = …

    public Bar getBar()
    {
    if(bar.get() == null)
    {
    synchronized(baz)
    {
    if (!bar.weakCompareAndSet(null, baz)) baz.undo();

    return baz.get();
    }
    }
    else return baz.get();
    }
    }

    So we use an atomic reference (which is a lot nicer in both usage and performance than synchronisation) to guarantee the memory consistency effects on the field and synchronize on the source of the object to guarantee the get/close consistency.

    I confess I’ve not tested this extensively yet, but I’m pretty sure it will work. It might be hard to adapt to the singleton case (unless you don’t care about instantiating more than one of your singletons as long as you don’t expose it), but I think it’s more flexible elsewhere.

  2. Dan says:

    The beauty of the static initialisation approach is that it is effectively lazy-loading. The instance is not created until the class is loaded and the class will not be loaded until is needed. Since the class is a singleton, it’s unlikely that there will be any reason to reference the class (and hence create the instance) other than by invoking getInstance().

  3. Hi Alex,

    This is a nice exploration of double-checked locking with good code examples. There was a point you touched on near the beginning where you said:

    “It is thus undefined whether Thread 2 will see a fully constructed instance (you got lucky!), a partially constructed instance (probably real bad), or null (causing two singletons to get constructed and breaking the singelton-ness).”

    In the double-checked locking with volatile section you hinted that using that method may still be a bad idea and that’s true. With double-checked locking with volatile you eliminate the possibility of getting a null reference, unfortunately the possibility of getting a partially constructed object still remains. The volatile variable guarantees the reference update in thread1 happens-before thread2 uses it, but there is no guarantee that the object itself is fully constructed, even with the Java 5 fix for the volatile keyword. Even though thread2 got a valid reference, thread1 may not be finished constructing or otherwise initializing (calling any init methods, loading caches or other resources, etc) the object. If the reference is to a primitive type variable you are in the clear but not if it is an object reference. At least this is my understanding of the specification. If I’m wrong please correct me.

    I’m glad you recommend using static initialization. It’s a simple and effective way of instantiating a singleton.

    I’ve found myself reading your blog several times in the last week and I really like it. Keep up the good blogging!

    Anthony

  4. Alex says:

    @Anthony: Actually, writing a reference to a volatile does constitute safe publication in Java 5+, so there is no danger of getting a partially constructed object.

    Thanks for reading!

  5. I just reviewed my copy of JCCiP and you are correct Alex. Seems like *my* memory model is broken! That’ll teach me to comment from memory.

    Thanks!

  6. locker says:

    In the original you don’t assign instance directly. You assign a temp and then when done constructing assign temp to instance.

  7. Alex says:

    @locker – Can’t say I’ve ever seen it done that way with a temp variable. Regardless, I think it would be equally broken.

  8. Although, my own memory model lacks similarily to Anthony’s, I think to remember that compiler optimization may break the temp-approach mentioned by locker. For optimization, the compiler may/will rearrange instructions, and the late assignment cannot be guaranteed. The compiler could actually decide to remove the local temp variable.

  9. Ugh, no matter the changes made to volatile, I’d still go with one of the two static intialize styles. They will have the best performance, ultimately (volatile member access is a bit slower, if I recall correctly).

    Two comments:
    – With volatile DCL, you could still initialize the constant twice — probably not what you intend.
    – With synchronized locking, you will get better performance by synchronizing the method than having a sync block.

    I can dig up some references for these assertions, but most of them come out of Peter Haggar’s Practical Java.

  10. Alex says:

    @Patrick: Howdy! Been a while…

    I don’t see how you could initialize the constant twice. Initialization is only done inside a synchronized block when the instance is null, so there is no way that two threads could ever be inside the critical section at the same time to initialize.

    I also think you are incorrect that synchronized methods are faster than a synchronized block. There is no advantage (to my knowledge) to marking at the method level; it’s merely a convenience that effectively wraps the body of the method in “synchronized(this) { }” for class methods or “synchronized(Foo.class) { }” for static methods. So, at best they are the same performance. It’s actually likely to be worse because you are probably using a wider scope for your critical section. In general, reducing the scope of your critical section to as few number of instructions as possible is the best thing you can do to reduce the contention.

    From what I’ve read from people much smarter than me, volatile is faster than synchronized as it utilizes hardware instructions that avoid any thread context switches or scheduling even in the case of contention. Eagerly initializing an instance should be fastest since you avoid the whole possibility of contention in the first place. The question is really whether it’s possible it will never be called, in which case it’s not a good idea to take the needless hit.

  11. I won’t pretend to know much if anything about the JVM and the JMM, but I’ll keep blathering on anyway…

    Volatile DCL:
    With the volatile, couldn’t two (or more) threads get past the if check, then wait in line for a lock on the object?

    Thread 1:
    – enter method
    – perform if check, it is true, enter “then” block
    – ask for a lock on MyClass.class object
    – thread control yielded
    Thread 2:
    – enter method
    – perform if check, it is still true, enter “then” block
    – thread control yielded
    Thread 1:
    – granted object lock, proceeds into sync block
    – thread control yielded
    Thread 2:
    – ask for a lock on MyClass.class object
    – thread control yielded
    Thread 1:
    – finish method
    – go on with life
    Thread 2:
    – granted object lock, proceeds into sync block
    – finish method
    – go on with life

    Re: Synchronized:
    According to Haggar’s Practical Java, page 118, the bytecode generated is significantly different for the following:

    public synchronzied int top1() {
    return intArr[0];
    }

    public int top2() {
    syncronized(this) {
    return intArr[0];
    }
    }

    The latter apparently has more to do, as cleanup and object lock release from exiting the sync block is now distinct from the method block. That being said, the performance improvement is minor, around 13%.

    It would be interesting to see the performance numbers on a lazy initializer like we are discussing, since it has slightly more code than those tiny examples.

    Pat.

  12. Alex says:

    Two or more threads can get past the first if check, and eventually past the synchronized lock, but only one will ever get past the second if check. Once the first thread gets into the synchronized block when instance is null, it will set the instance. When it leaves the synchronized block, all other waiting threads will be notified and see a consistent state for the volatile, so none of them will enter the second if block. So, only one thread will ever a) call PieChucker() and b) set the value for instance.

    You may be right on the synchronized method vs block – I don’t really know the details at the bytecode level. I’m not sure I would trust Practical Java though given its age (published in 2000). I can’t say I’ve seen any hard information on this on more recent JVMs. Maybe someone in the blogosphere will read this comment and do some awesome micro benchmarks to tell us the answer. :)

  13. Whoops, forgot the second if check. That would be the Double in double-checked locking.

    Re: sync on methods, if I wasn’t lazy, I could do a javap and find out if it is still true… but I am lazy.

    Anyway, my point is this: Initialize on class load (whether outer or inner) is, in the end, more straightforward, and has better performance. As you mentioned, if the class is not loaded, the constant is not created.

  14. Alex says:

    Actually, I googled it and found a very helpful article from (you guessed it)…Peter Haggar. I also did a very quick javap and it doesn’t seem much different now (which is what I would expect). The synchronized method is just annotated in the method_info structure. I imagine that the actual performance implications of all this are probably a lot different given the state of today’s JVM technology.

    Definitely agree on the initialize on class load.

  15. There is one other benefit to using one of the simple solutions: Less embarrassment for know-it-all programmers who don’t read the code closely. ;-)

  16. Anonymous says:

    <BeatDeadHorse>

    Section 16.2.4 in the aforementioned Java Concurrency in Practice lays it all out.

    The reason I couldn’t remember at lunch why DCL was broken is because DCL **does** prevent multiple threads from falsely detecting “null” and instantiating multiple instances. That was thought to be the whole point of DCL back in the day.

    But the authors explain my flawed thinking perfectly in section 16.2.4: “But at the time, synchronization was slow and, more importantly, not completely understood: the exclusion aspects were well enough understood, but the visibility aspects were not.”

    What I failed to appreciate, as you already pointed out, is that the real peril of DCL is that a thread can get a non-null reference to the singleton that is not safely published/initialized.

    So, actually, in your original post you are not correct in stating (under the “Happens Before” header) that “…or null (causing two singletons to get constructed and breaking the singelton-ness)”. I don’t believe that can happen with DCL even w/o volatile keyword. (You explained this yourself in your comment to Patrick.)

    </BeatDeadHorse>

  17. Scott Bale says:

    Sorry, meant to leave my name on the previous post.

  18. Peter Centgraf says:

    I’d like to reiterate Comment #2, which is quite important. For client code outside of java.lang, the “static initialization” and “initialize on demand” approaches are identical. Static initialization occurs when the class is loaded, and the class will not be loaded until other code makes reference to it. Since the only reason to make reference to a singleton is to use it, this is exactly what we want. The “initialize on demand” approach is only necessary for Integer because all of java.lang is loaded as part of the JVM boot process. For client code it is a total waste. Avoid the extra nested class!

  19. Alex says:

    @Peter – I think in general usage you’re right, however this is not true in all cases. There are certain operations that can be performed on a singleton class (like calling a static method) that will cause the singleton to be loaded from a static variable where it will not be loaded from a static holder class. Here’s an example:

    public class InitTest {
    
      public static void main(String arg[]) {
        System.out.println("Force singleton class to load");
        Singleton.test();
       
        System.out.println("\ngetInstance1");
        Singleton.getStaticInstance();
        
        System.out.println("\ngetInstance2");
        Singleton.getHolderInstance();
      } 
    }
    
    class Singleton {
      static {
        System.out.println("Loading Singleton class");
      }
      
      private static Singleton s1 = new Singleton();
      
      private static class SingletonHolder {
        static final Singleton s2 = new Singleton();
      }
      
      Singleton() {
        System.out.println("Constructing Singleton");
      }
      
      public static Singleton getStaticInstance() {
        return s1;
      }
      
      public static Singleton getHolderInstance() {
        return SingletonHolder.s2;
      }
      
      public static void test() {
        // do nothing with s1 or s2
      }
    }
    

    which when run prints:

    Force singleton class to load
    Loading Singleton class
    Constructing Singleton
    
    getInstance1
    
    getInstance2
    Constructing Singleton
    

    As you can see, calling the static Singleton.test() method causes s1 to be loaded in the static variable, but s2 is not constructed until it is actually asked for, so the “initialize on demand” idiom is slightly lazier. But, I admit that this scenario is probably not common and that most singleton classes have just a static getInstance() which will effectively behave the same with either a static variable or an “initialize on demand” class.

  20. Hi Alex

    Sorry talking about this topic after one year… I have a small request. Can you write an example code which shows that double checked locking might create partially singleton object ?

    I’m asking this question because I have just read information below from jvm spec…

    ******Just before a reference to the newly created object is returned as the result*****, the indicated constructor is processed to initialize the new object using the following procedure:

    1. Assign the arguments for the constructor to newly created parameter variables for this constructor invocation.
    2. If this constructor begins with an explicit constructor invocation of another constructor in the same class (using this), then evaluate the arguments and process that constructor invocation recursively using these same five steps. If that constructor invocation completes abruptly, then this procedure completes abruptly for the same reason; otherwise, continue with step 5.
    3. This constructor does not begin with an explicit constructor invocation of another constructor in the same class (using this). If this constructor is for a class other than Object, then this constructor will begin with an explicit or implicit invocation of a superclass constructor (using super). Evaluate the arguments and process that superclass constructor invocation recursively using these same five steps. If that constructor invocation completes abruptly, then this procedure completes abruptly for the same reason. Otherwise, continue with step 4.
    4. Execute the instance initializers and instance variable initializers for this class, assigning the values of instance variable initializers to the corresponding instance variables, in the left-to-right order in which they appear textually in the source code for the class. If execution of any of these initializers results in an exception, then no further initializers are processed and this procedure completes abruptly with that same exception. Otherwise, continue with step 5. (In some early implementations, the compiler incorrectly omitted the code to initialize a field if the field initializer expression was a constant expression whose value was equal to the default initialization value for its type.)
    5. Execute the rest of the body of this constructor. If that execution completes abruptly, then this procedure completes abruptly for the same reason. Otherwise, this procedure completes normally.

    What I understood from this is JVM will not return a reference which is not fully constructed.

    Note: I read the book you mentioned. And There was no example about partially constructed object in case of double checked locking.

  21. Alex says:

    @Erkin: Re-reading my original post, that may not be correct. Even if it was, I think it’s highly improbably that I could create an example showing it. :) The one case where a partially constructed object could occur would be if the “this” reference escaped during the construction of the object. The classic case for this is registering yourself as a listener with this during construction (for instance registering the singleton with some other singleton). If you do that then another object will have access to the singleton’s fields before they may have been set, creating a possible data race. You can find more info on this if you search for things like “safe publication” or “escape during construction”. Here’s one excellent article on the topic from Brian Goetz, which is also covered in his book Java Concurrency in Practice.

  22. Hi Alex

    Thanks for quick response. Definitely We can simulate partially constructed objects for collaborations (listeners, parent-child bidirectional relations).

    Cheers

  23. Steven says:

    Hi thanks for the article. I’m designing a new piece of software and wanted to use the Singleton pattern for some classes, but I also remembered that I heard that singletons are bad. I never really looked into before. I’m glad I did.

    I have the following question though. I’m using boost statechart and I see this as one of those times that a singleton is the correct solution for the state class. Am I correct in this assumption?

  24. Alex Miller says:

    @Steven: Sorry, not sure, haven’t used it.

  25. Thomas W says:

    Sorry, don’t think your post here is really correct. Double-checked locking with an inner synchronization block would appear quite safe — partly initialized objects are guarded within the “inner” synchronized block.

    “this” reference escaping, or being used externally during construction, is bad design. Constructors limit what you can do before calling super() for exactly this reason.

    Singletons registering themselves with other services, bad for memory leaks/ webapp unload/ lifetime control.
    Static singletons collaborating in parent/child relationships, that’s neither very plausible in an entity model nor good design.

    Anyway, business requirements are the #1 goal — and these days, as mentioned, synchronization is much more cheap.

    Code first, optimize later — unless you’re really going to be using the method heavily/ bottlenecking on performance, just use ‘synchronized’ keyword on the method & get on with the real (business) requirements.

    Regards.
    Tom

  26. Daniel says:

    @Tom

    > Sorry, don’t think your post here is really correct. Double-checked locking with an inner
    > synchronization block would appear quite safe — partly initialized objects are guarded within the
    > “inner” synchronized block.

    No they’re not guarded – the point is that the test “if(instance == null)” may be false *outside* the synchronized but the thread may see something different than the completely initialized object. This may be remedied by marking instance volatile since java 5. But this is already covered above.

Trackbacks

Check out what others are saying about this post...
  1. [...] If you do really need to use a singleton, please make sure you initialize it safely! [...]

  2. [...] You may find my article on Singleton construction, double-checked locking, etc of interest. Alex Miller – Pure Danger Tech [...]