How to manage a dictionary of lazily created objects in a multithreaded environment in .NET?

Question

Dear ladies and sirs.

This question is in continuation of this one. The deal is simple.

Given:

• A collection of lazily created singletons.
• Multithreaded environment.

Wanted:

• An implementation with as little lock penalty as possible when an already created object is accessed. It is OK to pay higher penalty on removal or lazy initialization of a new object.

Let us consider the good old C++ style implementation of a singleton, used as an illustration of the if-lock-if pattern:

public static SomeType Instance
{
  get
  {
    if (m_instance == null)
    {
      lock(m_lock)
      {
        if (m_instance == null)
        {
          m_instance = new SomeType();
        }
      }
    }
    return m_instance;
  }
}

Again, this is just an illustration of the if-lock-if pattern.

Clearly, there is no lock penalty at all when accessing an already constructed object. Is it possible to devise a collection of lazily created objects in the same spirit of keeping the penalty minimal when the particular object is already created? It is fine to pay higher penalty when the object is removed.

Thanks.

EDIT:

I have rewritten the question to completely erase the word singleton from it, since people tend to attribute too much attention to it and not to the core of the question.

Answer 1

I can't see why IDictionary<string, object> singletons with same double-check approach cannot be used in GetInstance():

public object GetInstance(string key)
{
      if(!singletons.ContainsKey(key))
           lock(syncRoot)
                if(!singletons.ContainsKey)
                     singletons[key] = new ...();

      return singletons[key];
}

Answer 2

There is a potential multithreading issue on Itanium processors in your code (a, beside from that, very common initialization pattern).

An itanium processor will allocate the memory of the variable and set the variable BEFORE the constructor is called. Therefore if two threads are executed simultaneously, the second thread will se the instance to be non-null, even though it hasn't beein initialized.

The itanium safe way is this:

public static SomeType Instance
{
  get
  {
    if (m_instance == null)
    {
      lock(m_lock)
      {
        if (m_instance == null)
        {
          var tmpInstance = new SomeType();
          System.Threading.Thread.MemoryBarrier();
          m_Instance = tmpInstance;
        }
      }
    }
    return m_instance;
  }
}

The MemoryBarrier() will cause that all memory writes before the memory barrier must be executed before memory writes after the barrier.

But aside from that I think that it is probably the most efficient lazy initialization of static members (because if you want eager instantiation, you can just do it in the static constructor).

Then there are other aspects, such as coupling. Having dependencies to singletons that are declared as static public properties gives a tight coupling in your system, and makes it difficult to test, but that is another story.

Answer 3

You could use a dictionary of Lazy<T> objects, but you'll either need to wait for .NET4, borrow the code from Joe Duffy or code it yourself.

You'd still need to deal with the question of how to synchronise access to the dictionary itself. I'd probably just wrap the dictionary access in a lock block and profile later to decide whether it needs further optimisation. (Monitor based locks actually have pretty good performance when there's not much contention.)

Answer 4

Register all of the types you want to act as singletons into a windsor container instance with the lifestyle set to singleton and let the container manage it for you ( singletons without singletons are the best kind of singletons there are ).

By registering each type with a key you can use container.Resolve( key ) to retrieve the component you require by name rather than type.

Answer 5

One idea is to create the dictionary during initialization of the program, and fill it immediately with required singletons/objects. Don't modify the dictionary after, and just access it in a read only fashion, I'm assuming that the dictionary is thread safe for reading (I'd find it strange if that wasn't the case).

I'm assuming that if you're using singletons, there will be a limited number of them, and they will eventually be needed, so should be little harm in creating them up front, and therefore avoiding a lock around the whole collection every time access is needed to a singleton.

Answer 6

I can only think of this... one problem with this approach is the fact that you must know in advance the maximum capacity of your dictionary as internally it will use an array to be able to compare and exchange on it.

public class MyClass<TKey, TValue> where TValue : class, new
{
   private bool lockTaken = false;
   private SpinLock mSpinLock = new SpinLock();

   private readonly TValue[] myObjects;
   private readonly LinkedList<int> freeSpaces = new LinkedList<int>();

   private Dictionary<TKey, int> map = new Dictionary<TKey, int>();        


   private TValue Lazy(int ix)
   {
      // Atomically create the object if needed
      Interlocked.CompareExchange<TValue>(ref myObjects[ix], new TValue(), null);
      return (myObjects[ix]);
   }

   public TValue LazyGetValue(TKey key)
   {
      try
      {
         // Check for key existance or add it
         mSpinLock.Enter(ref lockTaken);
         if (map.ContainsKey(key))
            int ix = map[key];
         else // Find an empty space in the array
            map[key] = FindEmptySpace();                                 
      }
      finally
      {
         if (lockTaken)
         {
            mSpinLock.Exit();
            // Lazy create the object if needed
            if (myObjects[ix] != null)
               return myObjects[ix];
            else            
               return Lazy(ix);
         }
      }            
      throw new Exception("Couldn't lock"); 
   }

   public MyClass(int maxCapacity)
   {
      myObjects = new TValue[maxCapacity];
   }

}

Of course you have to spinlock in order to check for the existance of the key but that should get you little contention. There probably are some security checks missing from the code, as well as the method body for FindEmptySpace which finds a free index in the array.

Joe Duffy has a single implementation of a spinlock in this article and this other one. Spinlock is also included with the Parallels Extensions and in the new .Net 4.0

Answer 7

• You could have a non-lazy collection of lazy proxy objects; each proxy object has a reference to the 'real' content of that slot, and that reference can be null-checked without a lock.

• If your set of lazily-created objects is known in advance, forget the dictionary entirely and just create an class with dedicated fields for each lazy object; those fields can be null-checked without a lock.

• Instead of a dictionary, use integer values as your keys and store your values in a large array; references in the array can be null-checked without a lock.

Answer 8

I suggest you write your own dictionary implementation (or provide your own multi-threading wrapper). The .net dictionary (and the wrapper for multi-threading) has a rather simple lock schema. What you need is to control lock at a very granular level, for example: retrieving an object does not need to modify the internal data structure, so it is ok to allow multiple retrieves to happen at the same time. A complete race control strategy cannot be covered in this reply but I suggest you take a shortcut by reading how SQL Server uses read lock, write lock, update lock ... You can find these information in MSDN.

Answer 9

It is for precisely this case that I still use Hashtable on occasion. Hashtable is multi-reader, single-writer thread-safe, so you can use it in the double-checked locking pattern pretty much the same as you would a field:

public static SomeType Instance
{
  get
  {
    if (!m_ht.Contains(typeof(SomeType)))
    {
      lock(m_lock)
      {
        if (!m_ht.Contains(typeof(SomeType)))
        {
          m_ht[typeof(SomeType)] = new SomeType();
        }
      }
    }
    return (SomeType)m_ht[typeof(SomeType)];
  }
}

Just don't ever enumerate all the Keys or Values.

Answer 10

The easiest solution I can think of is wrapping a Hashtable to get type and thread safety. You can do this because the HashTable class is thread-safe for multiple readers and a single writer. The drawback is - as far as I know - that Hashtable is slower then Dictionary<TKey, TValue>. And for developers like me caring about the details it costs quite an effort to use a collection of Objects.

internal abstract class LazyInitializedDictionary<TKey, TValue>
{
   private readonly Hashtable store = new Hashtable();

   internal TValue this[TKey key]
   {
      get
      {
         if (!this.store.ContainsKey(key))
         {
            lock (this.store)
            {
               if (!this.store.ContainsKey(key))
               {
                  this.store.Add(key, this.CreateNewValue(key));
               }
            }
         }

         return (TValue)this.store[key];
      }
   }

   internal Boolean Remove(TKey key)
   {
      if (this.store.ContainsKey(key))
      {
         lock (this.store)
         {
            if (this.store.ContainsKey(key))
            {
               this.store.Remove(key);

               return true;
            }
         }
      }

      return false;
   }   

   protected abstract TValue CreateNewValue(TKey key);
}

With this at hand you can create a derived class implementing your desired behavior. For example a very helpful class making String.Length obsolete... ;)

internal sealed class StringLengthLookup :
   LazyInitializedDictionary<String, Int32>
{
   protected override Int32 CreateNewValue(String key)
   {
      return key.Length;
   }
}