Channels ▼

Bil Lewis

Dr. Dobb's Bloggers

Double Checked Disaster

December 30, 2008

When I first developed what later became know as  "Double Checked Locking," it was just a cute idea to save a little CPU in very restricted circumstances....

Much to my amusement (and consternation) Double Checked Locking has risen its
head again and occupies the minds of many a programmer, throwing them into fits
of confusion.

The short version of the story is "It doesn't work. Don't do that."

The longer version is, well, longer.

Back in the early 90's, I started working with Sun's threading group, and was
directed to write the first book on multithreading, "The Threads Primer". As a
minor aside, I described what later became known as "Double Checked
Locking". The basic idea was very simple. Why take the expense of locking a
lock, just to check if something has been initialized?

My example looked something like this (my code was in C):

Thing getThingDCL() {
  if (initialized) return thing;
  synchronized (this) {
    thing = new Thing();
    initialized = true;
  }
  return thing;
}


It worked just fine and ran much faster (~20x) than the fully locked version:

Thing synchronized getThingLocked() {
  if (initialized) return thing;
  thing = new Thing();
  initialized = true;
  return thing;
}


It went out, people used it, and everyone was happy.

Then Digital release their Alpha processor. It was super fast, super hot, and
used a different memory model than Sun's SPARC chip did. It used a weak memory
model, while SPARC used a "strong" memory model.  The difference is that on a
SPARC chip, a memory write by one CPU to main memory will be seen by the cache
snoopers on all the other CPUs, while on an Alpha chip, the other CPUs must
issue a kind of a "memory barrier" instruction to ensure the caches are coherent.

This means that a write to a variable (say "thing") will not necessarily be seen
without that barrier instruction.  Which means my clever little hack won't work.

A bunch of us all realized this problem at the same time. (I remember talking to
Doug Schmidt, Bill Pugh, Doug Lea, and a few other folks.) A disclaimer was
written "Double Checked Locking is Broken," explaining this.  There was big
meeting on memory models at Sun a bit later, when these issues were discussed,
and a number of significant changes were made to Java to deal with relates stuff,
including redefining what "volatile" meant.

It used to mean "Dear Compiler, this is a variable that I know something special
about, which you don't. Do not cache it, but force all reads and writes to go to
main memory all the time." This made it possible to do memory-mapped I/O.

The new meaning of volatile is more like "...and make sure all memory
reads/writes are seen across all CPUs."  This means that a volatile variable
must issue memory barrier instructions.

With this new version of volatile, it is possible to write something DCL-like
(we'll call it VDCL) that does work and there's been a lot of discussion about
this recently. Here's one of many examples you can find on the net:

// Works with acquire/release semantics for volatile
// Broken under Java 1.4 and earlier 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;
    }
 
    // other functions and members...
}


This is a bit slower than DCL is, but still faster than full locking. Which is
kind of cool.

What has been constantly overlooked is the rest of my discussion on the utility
of DCL.

The rest of the discussion runs something like this:

"But the time savings is only interesting if you have a situation where the cost
of initialization is very high, it often is never used, and when it is used,
it's used extensively with little other intervening work."

The point is that 99.99% of the time, it's best to initialize at load-time. In a
small percentage of cases (where it is often never used), a normal locking
(getThingLocked) is reasonable, and almost never is DCL actually useful.
Indeed, outside of a few extreme (and artificial) examples, DCL is useless.
Because saving 30ns in a task that takes 30ms to run is not interesting.

Oh, yes. Timing. That what this is all about, right?

On my 3Ghz iMac, the VDCL outperformed the fully locked version by a vast 9x and
load-time initialization ourperformed VDCL by 10% on a single-threaded
test. Presumably VDCL will run slower when there's more shared data changing.

VDCL: 3.2ns
Lock: 29ns
Load: 2.9ns

So if you spend more than 1us doing real work, you'll see no benefit.

The logical conclusion here is:



Don't Do That!




====

And if you are dead-set on doing it anyway ('cause you're probably a little like
me), then do it correctly: Write your program using load-time initialization,
write it using full locking, and write it with VDCL. Then time the program using
each of them in turn. If the VDCL version is not at least 10% faster, dump it!

Always keep in mind your real objective: Write a cool program that does useful
things.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video