The unary bitwise complement operator "~" inverts a bit pattern; it can be applied to any of the integral types, making every "0" a "1" and every "1" a "0". For example, a byte contains 8 bits; applying this operator to a value whose bit pattern is "00000000" would change its pattern to "11111111".

The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand. The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.

The bitwise & operator performs a bitwise AND operation.

The bitwise ^ operator performs a bitwise exclusive OR operation.

The bitwise | operator performs a bitwise inclusive OR operation.

Signed by: David Bacon (IBM Research) Joshua Bloch (Javasoft), Jeff Bogda, Cliff Click (Hotspot JVM project), Paul Haahr, Doug Lea, Tom May, Jan-Willem Maessen, Jeremy Manson, John D. Mitchell (jGuru) Kelvin Nilsen, Bill Pugh, Emin Gun Sirer

Double-Checked Locking is widely cited and used as an efficient method for implementing lazy initialization in a multithreaded environment.

Unfortunately, it will not work reliably in a platform independent way when implemented in Java, without additional synchronization. When implemented in other languages, such as C++, it depends on the memory model of the processor, the reorderings performed by the compiler and the interaction between the compiler and the synchronization library. Since none of these are specified in a language such as C++, little can be said about the situations in which it will work. Explicit memory barriers can be used to make it work in C++, but these barriers are not available in Java.

To first explain the desired behavior, consider the following code:

// Single threaded version class Foo { private Helper helper = null; public Helper getHelper() { if (helper == null) helper = new Helper(); return helper; } // other functions and members... }

If this code was used in a multithreaded context, many things could go wrong. Most obviously, two or more Helper objects could be allocated. (We'll bring up other problems later). The fix to this is simply to synchronize the getHelper() method:

// Correct multithreaded version class Foo { private Helper helper = null; public synchronized Helper getHelper() { if (helper == null) helper = new Helper(); return helper; } // other functions and members... }

The code above performs synchronization every time getHelper() is called. The double-checked locking idiom tries to avoid synchronization after the helper is allocated:

// Broken multithreaded version // "Double-Checked Locking" idiom class Foo { private Helper helper = null; public Helper getHelper() { if (helper == null) synchronized(this) { if (helper == null) helper = new Helper(); } return helper; } // other functions and members... }

Unfortunately, that code just does not work in the presence of either optimizing compilers or shared memory multiprocessors.

It doesn't work

There are lots of reasons it doesn't work. The first couple of reasons we'll describe are more obvious. After understanding those, you may be tempted to try to devise a way to "fix" the double-checked locking idiom. Your fixes will not work: there are more subtle reasons why your fix won't work. Understand those reasons, come up with a better fix, and it still won't work, because there are even more subtle reasons.

Lots of very smart people have spent lots of time looking at this. There is no way to make it work without requiring each thread that accesses the helper object to perform synchronization.

The first reason it doesn't work

The most obvious reason it doesn't work it that the writes that initialize the Helper object and the write to the helper field can be done or perceived out of order. Thus, a thread which invokes getHelper() could see a non-null reference to a helper object, but see the default values for fields of the helper object, rather than the values set in the constructor.

If the compiler inlines the call to the constructor, then the writes that initialize the object and the write to the helper field can be freely reordered if the compiler can prove that the constructor cannot throw an exception or perform synchronization.

Even if the compiler does not reorder those writes, on a multiprocessor the processor or the memory system may reorder those writes, as perceived by a thread running on another processor.

Doug Lea has written a more detailed description of compiler-based reorderings.

A test case showing that it doesn't work

Paul Jakubik found an example of a use of double-checked locking that did not work correctly. A slightly cleaned up version of that code is available here.

When run on a system using the Symantec JIT, it doesn't work. In particular, the Symantec JIT compiles

singletons[i].reference = new Singleton();

to the following (note that the Symantec JIT using a handle-based object allocation system).

0206106A   mov         eax,0F97E78h
0206106F   call        01F6B210                  ; allocate space for
; Singleton, return result in eax
02061074   mov         dword ptr [ebp],eax       ; EBP is &singletons[i].reference
; store the unconstructed object here.
02061077   mov         ecx,dword ptr [eax]       ; dereference the handle to
; get the raw pointer
02061079   mov         dword ptr [ecx],100h      ; Next 4 lines are
0206107F   mov         dword ptr [ecx+4],200h    ; Singleton's inlined constructor
02061086   mov         dword ptr [ecx+8],400h
0206108D   mov         dword ptr [ecx+0Ch],0F84030h

As you can see, the assignment to singletons[i].reference is performed before the constructor for Singleton is called. This is completely legal under the existing Java memory model, and also legal in C and C++ (since neither of them have a memory model).

A fix that doesn't work

Given the explanation above, a number of people have suggested the following code:

// (Still) Broken multithreaded version // "Double-Checked Locking" idiom class Foo { private Helper helper = null; public Helper getHelper() { if (helper == null) { Helper h; synchronized(this) { h = helper; if (h == null) synchronized (this) { h = new Helper(); } // release inner synchronization lock helper = h; } } return helper; } // other functions and members... }

This code puts construction of the Helper object inside an inner synchronized block. The intuitive idea here is that there should be a memory barrier at the point where synchronization is released, and that should prevent the reordering of the initialization of the Helper object and the assignment to the field helper.

Unfortunately, that intuition is absolutely wrong. The rules for synchronization don't work that way. The rule for a monitorexit (i.e., releasing synchronization) is that actions before the monitorexit must be performed before the monitor is released. However, there is no rule which says that actions after the monitorexit may not be done before the monitor is released. It is perfectly reasonable and legal for the compiler to move the assignment helper = h; inside the synchronized block, in which case we are back where we were previously. Many processors offer instructions that perform this kind of one-way memory barrier. Changing the semantics to require releasing a lock to be a full memory barrier would have performance penalties.

More fixes that don't work

There is something you can do to force the writer to perform a full bidirectional memory barrier. This is gross, inefficient, and is almost guaranteed not to work once the Java Memory Model is revised. Do not use this. In the interests of science, I've put a description of this technique on a separate page. Do not use it.

However, even with a full memory barrier being performed by the thread that initializes the helper object, it still doesn't work.

The problem is that on some systems, the thread which sees a non-null value for the helper field also needs to perform memory barriers.

Why? Because processors have their own locally cached copies of memory. On some processors, unless the processor performs a cache coherence instruction (e.g., a memory barrier), reads can be performed out of stale locally cached copies, even if other processors used memory barriers to force their writes into global memory.

I've created a separate web page with a discussion of how this can actually happen on an Alpha processor.

Is it worth the trouble?

For most applications, the cost of simply making the getHelper() method synchronized is not high. You should only consider this kind of detailed optimizations if you know that it is causing a substantial overhead for an application.

Very often, more high level cleverness, such as using the builtin mergesort rather than handling exchange sort (see the SPECJVM DB benchmark) will have much more impact.

Making it work for static singletons

If the singleton you are creating is static (i.e., there will only be one Helper created), as opposed to a property of another object (e.g., there will be one Helper for each Foo object, there is a simple and elegant solution.

Just define the singleton as a static field in a separate class. The semantics of Java guarantee that the field will not be initialized until the field is referenced, and that any thread which accesses the field will see all of the writes resulting from initializing that field.

class HelperSingleton { static Helper singleton = new Helper(); }

It will work for 32-bit primitive values

Although the double-checked locking idiom cannot be used for references to objects, it can work for 32-bit primitive values (e.g., int's or float's). Note that it does not work for long's or double's, since unsynchronized reads/writes of 64-bit primitives are not guaranteed to be atomic.

// Correct Double-Checked Locking for 32-bit primitives class Foo { private int cachedHashCode = 0; public int hashCode() { int h = cachedHashCode; if (h == 0) synchronized(this) { if (cachedHashCode != 0) return cachedHashCode; h = computeHashCode(); cachedHashCode = h; } return h; } // other functions and members... }

In fact, assuming that the computeHashCode function always returned the same result and had no side effects (i.e., idempotent), you could even get rid of all of the synchronization.

// Lazy initialization 32-bit primitives // Thread-safe if computeHashCode is idempotent class Foo { private int cachedHashCode = 0; public int hashCode() { int h = cachedHashCode; if (h == 0) { h = computeHashCode(); cachedHashCode = h; } return h; } // other functions and members... }

Making it work with explicit memory barriers

It is possible to make the double checked locking pattern work if you have explicit memory barrier instructions. For example, if you are programming in C++, you can use the code from Doug Schmidt et al.'s book:

// C++ implementation with explicit memory barriers // Should work on any platform, including DEC Alphas // From "Patterns for Concurrent and Distributed Objects", // by Doug Schmidt template <class TYPE, class LOCK> TYPE * Singleton<TYPE, LOCK>::instance (void) { // First check TYPE* tmp = instance_; // Insert the CPU-specific memory barrier instruction // to synchronize the cache lines on multi-processor. asm ("memoryBarrier"); if (tmp == 0) { // Ensure serialization (guard // constructor acquires lock_). Guard<LOCK> guard (lock_); // Double check. tmp = instance_; if (tmp == 0) { tmp = new TYPE; // Insert the CPU-specific memory barrier instruction // to synchronize the cache lines on multi-processor. asm ("memoryBarrier"); instance_ = tmp; } return tmp; }

Fixing Double-Checked Locking using Thread Local Storage

Alexander Terekhov (TEREKHOV@de.ibm.com) came up clever suggestion for implementing double checked locking using thread local storage. Each thread keeps a thread local flag to determine whether that thread has done the required synchronization.

class Foo { /** If perThreadInstance.get() returns a non-null value, this thread has done synchronization needed to see initialization of helper */ private final ThreadLocal perThreadInstance = new ThreadLocal(); private Helper helper = null; public Helper getHelper() { if (perThreadInstance.get() == null) createHelper(); return helper; } private final void createHelper() { synchronized(this) { if (helper == null) helper = new Helper(); } // Any non-null value would do as the argument here perThreadInstance.set(perThreadInstance); } }

The performance of this technique depends quite a bit on which JDK implementation you have. In Sun's 1.2 implementation, ThreadLocal's were very slow. They are significantly faster in 1.3, and are expected to be faster still in 1.4. Doug Lea analyzed the performance of some techniques for implementing lazy initialization.

Under the new Java Memory Model

As of JDK5, there is a new Java Memory Model and Thread specification.

Fixing Double-Checked Locking using Volatile

JDK5 and later extends the semantics for volatile so that the system will not allow a write of a volatile to be reordered with respect to any previous read or write, and a read of a volatile cannot be reordered with respect to any following read or write. See this entry in Jeremy Manson's blog for more details.

With this change, the Double-Checked Locking idiom can be made to work by declaring the helper field to be volatile. This does not work under JDK4 and earlier.

// Works with acquire/release semantics for volatile // Broken under current semantics for volatile class Foo { private volatile Helper helper = null; public Helper getHelper() { if (helper == null) { synchronized(this) { if (helper == null) helper = new Helper(); } } return helper; } }

Double-Checked Locking Immutable Objects

If Helper is an immutable object, such that all of the fields of Helper are final, then double-checked locking will work without having to use volatile fields. The idea is that a reference to an immutable object (such as a String or an Integer) should behave in much the same way as an int or float; reading and writing references to immutable objects are atomic.

Descriptions of double-check idiom

• Reality Check, Douglas C. Schmidt, C++ Report, SIGS, Vol. 8, No. 3, March 1996.
• Double-Checked Locking: An Optimization Pattern for Efficiently Initializing and Accessing Thread-safe Objects, Douglas Schmidt and Tim Harrison. 3rd annual Pattern Languages of Program Design conference, 1996
• Lazy instantiation, Philip Bishop and Nigel Warren, JavaWorld Magazine
• Programming Java threads in the real world, Part 7, Allen Holub, Javaworld Magazine, April 1999.
• Java 2 Performance and Idiom Guide, Craig Larman and Rhett Guthrie, p100.
• Java in Practice: Design Styles and Idioms for Effective Java, Nigel Warren and Philip Bishop, p142.
• Rule 99, The Elements of Java Style, Allan Vermeulen, Scott Ambler, Greg Bumgardner, Eldon Metz, Trvor Misfeldt, Jim Shur, Patrick Thompson, SIGS Reference library
• Global Variables in Java with the Singleton Pattern, Wiebe de Jong, Gamelan

1. General Steps
To implement this design pattern we need to consider the following 4 steps:
Step 1: Provide a default Private constructor
public class SingletonObjectDemo {

 // Note that the constructor is private
 private SingletonObjectDemo() {
  // Optional Code
 }
}

Step 2: Create a Method for getting the reference to the Singleton Objectpublic class SingletonObjectDemo {

 private static SingletonObject singletonObject;
 // Note that the constructor is private
 private SingletonObjectDemo() {
  // Optional Code
 }
 public static SingletonObjectDemo getSingletonObject() {
  if (singletonObject == null) {
   singletonObject = new SingletonObjectDemo();
  }
  return singletonObject;
 }
}

     We write a public static getter or access method to get the instance of the Singleton Object at runtime. First time the object is created inside this method as it is null. Subsequent calls to this method returns the same object created as the object is globally declared (private) and the hence the same referenced object is returned.

Step 3: Make the Access method Synchronized to prevent Thread Problems.

public static synchronized SingletonObjectDemo getSingletonObject()

It could happen that the access method may be called twice from 2 different classes at the same time and hence more than one object being created. This could violate the design patter principle. In order to prevent the simultaneous invocation of the getter method by 2 threads or classes simultaneously we add the synchronized keyword to the method declaration

Step 4: Override the Object clone method to prevent cloning

We can still be able to create a copy of the Object by cloning it using the Object’s clone method. This can be done as shown below

SingletonObjectDemo clonedObject = (SingletonObjectDemo) obj.clone();

This again violates the Singleton Design Pattern's objective. So to deal with this we need to override the Object’s clone method which throws a CloneNotSupportedException exception.

public Object clone() throws CloneNotSupportedException {
throw new CloneNotSupportedException();
}

The below program shows the final Implementation of Singleton Design Pattern in java, by using all the 4 steps mentioned above.class SingletonClass {

 private static SingletonClass singletonObject;
 /** A private Constructor prevents any other class from instantiating. */
 private SingletonClass() {
  //  Optional Code
 }
 public static synchronized SingletonClass getSingletonObject() {
  if (singletonObject == null) {
   singletonObject = new SingletonClass();
  }
  return singletonObject;
 }
 public Object clone() throws CloneNotSupportedException {
  throw new CloneNotSupportedException();
 }
}

public class SingletonObjectDemo {

 public static void main(String args[]) {
  //  SingletonClass obj = new SingletonClass();  
                //Compilation error not allowed
  SingletonClass obj = SingletonClass.getSingletonObject();
  // Your Business Logic
  System.out.println("Singleton object obtained");
 }
}

2. Implemetion principles

(1).The solution of Bill Pugh

This is the recommended method. It is known as the initialization on demand holder idiom and is as lazy as possible. Moreover, it works in all known versions of Java. This solution is the most portable across different Java compilers and virtual machines.

The inner class is referenced no earlier (and therefore loaded no earlier by the class loader) than the moment that getInstance() is called. Thus, this solution is thread-safe without requiring special language constructs (i.e. volatile and/or synchronized).
 public class Singleton {
   // Protected constructor is sufficient to suppress unauthorized calls to the constructor
   protected Singleton() {}
 
   /**
    * SingletonHolder is loaded on the first execution of Singleton.getInstance()
    * or the first access to SingletonHolder.INSTANCE , not before.
    */
   private static class SingletonHolder {
     private final static Singleton INSTANCE = new Singleton();
   }
 
   public static Singleton getInstance() {
     return SingletonHolder.INSTANCE;
   }
 }

(2).Traditional simple way

Just like the one above, this solution is thread-safe without requiring special language constructs, but it lacks the laziness. The INSTANCE is created as soon as the Singleton class loads. That might even be long before getInstance() is called. It might be (for example) when some static method of the class is used. If laziness is not needed or the instance needs to be created early in the application's execution, this (slightly) simpler solution can be used:
 public class Singleton {
   public final static Singleton INSTANCE = new Singleton();
 
   // Protected constructor is sufficient to suppress unauthorized calls to the constructor
   protected Singleton() {}
 }

Sometimes the static final field is made private and a static factory-method is provided to get the instance. This way the underlying implementation may change easily while it has no more performance-issues on modern JVMs.

(3).Java 5 solution

If and only if the compiler used is Java 5 (also known as Java 1.5) or newer, AND all Java virtual machines the application is going to run on fully support the Java 5 memory model, then (and only then) the volatile double checked locking can be used (for a detailed discussion of why it should never be done before Java 5 see The "Double-Checked Locking is Broken" Declaration):
 public class Singleton {
   private static volatile Singleton INSTANCE;
 
   // Protected constructor is sufficient to suppress unauthorized calls to the constructor
   protected Singleton() {}
 
   public static Singleton getInstance() {
      if (INSTANCE == null) {
         synchronized(Singleton.class) {
           if (INSTANCE == null)
             INSTANCE = new Singleton();
         }
      }
      return INSTANCE;
   }
}

Allen Holub (in "Taming Java Threads", Berkeley, CA: Apress, 2000, pp. 176–178) notes that on multi-CPU systems (which are widespread as of 2007), the use of volatile may have an impact on performance approaching to that of synchronization, and raises the possibility of other problems. Thus this solution has little to recommend it over Pugh's solution described above.

(4).The Enum-way

In the second edition of his book "Effective Java" Joshua Bloch claims that "a single-element enum type is the best way to implement a singleton" for any Java that supports enums. The use of an enum is very easy to implement and has no drawbacks regarding serializable objects, which have to be circumvented in the other ways.
 public enum Singleton {
   INSTANCE;
 }

or
&#xhhhh;

where nnnn is the code point in decimal form, and hhhh is the code point in hexadecimal form. The x must be lowercase in XML documents. The nnnn or hhhh may be any number of digits and may include leading zeros. The hhhh may mix uppercase and lowercase, though uppercase is the usual style.

(see wiki)