Editing Double-checked locking

{{Short description|Software design pattern}}
In [[software engineering]], '''double-checked locking''' (also known as "double-checked locking optimization"<ref>Schmidt, D et al. Pattern-Oriented Software Architecture Vol 2, 2000 pp353-363</ref>) is a [[software design pattern]] used to reduce the overhead of acquiring a [[Lock (computer science)|lock]] by testing the locking criterion (the "lock hint") before acquiring the lock.  Locking occurs only if the locking criterion check indicates that locking is required.

The original form of the pattern, appearing in ''Pattern Languages of Program Design 3'',<ref>{{cite book |title=Pattern languages of program design. 3 |date=1998 |publisher=Addison-Wesley |location=Reading, Mass |isbn=978-0201310115 |edition=Nachdr. |url=https://www.dre.vanderbilt.edu/~schmidt/PDF/DC-Locking.pdf}}</ref> has [[data race]]s, depending on the [[Memory model (programming)|memory model]] in use, and it is hard to get right. Some consider it to be an [[anti-pattern]].<ref>{{cite book |last1=Gregoire |first1=Marc |title=Professional C++ |date=24 February 2021 |publisher=John Wiley & Sons |isbn=978-1-119-69545-5 |url=https://books.google.com/books?id=MyEgEAAAQBAJ&pg=PA946 |language=en}}</ref> There are valid forms of the pattern, including the use of the {{java|volatile}} keyword in Java and explicit memory barriers in C++.<ref name="bdec">David Bacon et al. [http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html The "Double-Checked Locking is Broken" Declaration].</ref>

The pattern is typically used to reduce locking overhead when implementing "[[lazy initialization]]" in a multi-threaded environment, especially as part of the [[Singleton pattern]]. Lazy initialization avoids initializing a value until the first time it is accessed.

== Motivation and original pattern ==

Consider, for example, this code segment in the [[Java (programming language)|Java programming language]]:<ref name="bdec" />

<syntaxhighlight lang="java">
// Single-threaded version
class Foo {
    private static Helper helper;
    public Helper getHelper() {
        if (helper == null) {
            helper = new Helper();
        }
        return helper;
    }

    // other functions and members...
}
</syntaxhighlight>

The problem is that this does not work when using multiple threads. A [[lock (computer science)|lock]] must be obtained in case two threads call <code>getHelper()</code> simultaneously. Otherwise, either they may both try to create the object at the same time, or one may wind up getting a reference to an incompletely initialized object.

Synchronizing with a lock can fix this, as is shown in the following example:

<syntaxhighlight lang="java">
// Correct but possibly expensive multithreaded version
class Foo {
    private Helper helper;
    public synchronized Helper getHelper() {
        if (helper == null) {
            helper = new Helper();
        }
        return helper;
    }

    // other functions and members...
}
</syntaxhighlight>

This is correct and will most likely have sufficient performance. However, the first call to <code>getHelper()</code> will create the object and only the few threads trying to access it during that time need to be synchronized; after that all calls just get a reference to the member variable. Since synchronizing a method could in some extreme cases decrease performance by a factor of 100 or higher,<ref name=Boehm2005>{{cite journal|last=Boehm|first=Hans-J|title=Threads cannot be implemented as a library|journal=ACM SIGPLAN Notices|date=Jun 2005|volume=40|issue=6|pages=261–268|doi=10.1145/1064978.1065042|url=http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf|access-date=2014-08-12|archive-date=2017-05-30|archive-url=https://web.archive.org/web/20170530160703/http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf|url-status=dead}}</ref> the overhead of acquiring and releasing a lock every time this method is called seems unnecessary: once the initialization has been completed, acquiring and releasing the locks would appear unnecessary. Many programmers, including the authors of the double-checked locking design pattern, have attempted to optimize this situation in the following manner:

# Check that the variable is initialized (without obtaining the lock). If it is initialized, return it immediately.
# Obtain the lock.
# Double-check whether the variable has already been initialized: if another thread acquired the lock first, it may have already done the initialization. If so, return the initialized variable.
# Otherwise, initialize and return the variable.

<syntaxhighlight lang="java">
// Broken multithreaded version
// original "Double-Checked Locking" idiom
class Foo {
    private Helper helper;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }

    // other functions and members...
}
</syntaxhighlight>

Intuitively, this algorithm is an efficient solution to the problem. But if the pattern is not written carefully, it will have a [[data race]]. For example, consider the following sequence of events:

# Thread ''A'' notices that the value is not initialized, so it obtains the lock and begins to initialize the value.
# Due to the semantics of some programming languages, the code generated by the compiler is allowed to update the shared variable to point to a ''partially constructed'' object before ''A'' has finished performing the initialization. For example, in Java if a call to a constructor has been inlined then the shared variable may immediately be updated once the storage has been allocated but before the inlined constructor initializes the object.<ref name=IBM>{{cite web|last=Haggar|first=Peter|title=Double-checked locking and the Singleton pattern|url=http://www.ibm.com/developerworks/java/library/j-dcl/index.html|publisher=IBM|date=1 May 2002|archive-url=https://web.archive.org/web/20171027162134/https://www.ibm.com/developerworks/java/library/j-dcl/index.html |archive-date=2017-10-27|access-date=2022-05-19|url-status=dead}}</ref>
# Thread ''B'' notices that the shared variable has been initialized (or so it appears), and returns its value. Because thread ''B'' believes the value is already initialized, it does not acquire the lock. If ''B'' uses the object before all of the initialization done by ''A'' is seen by ''B'' (either because ''A'' has not finished initializing it or because some of the initialized values in the object have not yet percolated to the memory ''B'' uses ([[cache coherence]])), the program will likely crash.

Most runtimes have [[memory barrier]]s or other methods for managing memory visibility across execution units. Without a detailed understanding of the language's behavior in this area, the algorithm is difficult to implement correctly. One of the dangers of using double-checked locking is that even a naive implementation will appear to work most of the time: it is not easy to distinguish between a correct implementation of the technique and one that has subtle problems. Depending on the [[compiler]], the interleaving of threads by the [[Scheduling (computing)|scheduler]] and the nature of other [[concurrency (computer science)|concurrent system activity]], failures resulting from an incorrect implementation of double-checked locking may only occur intermittently. Reproducing the failures can be difficult.

== Usage in C++11 ==
For the singleton pattern, double-checked locking is not needed:

{{quote|If control enters the declaration concurrently while the variable is being initialized, the concurrent execution shall wait for completion of the initialization.|§&nbsp;6.7 [stmt.dcl] p4}}

<syntaxhighlight lang="cpp">
Singleton& GetInstance() {
  static Singleton s;
  return s;
}
</syntaxhighlight>

C++11 and beyond also provide a built-in double-checked locking pattern in the form of <code>std::once_flag</code> and <code>std::call_once</code>:
<syntaxhighlight lang="cpp">
#include <mutex>
#include <optional> // Since C++17

// Singleton.h
class Singleton {
 public:
  static Singleton* GetInstance();
 private:
  Singleton() = default;

  static std::optional<Singleton> s_instance;
  static std::once_flag s_flag;
};

// Singleton.cpp
std::optional<Singleton> Singleton::s_instance;
std::once_flag Singleton::s_flag{};

Singleton* Singleton::GetInstance() {
  std::call_once(Singleton::s_flag,
                 []() { s_instance.emplace(Singleton{}); });
  return &*s_instance;
}
</syntaxhighlight>

If one truly wishes to use the double-checked idiom instead of the trivially working example above (for instance because [[Visual Studio]] before the 2015 release did not implement the C++11 standard's language about concurrent initialization quoted above <ref>{{Cite web | url=https://msdn.microsoft.com/en-au/library/hh567368.aspx#concurrencytable | title=Support for C++11-14-17 Features (Modern C++)}}</ref> ), one needs to use acquire and release fences:<ref>[http://preshing.com/20130930/double-checked-locking-is-fixed-in-cpp11/ Double-Checked Locking is Fixed In C++11]</ref>

<syntaxhighlight lang="cpp">
#include <atomic>
#include <mutex>

class Singleton {
 public:
  static Singleton* GetInstance();

 private:
  Singleton() = default;

  static std::atomic<Singleton*> s_instance;
  static std::mutex s_mutex;
};

Singleton* Singleton::GetInstance() {
  Singleton* p = s_instance.load(std::memory_order_acquire);
  if (p == nullptr) { // 1st check
    std::lock_guard<std::mutex> lock(s_mutex);
    p = s_instance.load(std::memory_order_relaxed);
    if (p == nullptr) { // 2nd (double) check
      p = new Singleton();
      s_instance.store(p, std::memory_order_release);
    }
  }
  return p;
}
</syntaxhighlight>

== Usage in POSIX ==
<code>[https://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_once.html pthread_once()]
</code> must be used
to initialize library (or sub-module) code when its API does not have a dedicated initialization 
procedure required to be called in single-threaded mode.

== Usage in Go ==
<syntaxhighlight lang="go">
package main

import "sync"

var arrOnce sync.Once
var arr []int

// getArr retrieves arr, lazily initializing on first call. Double-checked
// locking is implemented with the sync.Once library function. The first
// goroutine to win the race to call Do() will initialize the array, while
// others will block until Do() has completed. After Do has run, only a
// single atomic comparison will be required to get the array.
func getArr() []int {
	arrOnce.Do(func() {
		arr = []int{0, 1, 2}
	})
	return arr
}

func main() {
	// thanks to double-checked locking, two goroutines attempting to getArr()
	// will not cause double-initialization
	go getArr()
	go getArr()
}
</syntaxhighlight>

== Usage in Java ==

As of [[Java Platform, Standard Edition|J2SE 5.0]], the [[Volatile variable|volatile]] keyword is defined to create a memory barrier. This allows a solution that ensures that multiple threads handle the singleton instance correctly. This new idiom is described in [http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html] and [http://www.oracle.com/technetwork/articles/javase/bloch-effective-08-qa-140880.html].

<syntaxhighlight lang="java">
// Works with acquire/release semantics for volatile in Java 1.5 and later
// Broken under Java 1.4 and earlier semantics for volatile
class Foo {
    private volatile Helper helper;
    public Helper getHelper() {
        Helper localRef = helper;
        if (localRef == null) {
            synchronized (this) {
                localRef = helper;
                if (localRef == null) {
                    helper = localRef = new Helper();
                }
            }
        }
        return localRef;
    }

    // other functions and members...
}
</syntaxhighlight>

Note the [[local variable]] "{{mono|localRef}}", which seems unnecessary. The effect of this is that in cases where {{mono|helper}} is already initialized (i.e., most of the time), the volatile field is only accessed once (due to "{{mono|return localRef;}}" instead of "{{mono|return helper;}}"), which can improve the method's overall performance by as much as 40 percent.<ref>{{cite book |last1=Bloch |first1=Joshua |title=Effective Java |date=2018 |publisher=Addison-Wesley |isbn=978-0-13-468599-1 |page=335 |edition=Third |quote=On my machine, the method above is about 1.4 times as fast as the obvious version without a local variable.}}</ref>

Java 9 introduced the {{Javadoc:SE|java/lang/invoke|VarHandle}} class, which allows use of relaxed atomics to access fields, giving somewhat faster reads on machines with weak memory models, at the cost of more difficult mechanics and loss of [[sequential consistency]] (field accesses no longer participate in the synchronization order, the global order of accesses to volatile fields).<ref>{{Cite web|url=https://docs.oracle.com/javase/specs/jls/se10/html/jls-17.html#jls-17.4.4|title=Chapter 17. Threads and Locks|website=docs.oracle.com|access-date=2018-07-28}}</ref>

<syntaxhighlight lang="java">
// Works with acquire/release semantics for VarHandles introduced in Java 9
class Foo {
    private volatile Helper helper;

    public Helper getHelper() {
        Helper localRef = getHelperAcquire();
        if (localRef == null) {
            synchronized (this) {
                localRef = getHelperAcquire();
                if (localRef == null) {
                    localRef = new Helper();
                    setHelperRelease(localRef);
                }
            }
        }
        return localRef;
    }

    private static final VarHandle HELPER;
    private Helper getHelperAcquire() {
        return (Helper) HELPER.getAcquire(this);
    }
    private void setHelperRelease(Helper value) {
        HELPER.setRelease(this, value);
    }

    static {
        try {
            MethodHandles.Lookup lookup = MethodHandles.lookup();
            HELPER = lookup.findVarHandle(Foo.class, "helper", Helper.class);
        } catch (ReflectiveOperationException e) {
            throw new ExceptionInInitializerError(e);
        }
    }

    // other functions and members...
}
</syntaxhighlight>

If the helper object is static (one per class loader), an alternative is the [[initialization-on-demand holder idiom]]<ref>Brian Goetz et al. Java Concurrency in Practice, 2006 pp348</ref> (See Listing 16.6<ref name=JCP>{{cite web|last1=Goetz|first1=Brian|title=Java Concurrency in Practice – listings on website|url=http://jcip.net.s3-website-us-east-1.amazonaws.com/listings.html|access-date=21 October 2014|display-authors=etal}}</ref> from the previously cited text.)
<syntaxhighlight lang="java">
// Correct lazy initialization in Java
class Foo {
    private static class HelperHolder {
       public static final Helper helper = new Helper();
    }

    public static Helper getHelper() {
        return HelperHolder.helper;
    }
}
</syntaxhighlight>

This relies on the fact that nested classes are not loaded until they are referenced.

Semantics of {{mono|final}} field in Java 5 can be employed to safely publish the helper object without using {{mono|volatile}}:<ref>[https://mailman.cs.umd.edu/mailman/private/javamemorymodel-discussion/2010-July/000422.html] Javamemorymodel-discussion mailing list{{Stale|text=Page not found – consider updating the link}}</ref>

<syntaxhighlight lang="java">
public class FinalWrapper<T> {
    public final T value;
    public FinalWrapper(T value) {
        this.value = value;
    }
}

public class Foo {
   private FinalWrapper<Helper> helperWrapper;

   public Helper getHelper() {
      FinalWrapper<Helper> tempWrapper = helperWrapper;

      if (tempWrapper == null) {
          synchronized (this) {
              if (helperWrapper == null) {
                  helperWrapper = new FinalWrapper<Helper>(new Helper());
              }
              tempWrapper = helperWrapper;
          }
      }
      return tempWrapper.value;
   }
}
</syntaxhighlight>

The local variable {{mono|tempWrapper}} is required for correctness: simply using {{mono|helperWrapper}} for both null checks and the return statement could fail due to read reordering allowed under the Java Memory Model.<ref>[http://jeremymanson.blogspot.ru/2008/12/benign-data-races-in-java.html] {{cite web |last1=Manson |first1=Jeremy |date=2008-12-14 |title=Date-Race-Ful Lazy Initialization for Performance – Java Concurrency (&c) |url=http://jeremymanson.blogspot.ru/2008/12/benign-data-races-in-java.html |access-date=3 December 2016}}</ref> Performance of this implementation is not necessarily better than the {{mono|volatile}} implementation.

== Usage in C# ==

In .NET Framework 4.0, the <code>Lazy&lt;T&gt;</code> class was introduced, which internally uses double-checked locking by default (ExecutionAndPublication mode) to store either the exception that was thrown during construction, or the result of the function that was passed to <code>Lazy&lt;T&gt;</code>:<ref>{{cite book
 |title=C# 4.0 in a Nutshell
 |last=Albahari
 |first=Joseph
 |isbn=978-0-596-80095-6
 |year=2010
 |publisher=O'Reilly Media
 |chapter=Threading in C#: Using Threads
 |chapter-url=http://www.albahari.com/threading/part3.aspx#_LazyT
 |quote=<code>Lazy&lt;T&gt;</code> actually implements […] double-checked locking. Double-checked locking performs an additional volatile read to avoid the cost of obtaining a lock if the object is already initialized.
}}</ref>

<syntaxhighlight lang="csharp">
public class MySingleton
{
    private static readonly Lazy<MySingleton> _mySingleton = new Lazy<MySingleton>(() => new MySingleton());

    private MySingleton() { }

    public static MySingleton Instance => _mySingleton.Value;
}
</syntaxhighlight>

== See also ==
* The [[Test and Test-and-set]] [[programming idiom|idiom]] for a low-level locking mechanism.
* [[Initialization-on-demand holder idiom]] for a thread-safe replacement in Java.

== References ==
<references />

== External links ==
* Issues with the double checked locking mechanism captured in [https://web.archive.org/web/20060620041255/http://purevirtuals.com/blog/2006/06/16/son-of-a-bug/ Jeu George's Blogs]
* [[c2:DoubleCheckedLocking|"Double Checked Locking" Description from the Portland Pattern Repository]]
* [[c2:DoubleCheckedLockingIsBroken|"Double Checked Locking is Broken" Description from the Portland Pattern Repository]]
* Paper "[http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf C++ and the Perils of Double-Checked Locking]" (475&nbsp;KB) by [[Scott Meyers]] and [[Andrei Alexandrescu]]
* Article "[https://www.infoworld.com/article/2074979/double-checked-locking--clever--but-broken.html Double-checked locking: Clever, but broken]" by [[Brian Goetz]]
* Article "[https://www.infoworld.com/article/2074990/warning--threading-in-a-multiprocessor-world.html Warning! Threading in a multiprocessor world]" by [[Allen Holub]]
* [http://www.ibm.com/developerworks/java/library/j-dcl/index.html Double-checked locking and the Singleton pattern]
* [https://web.archive.org/web/20060412081055/http://www.oaklib.org/docs/oak/singleton.html Singleton Pattern and Thread Safety]
* [http://msdn2.microsoft.com/en-us/library/12a04hfd.aspx volatile keyword in VC++ 2005]
* [https://web.archive.org/web/20120902131951/https://blogs.oracle.com/cwebster/entry/double_check_locking Java Examples and timing of double check locking solutions]
* {{cite news |url=http://www.oracle.com/technetwork/articles/javase/bloch-effective-08-qa-140880.html |title=More Effective Java With Google's Joshua Bloch}}

{{Design Patterns patterns}}

[[Category:Concurrency control]]
[[Category:Software design patterns]]
[[Category:Articles with example Java code]]