Skip to content

Double-Checked Locking in C#

Heute hatte ich eher zufällig das Buch Head First Design Patterns in der Hand. Auch eher zufällig bin ich dabei im Kapitel über das Singleton-Pattern beim Double-Checked Locking hängen geblieben. Dort wird darauf aufmerksam gemacht, dass dieses Pattern unter Java 1.4 und früheren Versionen nicht funktioniert.
Da ich dieses Pattern bereits einige male in C# verwendet habe, wurde ich doch etwas neugierig und habe ein bischen nach den Gründen dafür gesucht. Dabei bin ich auf den Artikel The "Double-Checked Locking is Broken" Declaration aufmerksam geworden. In diesem werden alle Probleme mit diesem Pattern detailiert erläutert.

Mein C#-Code für dieses Pattern sah bis jetzt immer folgendermaßen aus (stark abstrahiert):

PLAIN TEXT
C#:
  1. public sealed class Singleton
  2. {
  3.     private static Singleton instance = null;
  4.     private static object syncRoot = new object();
  5.     public string value;
  6.  
  7.     private Singleton()
  8.     {
  9.         value = "test123";
  10.     }
  11.  
  12.     public static Singleton Instance
  13.     {
  14.         get
  15.         {
  16.             if (null == instance) // first check
  17.             {
  18.                 lock (syncRoot)
  19.                 {
  20.                     if (null == instance) // second (double) check
  21.                         instance = new Singleton();
  22.                 }
  23.             }
  24.             return instance;
  25.         }
  26.     }
  27. }

Stellt sich die Frage, ob mit diesem Code in C# bzw. unter .Net auch Probleme bestehen.

Die Antwort ist leider ja. Welche genau wird in The DOTNET Memory Model beschrieben (unbedingt den ganzen Thread lesen) und auch eine Lösung für das Problem gegeben:

PLAIN TEXT
C#:
  1. public sealed class Singleton
  2. {
  3.     private static volatile Singleton instance = null; // important: this is volatile now
  4.     private static object syncRoot = new object();
  5.     public string value;
  6.  
  7.     private Singleton()
  8.     {
  9.         value = "test123";
  10.     }
  11.  
  12.     public static Singleton Instance
  13.     {
  14.         get
  15.         {
  16.             if (null == instance) // first check
  17.             {
  18.                 lock (syncRoot)
  19.                 {
  20.                     if (null == instance) // second (double) check
  21.                         instance = new Singleton();
  22.                 }
  23.             }
  24.             return instance;
  25.         }
  26.     }
  27. }

Das funktioniert, da das Speichermodell von .Net einen Schutz (memory barrier; hat jemand eine gute Übersetzung dafür?) für diese flüchtigen Lese-/Schreibzugriffe (volatile read/write) hat (s. 17.4.3 Volatile fields in ECMA-334 C# Language Specification). Dieses ist in Java nicht der Fall. Daher funktionieren die ganzen Verbesserungsvorschläge für die Java-Implementierungen aus meiner Sicht auch nicht.

Es gibt auch noch eine zweite (etwas effizientere) Variante, die auch aus The DOTNET Memory Model stammt:

PLAIN TEXT
C#:
  1. public sealed class Singleton
  2. {
  3.     private static Singleton instance = null;
  4.     private static object syncRoot = new object();
  5.     public string value;
  6.  
  7.     private Singleton()
  8.     {
  9.         value = "test123";
  10.     }
  11.  
  12.     public static Singleton Instance
  13.     {
  14.         get
  15.         {
  16.             if (null == instance) // first check
  17.             {
  18.                 lock (syncRoot)
  19.                 {
  20.                     if (null == instance) // second (double) check
  21.                     {
  22.                         Singleton singleton = new Singleton();
  23.                         System.Threading.Thread.MemoryBarrier(); // comment for next version of .Net
  24.                         // System.Threading.Thread.WriteMemoryBarrier(); // uncomment for next version of .Net
  25.                         instance = singleton;
  26.                     }
  27.                 }
  28.             }
  29.             return instance;
  30.         }
  31.     }
  32. }

Wieder mal was dazu gelernt ...

Hier noch ein paar weitere interessante Links zum Thema:

13 Comments

Categories: Programming.

Tags: , , ,

By stj
— January 10, 2008 at 2:08 am
Comment Feed

13 Responses

  1. This is a problem that has been debated for years. The C++ guys have had problems with singleton initialization since the first version of the specification :-) .

    However, there is an interesting alternative solution, which may well be more efficient:

    using System.Threading;
    public class Singleton {
      const int NotInitialized = 0;
      const int Initializing = 1;
      const int Initialized = 2;
      static int state;
      static Singleton instance;

      Singleton Instance {
        get {
          while (true) {
            switch (Interlocked.CompareExchange(ref state, Initializing, NotInitialized) {
            case NotInitialized: instance = new Singleton(); state = Initialized; return instance;
            case Initializing: Thread.Sleep(0); break;
            case Initialized: return (Singleton)Interlocked.CompareExchange(ref singleton, null, null);
            }
          }
        }
      }
    }

    This is obviously a lot more light-weight. The spinning during the Initializing state could be replaced with an event, but I'm not sure the cost of the event is justified.

    In C++ I'd have to explicitly initialize state to zero, but it's not necessary in C#.

    See also http://www.sandpile.org/post/msgs/20003674.htm

    David Turner — February 21, 2008 @ 8:06 am —

  2. PS C# makes all the necessary guarantees about "static Singleton instance = new Singleton();", so technically none of this is necessary ;-)

    David Turner — February 21, 2008 @ 9:19 am —

  3. "static Singleton instance = new Singleton();" would also work in Java, but then you get an eagerly created instance instead of alazily created one.

    stj — February 21, 2008 @ 6:36 pm —

  4. I don't see why your solution is more efficient than one of the other solutions. Can you explain that in more detail?

    btw: I think your solution might be broken.

    Let's assume we've got two threads, T1 and T2.
    T1 first enters the Instance-Property and executes the first "Interlocked.CompareExchange" statement. The result will be "NotInitialized" and state will be set to "Initializing".
    Now T2 enters the Insance-Property and executes the first "Interlocked.CompareExchange" statement. The result will be "Initializing".
    T1 can now execute the statements at the "case NotInitialized:"-block. Because of compiler optimizations it might be possible that the "state = Initialized"-statement gets executed before "instance = new Singleton();".
    In this case T2 executes the "case Initialized"-block and might return a null reference.

    possible execution order:
    T1: Interlocked.CompareExchange(ref state, Initializing, NotInitialized) //with return value "NotInitialized"
    T2: Interlocked.CompareExchange(ref state, Initializing, NotInitialized) //with return value "Initializing"
    T1: state = Initialized
    T2: Thread.Sleep(0);
    T2: Interlocked.CompareExchange(ref state, Initializing, NotInitialized) //with return value "Initialized"
    T2: return (Singleton)Interlocked.CompareExchange(ref singleton, null, null); // return value is null, cause singleton (did you mean instance?) has not been initialized yet
    T1: instance = new Singleton();
    T1: return instance;

    Correct me if I'm wrong.

    stj — February 21, 2008 @ 10:16 pm —

  5. stj: You make an excellent point. As you may have noticed from the syntax errors, I wrote it in a hurry and without referring back to my original implementation. I'm not 100% sure that the scenario you described is possible, as a constructor call counts as a method invocation, and the subsequent write to "state" cannot therefore be re-ordered. But supposing it could, one can always replace the assignments to "singleton" and to "state" with yet more interlocked operations.

    On the point of static initialization, C# does it lazily.

    Now, from an efficiency point of view, an interlocked operation is orders of magnitude faster than using any sort of synchronization primitive. I'm speaking about the Intel architecture here, because for all practical purposes that's what a C# application will be running on. Interlocked.CompareExchange reduces to a "LOCK CMPXCHG" instruction. This asserts the LOCK# signal on the bus, which does prevent other processors from accessing it (but only for a single cycle). On the other hand, the lock(..,) statement results in, inter alia: a transition to kernel mode, an interlocked operation, a thread queue update, another interlocked operation, and a return to user mode. Twice over. So InterlockedExchange wins hands-down.

    David Turner — February 22, 2008 @ 10:49 am —

  6. A couple of other points:

    1. Static members aren't subject to write-reordering in the CLR. However there is the possibility of the processor reordering the writes; so to be safe, I'd change both of the assignments in the first case statement into interlocked operations.

    2. I don't use the pattern I described for singletons (since static object instance = new object() works fine), but I do use it for kicking off costly initializations. For example, in a service that needs to run a big sanity-check query on the database before it can start responding to requests, I use this pattern as part of the invocation guard on each operation; if the sanity check isn't finished, the operation faults with "server not ready'. If it's the first invocation, it kicks off the query in a worker thread. Otherwise it continues with the operation,

    By the way, have a look at: http://thith.blogspot.com/2005/11/c-interlocked.html

    David Turner — February 22, 2008 @ 11:19 am —

  7. I can follow your line of argument concerning the efficiency. But I just wrote a very short program which spwans two threads executing the following code:

    Singleton s = null;
    DateTime start = DateTime.Now;
    for (int i = 1; i < 1000000000; ++i)
    s = Singleton.Instance;
    DateTime end = DateTime.Now;
    Console.WriteLine((end - start));

    I did this for all three implementations and the outcome was as follows:

    volatile/lock implementation:
    00:00:12.7187500
    00:00:19.2343750

    MemoryBarrier implementation:
    00:00:12.5468750
    00:00:19.2031250

    Interlocked implementation:
    00:03:14.2968750
    00:04:46.3593750

    Of course, that's a very simple-minded test but refering to it I would not call it very efficient. Do you have any clue why it's so slow?

    stj — February 22, 2008 @ 12:10 pm —

  8. Interesting!

    After seeing your results I had to do a test of my own, and I got the following:

    DEBUG:
    -- Locking:
    8,547,333.84 accesses per second
    8,623,477.58 accesses per second
    8,772,500.09 accesses per second
    10,185,575.55 accesses per second
    -- Memory barrier:
    8,791,792.79 accesses per second
    8,690,548.59 accesses per second
    8,753,742.40 accesses per second
    10,167,778.44 accesses per second
    -- Interlocked:
    7,540,435.62 accesses per second
    7,270,033.11 accesses per second
    7,236,951.95 accesses per second
    8,118,681.73 accesses per second

    RELEASE:
    -- Locking:
    23,161,192.68 accesses per second
    23,170,207.27 accesses per second
    23,690,394.64 accesses per second
    27,578,381.80 accesses per second
    -- Memory barrier:
    24,664,776.48 accesses per second
    24,410,319.12 accesses per second
    23,941,740.15 accesses per second
    30,162,966.80 accesses per second
    -- Interlocked:
    17,773,908.60 accesses per second
    17,506,720.20 accesses per second
    17,867,324.74 accesses per second
    20,818,168.77 accesses per second

    Definitely not the result I expected!!

    Having a look at the disassembly, it seems that the interlocked operation on the state is not treated as an intrinsic, which is quite disappointing.

    I'd like to hear what the CLR guys have to say about this.

    David Turner — February 22, 2008 @ 1:00 pm —

  9. Aha... apart from the non-inlining issue, it also helps to first check for null as the other techniques do ;-)

    Adding "if (instance != null) return instance;" just before the while loop improves performance dramatically.

    David Turner — February 22, 2008 @ 1:15 pm —

  10. That's why it's called "Double-Checked", isn't it? ;-)

    I could have come across this myself.

    stj — February 22, 2008 @ 2:13 pm —

  11. Concerning David Turner's sample, can someone elaborate on why we must do that Interlocked statement in the last case line?

    case Initialized: return (Singleton)Interlocked.CompareExchange(ref instance, null, null);

    Set the instance back to null if it is null? What for? Why set it back? When would that happen? Shouldn't the instance be always safely initialized at that point already anyway? Or am I getting something wrong here?

    Can't we do just simply:

    case Initialized: return instance;

    That looks pretty atomic to me.

    Michael — July 7, 2008 @ 1:37 am —

  12. I have same question as Michael. Why exactly do we need CompareExchange at that point?

    Vlad — May 15, 2010 @ 8:21 pm —

  13. lock() erzeugt einen Full-Fence, also auf beiden Seiten. Somit ist die "Double-Checked Locking in C#" kein Problem. Auch der gesamte Interlocked Bereich erzeugt MemoryBarriers und müssen nicht extra aufgerufen werden. Und weil C# einen static Constructor sowieso Lazy aber garantiert nur ein einziges mal bei gleichzeitigen anhalten paralleler Zugriffe regelt ist es besser für das Singleton eine eigene Klasse zu machen. Wenn man mit volatile und Thread.MemoryBarrier rumspielt kann natürlich auch Müll bei rauskommen. Einfach "normale" Variablen deklarieren und lock() sorgt schon dafür das der Cache aktuell ist!

    3 Jahre zu Spät — June 16, 2011 @ 1:17 pm —



Some HTML is OK

or, reply to this post via trackback.

WP SlimStat