The Break Room

Okay. It's time we put this one to bed, once and for all. If you have figured out how to make the DCL idiom work for Java, consider yourself among the brightest of the bright in computer science because you are alone. It has been well documented, since the late 90's that the DCL idiom will not work with the current Java Memory Model (JMM, Chap 17 of the spec). There seems to be one main tripping point programmers fall over.

They have no idea how free the compiler (or the u-processor running their code) is to optimize their solutions.

Furthmore, if someone has figured out a good solution, then why is there so much documentation stating that the problem is unsolvable? We are not talking about the average programmer here either. Some of our best scientists have studied this problem for years now, and have been unable to find a solution.

Consider a solution I was offered recently by an architect interviewing me for a programming position.

	public class Singleton {
		private static Singleton _instance;

		public static Singleton getInstance() {
			if(null == _instance) {
				_instance = getPrivateInstance();
			}

			return _instance;  
		}

		private static Singleton getPrivateInstance() {
			if(null == _instance) {
				return new Singleton();
			}
		}
	}

Now, I am sure you have caught the compiler problem already. What do we return from the private method when the instance is not null? The compiler is not going to like this. However, let's assume that the author made a simple mistake and in reality would have implemented something that at least compiles.

		private static Singleton getPrivateInstance() {
			if(null == _instance) {
				return new Singleton();
			} else {
				return _instance;
			}
		}

What is the compiler is allowed to do with your clever call to a synchronized method. Well, according to Dr. Bill Pugh, it is free to inline your method call. (This is my interpretation since in reality, the problem is at the op-code level and below.)

		public class Singleton {
			private static Singleton _instance;

			public static Singleton getInstance() {
				if(null == _instance) {
					synchronized(Singleton.class) {
						if(null == _instance) {
							_instance = new Singleton();
						} else {
							return _instance;
					}
				}
			}
		}

And just like that you are back to the plain-jane version of DCL. Thread A enters, sees that _instance is null, and enters the synchronized block. Thread A continues on and gets to the line _instance = new Singleton();. What happens if the compiler orders the op-codes in such a manner as to cause the assignment of the reference to occur before the creation of the object? In other words, the compiler may allocate the memory and initialize the pointer to that memory before it builds the object that will ultimately occupy that memory. So, the assignment has occured and now thread B enters the getInstance(); method and sees that the _instance reference is not null. In this perfectly legal scenario, thread B will end up with a reference to an object that doesn't exist.

The scariest part of the problem is how it can depend upon the hardware. If we are to be responsible for the differences in each vendor's VM implementation and each deployment's hardware architecture then a lot of programmers are going to be in for a rude awakening.

According to the many experts, the solution is to avoid DCL altogether and use the threading semantics of the class loader or declare the getInstance(); method synchronized. The rationale being that performance improvements have lowered the cost of synchronization by such a degree as to render the topic moot.

References

Pugh, W., The Java Memory Model
Bacon, Bloch, Bogda, Click, Haahr, Lea, May, Masessen, Mitchell, Nilsen, Pugh, Sirer "The Double-Checked Locking is Broken" Declaration
Lea, Doug Synchronization and the Java Memory Model from Concurrent Programming in Java
Goetz, B., Can double-checked locking be fixed?
Holub, A., Warning! Threading in a multiprocessor world

email exchange on a similar question

----- Original Message ----- 
From: "Bill Pugh"
To: "David McReynolds"
Sent: Thursday, February 19, 2004 3:09 PM
Subject: Re: JSR-133 and DCL

That is very much a standard DCL bug.

Here is one way you could get bit:

* The compiler could inline the call to getPrivateInstance
* The compiler could move the assignment to _instance inside the 
synchronized block
* The compiler could assign the address of the newly allocated object 
before flushing all initialization
   of the newly allocated object to shared memory.

On Feb 19, 2004, at 12:30 PM, David McReynolds wrote:

> Dear Dr. Pugh,
> 
> I hate to flog a dead horse, but was interviewing for a programmer 
> position the other day and someone proposed a rather naive solution to 
> the DCL idiom for java. I don't think it works but lack the detailed 
> knowledge of the JMM to explain why. In XP parlance, the code has a 
> smell about it.
> 
> public class Singleton {
> private Singleton _instance;
> 
> public Singleton getInstance() {
> if(_instance == null ) {
> _instance = getPrivateInstance();
> }
> 
>
> private synchronized Singleton getPrivateInstance() {
> return new Singleton();
> }
> }
> 
> Would you please shed some light on this for me? I've been following 
> the DCL problem for a couple of years now and find it hard to believe 
> that no one else thought of this solution.
> 
> David McReynolds

Web 2.0

Fashion Over Function

DCL Idiom Broken for Java

References

email exchange on a similar question