Name for this pattern? (Answer: lazy initialization with double-checked locking)

Question

Consider the following code:

public class Foo
{
    private static object _lock = new object();

    public void NameDoesNotMatter()
    {
        if( SomeDataDoesNotExist() )
        {
            lock(_lock)
            {
                if( SomeDataDoesNotExist() )
                {
                    CreateSomeData();
                }
                else
                {
                    // someone else also noticed the lack of data.  We
                    // both contended for the lock.  The other guy won
                    // and created the data, so we no longer need to.
                    // But once he got out of the lock, we got in.
                    // There's nothing left to do.
                }
            }
        }
    }

    private bool SomeDataDoesNotExist()
    {
        // Note - this method must be thread-safe.
        throw new NotImplementedException();
    }

    private bool CreateSomeData()
    {
        // Note - This shouldn't need to be thread-safe
        throw new NotImplementedException();
    }
}

First, there are some assumptions I need to state:

There is a good reason I couldn't just do this once an app startup. Maybe the data wasn't available yet, etc.
Foo may be instantiated and used concurrently from two or more threads. I want one of them to end up creating some data (but not both of them) then I'll allow both to access that same data (ignore thread safety of accessing the data)
The cost to SomeDataDoesNotExist() is not huge.

Now, this doesn't necessarily have to be confined to some data creation situation, but this was an example I could think of.

The part that I'm especially interested in identifying as a pattern is the check -> lock -> check. I've had to explain this pattern to developers on a few occasions who didn't get the algorithm at first glance but could then appreciate it.

Anyway, other people must do similarly. Is this a standardized pattern? What's it called?

Looks like an odd way to utilize a synchronized, [lazy-loaded](http://en.wikipedia.org/wiki/Lazy_loading), [singleton pattern](http://en.wikipedia.org/wiki/Singleton_pattern) to me. — Jeff Mercado, May 15 '11 at 20:39
You're implying there might be a better, but functionally equivalent, way to do this. What are you thinking specifically? — Matthew Lund, May 15 '11 at 20:42
I'm saying odd since it is combining a number of patterns into one method. Normally I'd expect to see them in separate methods. i.e., the lazy-loaded singleton (the data) would be in a separate method/property. — Jeff Mercado, May 15 '11 at 20:45
There is a problem in point 2. You need some sort of "thread safety" when accessing the data. Without it, you can't be sure the data was fully created before you access it. — Ishtar, May 15 '11 at 21:24
I agree, Ishtar. I just wanted to separate that concern, conceptually. But you're definitely right, detecting the scenario where the data seems to exist but is not complete would be important. — Matthew Lund, May 15 '11 at 21:28

score 14 · Answer 1 · edited May 23 '17 at 11:47

14

Though I can see how you might think this looks like double-checked locking, what it actually looks like is dangerously broken and incorrect double-checked locking. Without an actual implementation of SomeDataDoesNotExist and CreateSomeData to critique we have no guarantee whatsoever that this thing is actually threadsafe on every processor.

For an example of an analysis of how double-checked locking can go wrong, check out this broken and incorrect version of double-checked locking:

C# manual lock/unlock

My advice: don't use any low-lock technique without a compelling reason and a code review from an expert on the memory model; you'll probably get it wrong. Most people do.

In particular, don't use double-checked locking unless you can describe exactly what memory access reorderings the processors can do on your behalf and provide a convincing argument that your solution is correct given any possible memory access reordering. The moment you step away even slightly from a known-to-be-correct implementation, you need to start the analysis over from scratch. You can't assume that just because one implementation of double-checked locking is correct, that they all are; almost none of them are correct.

edited May 23 '17 at 11:47

Community

1
1

answered May 15 '11 at 22:24

Eric Lippert

647,829
179
1,238
2,067

That's a very good point, Eric. In my real-life code that inspired this, SomeDataDoesNotExist() is entirely thread-safe (I'll avoid mentioning why as that might take us on a tangent). If it were not, that would be a big problem. That link is helpful. I believe I'm safe but I'm going to re-read that link a few times to make sure. – Matthew Lund May 15 '11 at 23:19
I just modified my original post by adding comments in the final two methods. – Matthew Lund May 15 '11 at 23:24
I'm also going to consider the possibility that what I'm doing with lower-level locks could be done more simply using some higher-level constructs. – Matthew Lund May 15 '11 at 23:26
3

@Matthew: It doesn't matter whether SomeDataDoesNotExist is threadsafe; I mean, yes, it has to be threadsafe, but it needs to be more than that. The *whole pattern* needs to be threadsafe **in a world where reads of different addresses may be arbitrarily reordered as observed from multiple processors**. That is a far deeper and more complex requirement than mere thread safety! – Eric Lippert May 16 '11 at 03:17
@Eric Lippert - so what would be your suggestion to fixing this problem? ie. if we shouldn't be using Double-checked locking, what would you suggest? – Pure.Krome Aug 24 '11 at 01:00
2

@Pure.Krome: Perfectly ordinary locking. *Low lock techniques are dangerous.* Avoid them. Take the lock; it is probably fast enough. – Eric Lippert Aug 24 '11 at 04:28

score 9 · Accepted Answer · answered May 15 '11 at 20:37

9

Lazy initialization with double-checked locking?

answered May 15 '11 at 20:37

Ben Voigt

277,958
43
419
720

2

Precisely. And, by the way, .NET 4 provides a really nice `Lazy` class to take care of the implementation details of Lazy initialization. See http://stackoverflow.com/questions/5986466/why-use-system-runtime-caching-or-system-web-caching-vs-static-variables/5986819#5986819 for an example. – StriplingWarrior May 15 '11 at 20:43
I'm going to look into this Lazy class. I'm curious if it's thread-safe in terms of taking care of the locking. – Matthew Lund May 15 '11 at 20:51
Here's a wiki article on the term Ben Voigt used for the locking: http://en.wikipedia.org/wiki/Double-checked_locking – Matthew Lund May 15 '11 at 21:14

score 4 · Answer 3 · answered May 15 '11 at 20:43

4

The part that I'm especially interested in identifying as a pattern is the check -> lock -> check.

That is called double-checked locking.

Beware that in older Java versions (before Java 5) it is not safe because of how Java's memory model was defined. In Java 5 and newer changes were made to the specification of Java's memory model so that it is now safe.

answered May 15 '11 at 20:43

Jesper

202,709
46
318
350

There we go, that's _exactly_ what I was after. I just didn't have a lexicon for it. I'm trying to accept this answer but I'm new, give me a sec. – Matthew Lund May 15 '11 at 20:49
I'll vote up your answer down the road when the site actually allows me to vote up people. Thanks for your time. – Matthew Lund May 15 '11 at 21:15

score 0 · Answer 4 · answered May 15 '11 at 20:43

0

The only name that comes to mind for this kind of is "Faulting". This name is used in iOS Core-Data framework to similar effect.

Basically, your method NameDoesNotMatter is a fault, and whenever someone invokes it, it results in the object to get populated or initialized.

See http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/CoreData/Articles/cdFaultingUniquing.html for more details on how this design pattern is used.

answered May 15 '11 at 20:43

sinha

588
2
5

Interesting. Is this faulting inherently thread-safe in objective-C? Or could we say that mine is a thread-safe fault? – Matthew Lund May 15 '11 at 20:44
The faulting and creation of new objects as a result of firing of the faults is thread safe AFAIK, but only within a "context". – sinha May 15 '11 at 20:51

Name for this pattern? (Answer: lazy initialization with double-checked locking)

4 Answers4

Linked