Trouble Checked Locking

HWM

I recently discovered that there has been a significant discussion going on in the blogosphere about so called 'double checked locking'. Suffice to say I see no need for this and I find it very distasteful as a coding practice, one that can lead to developers adopting poor design ideas.

I post here the 'standard' singleton example, followed by what I think is a better solution:

Code Snippet

public sealed class MyClass
{
private static object _synchBlock = new object();
private static volatile MyClass _singletonInstance;

//Makes sure only this class can create an instance.
private MyClass() { }

//Singleton property.
public static MyClass Singleton
{
get
{
if (_singletonInstance == null)
{
lock (_synchBlock)
{
// Need to check again, in case another cheeky thread
// slipped in there while we were acquiring the lock.
if (_singletonInstance == null)
{
_singletonInstance = new MyClass();

}
}
}

return (_singletonInstance);
}
}
}

public sealed class MyBetterClass
{
private static Int32 controller;
private const Int32 UNCREATED = 0;
private const Int32 CREATED = 1;

private static volatile MyBetterClass _singletonInstance;

//Makes sure only this class can create an instance.
private MyBetterClass() { }

//Singleton property.
public static MyBetterClass Singleton
{
get
{ // The comparison and conditional exchange of values, is ALWAYS uninterruptible
if (Interlocked.CompareExchange(ref controller, CREATED, UNCREATED) == UNCREATED)
_singletonInstance = new MyBetterClass();

return (_singletonInstance);
}
}
}

bear in mind that to all intents and purposes, the interlocked operation is very fast, it is pretty much an uninterruptible 'if then assign' that relies on (reliable) hardware to ensure (even in SMP systems) that the if will branhc true once and only once, ever. Please post here if you spot an oversight.

Hugh

Peter Ritchie

How does your method stop another thread from creating another singleton between the call to CompareExchange and _singletonInstance = new MyBetterClass()

HWM

Hi, well if my undersatnding is correct, the only way a thread can execute the 'new' statement, is if the CompareExchange expression in the 'if' statement returns 'true'.

If it does return 'true' then it will, atomically, have had to update the 'control' integer to CREATED, no other thread even one running on a different CPU at the very same instant in time, will ever be able to get the same result (i.e. 'true) here because the compare and update occur in an uninterrupted manner, any thread that contended (by executing the same locked compare instruction at the very same instant) would either get control first or wait (at the hardware level) for an instant while the locked (hardware) bus was in use.

Of course I'm assuming this operation is the same (relies upon ) the existing kernel interlock functions, these are also used by device drivers for similar purposes it seems.

My overall opinion is that there appears to be nothing going on in the managed world that requires any new synchronization approaches to those that have served well in the unmanaged world.

Hugh

Oops, i just noticed a different little prob, another thread could see 'false' in the compare, but BEFORE the first thread has actually excuted the new, so could return a null. this is something that needs to be dealt with.

Peter Ritchie

Stolen from Jon Skeet:

Code Snippet public sealed class Singleton { Singleton() { } public static Singleton Instance { get { return Nested.instance; } } class Nested { // Explicit static constructor to tell C# compiler // not to mark type as beforefieldinit static Nested() { } internal static readonly Singleton instance = new Singleton(); } }

.NET constructors are already synchronized, a constructor for a class cannot be running in two or more threads, and a static constructor is only called once. You'd have to incur the locking penalty for the constructor anyway, this way you utilize it to it's full potential without incurring the overhead of another lock, or Interlocked...

The nested class is there to make the creation of the singleton lazy, so it doesn't have to be created at startup.

Thomas Danecker

You're code is not thread-safe:

If the first thread is interrupted between the CompareExchange and the creation of the new instance, CONTROLLER is set to CREATED but the instance was not created (because the thread was interrupted by the sheduler). Now a second thread enters the method and thinks that the instance was created but it returns a null-Reference what it should never do.

The second fact is, that your version is not as performant as the double checked locking pattern because a CompareExchange need quite more processor-ticks than a simple if statement. The lock in the double checked locking pattern is only done at the beginning (as long as the instance is not created) and it may have a performance-penalty there but in the normal case, the instance is already created and only one "if" has to be executed, so the overage performance is better than the one of your code.

EDIT:

Further performance penalties are the worse optimizable code because of the volatile declaration and the memory-overhead of the CONTROLLED value.

Thomas Danecker

The runtime does AFAIK a lock on typeof(Nested) to ensure the initialization of the type so the double checked locking pattern should be at least as fast as this solution, but no nested class is required. It would be nice to test the two approachs.

HWM

One way to eliminate that window is as follows:

Code Snippet

public sealed class MyBetterClass
{
private static Int32 controller;
private const Int32 UNCREATED = 0;
private const Int32 CREATED = 1;

private static volatile MyBetterClass _singletonInstance;

//Makes sure only this class can create an instance.
private MyBetterClass() { }

//Singleton property.
public static MyBetterClass Singleton
{
get
{ // The comparison and conditional exchange of values, is ALWAYS uninterruptible

if (Interlocked.CompareExchange(ref controller, CREATED, UNCREATED) == UNCREATED)
_singletonInstance = new MyBetterClass();

else

// ensure that the creator thread if it isnt us, completes the creation.

// this loop will execute very very rarely if ever, and will loop very few times

// if it does.

while (_singletonInstance == null)

;

return (_singletonInstance);
}
}
}

I can't comment upon performance, I understand that the interlock operations are very fast, and other synchronization mechanims (more complex ones) are inevitably a little slower, but I cannot swear to it.

Out of interest, do MS advocate anywhere this double check pattern for device driver designs

Rgds

Peter Ritchie

The Nested class is there for lazy creation. Yes, synchronization of constructors is effectively equivalent to lock(typeof(Nested)).

See the evolution of Jon's Singleton class here: http://www.yoda.arachsys.com/csharp/singleton.html

Thomas Danecker

Code Snippet

public sealed class Singleton

{

private static readonly Singleton instance = new Singleton();

// Explicit static constructor to tell C# compiler

// not to mark type as beforefieldinit

static Singleton()

{

}

Singleton()

{

}

public static Singleton Instance

{

get

{

return instance;

}

}

}

This should also work nearly the same way as your code because the instance is created the first time you access the Singleton (which would be a call to Singleton.Instance). Sure, if the Singleton has other static members which are accessed prior to Singleton.Instance, it would be initialized too soon but I think this isn't the case most of the time.

EDIT:

sorry, i read your post too late. It already covers my scenario in the referenced link.

Thomas Danecker

The loop will be executed at least till the sheduler interrupts the thread and gives controll to the other thread.

This should be quite more performant:

Code Snippet

while (_singletonInstance == null)

Thread.Sleep(0);

Peter Ritchie

Except that Thread.Sleep(0) will only relinquish to the a thread of equal priority that is ready to run. You're never allowing lower-priority threads a chance to run. Thread.Sleep(1) is better, See Joe Duffy's blog on the topic.

Thomas Danecker

The most performant version would be the following (and I also corrected Thread.Sleep(0) to Thread.Sleep(1), thanks Peter Ritchie):

Code Snippet

public static Singleton Instance
{
get
{
if (instance == null)
{
if (Interlocked.CompareExchange(ref created, 1, 0) == 0)
{
instance = new Singleton();
}
else
{
while (instance == null)
Thread.Sleep(1);
}
}
return instance;
}
}

But as stated in the referenced link of Peter Ritchie: It doesn't matter.

In my oppinion, the default case (instance is already initialized) is the more performance-critical part, so I prefer the sinple double checked locking pattern over the interlocked compare exchange (and also over my current example which should only show up the most performant version. I would never use it).

Thomas Danecker

Yet another performance consideration:

If the creation of the Singleton is expensive (because there's many to do in the constructor of the Singleton), a lock may be more performant and so we're back at the double checked locking pattern as the most performant implementation of a multithreaded singleton.

HWM

Yes, adding that up-front 'if' is better, good move.

I have seen such 'double checking' in code on mini's written by a programmer in haste, I think it can lead to a pattern of thinking, that gets applied in scenarios without due consideration, resulting in production code that has subtle nasties. I think I am drawn to the interlock operations as they focus very sharply on the vital uninterruptible step, that is precisley defined and upon which the other logic hinges.

As always these synchronization subjects are often very intriguing, I tend to give preference to overall 'digestibility' (which of course is also a matter of personal taste) rather than performance, in my experience it is often too easy to make subjective assumptions about performance and make something simple look a little more complex, I've done this myself and regrettted it numerous times!

having said that (!) I have to ask, why bother with Sleep at all I mean as soon as you do that, you are trapping into the (unmanaged) kernel (a mode switch) adding the thread to a wait list, causing the scheduler to get involved and no doubt locking quite a few kernel structures in the process.

I think that Sleep would be valid if the total CPU hit was less than the CPU hit incurred by the while loop, and tthat may or may not be true, I suspect it isnt true though.

A big weakness though is hwo this breaks if for some reason the 'new' should return null, rare I know, but a possibility

Thomas Danecker

HWM wrote:

having said that (!) I have to ask, why bother with Sleep at all I mean as soon as you do that, you are trapping into the (unmanaged) kernel (a mode switch) adding the thread to a wait list, causing the scheduler to get involved and no doubt locking quite a few kernel structures in the process. I think that Sleep would be valid if the total CPU hit was less than the CPU hit incurred by the while loop, and tthat may or may not be true, I suspect it isnt true though.

If you use a spin wait (your while loop), you're doing nothing till the sheduler interrupts you're thread. The sheduler run's also in kernel mode, so a context switch is always required. If you use Thread.Sleep(1), the context switch is done earlier. The only benefit you have is on a multi-processor machine where both threads execute the method simultanously. There, the loop is finished without a context switch. Best performance on a multi processor machine would be to mix spin wait and Thread.Sleep.

HWM wrote:

A big weakness though is hwo this breaks if for some reason the 'new' should return null, rare I know, but a possibility

It's less rare as if you only do the following:

Code Snippet

if(instance == null)

instance = new Singleton();

Fact is: It is NOT thread safe. It doesn't matter how rare it is. The application may crash because of this bug and it's easy to fix.