Consider a singleton:
public class Singleton {
private static Singleton instance;
private final Object important;
protected Singleton() {
important = Object.class; // or something important
}
public static Singleton instance() {
if(instance == null) {
instance = new Singleton();
}
return instance;
}
public Object getImportant() { return important; }
}
This works well for a single threaded program, but there's a race in the instance() method. If one thread evaluates the if(instance == null) test and starts the Singleton() constructor, but is then pre-emepted, another thread can run the test again and evaluate it to false, and also run the constructor, breaking the singleton pattern.
A solution is to synchronize the instance() method.
public static synchronized Singleton instance() {
if(instance == null) {
instance = new Singleton();
}
return instance;
}This eliminates the race (only one thread can be within a synchronized block), but making a synchronized call is expensive -- on the order of 100 times more than a regular call. The proposed solution to this problem is to use a double-checked lock:
public static Singleton instance() {
if(instance == null) {
synchronized(this) {
if(instance == null) {
instance = new Singleton();
}
}
}
return instance;
}Here, an inexpensive test is preformed before execution of the synchronized block. If the singleton has already been initialized, then the synchronized block does not execute, saving the synchronization overhead and maintaining the singleton pattern.
The problem with the double-checked lock is that it doesn't work without a strictly enforced memory model. Most systems do not have a strict enough memory model for it to work. A compiler (or VM, or whatever) can (and will) re-order instructions that it feels that it can reorder to improve performance, and the double-checked lock will fall victim to the reordering.
Without reordering, we expect execution to occur as it is written:
if(assigned to null) {
synchronize
if(assigned to null)
initialize object
assign object's memory location
un-synchronize
returnBut with reordering, the scheme can be broken:
if(assigned to null) {
synchronize
if(assigned to null)
assign object's memory location
initialize object
un-synchronize
returnThe difference is subtle. It's fine in a single-threaded context (which is why the compiler thinks that it can re-order), but it breaks the lock when multi-threaded. A thread can be pre-empted between the assignment and the initialization. Another thread can come and run the outer test, discover that the reference has been assigned a non-null value, and continue executing with a reference to an un-initialized object. This causes undefined (bad) behaviour in the second thread.
The best solution to this problem is to simply not use lazy initialization. Lazy initialization is sexy because it defers construction until it's needed. It saves memory (for a while) and delays execution (for a while), but the memory cost and execution time is paid eventually. If you statically initialize the singleton, it will all be paid for on the first reference to the class. This will make your start-up more expensive, but those costs (in space and time) would have been paid eventually.
A common objection to this is that with lazy initialization, you only pay for the init if the singleton is used. Static initialization still retains this property. The initialization will only occur if the class is loaded by the classloader (or linked by the linker, or loaded by the page-fault handler), and is therefore going to be in use. The prescribed (and preferred in most cases) solution is:
public class Singleton {
private static Singleton instance = new Singleton();
private final Object important;
protected Singleton() {
important = Object.class; // or something important
}
public static Singleton instance() {
return instance;
}
public Object getImportant() { return important; }
}
The second solution is to enforce the ordering of the instructions. As of Java 1.5, the volatile keyword prevents the reordering of reads/writes to a variable in relation to other variables (in addition to preventing local copies of variables). [The old behaviour was to enforce ordering on the variable itself, without respect to other variables, allowing the singleton to be assigned before its non-volatile instance variables were initialized.] Putting the volatile keyword on the singleton instance will prevent the variable from being assigned before its non-volatile instance variables are initialized:
private volatile static Singleton instance;
public static Singleton instance() {
if(instance == null) {
synchronized(this) {
if(instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
Using the volatile keyword in itself is expensive. It forces the the thread to use the main-memory copy of any variables, preventing them from being stored in CPU registers, in non-coherent caches, and a host of other optimizations. If there is no thread contention for the resource, using volatile may cost as much as a lock (since there would be no signaling by the semaphore). In the volatile solution, this cost is paid for every method call, not just when locking is required. If there is low thread contention, it may cost as much as locking on every call.
Most developers are not familiar with the volatile keyword. It was mostly ignored pre-Java-1.5 by VM makers, and it didn't work as advertised. Even if it had worked, it's old semantics were not very useful. Accordingly, the development community largely ignored it. Relying on it for your singletons will risk naive developers from removing it, or following the double-checked lock pattern but missing the volatile keyword, or deploying the pattern to a pre-1.5 VM where it will not work. It should be avoided in favor of the statically initialized singleton.
[Aside: these arguments apply to C/C++ and other languages as well as Java.]
