Sharing data in dictionary between threads

Question

Assume code:

class Memory {
  Dictionary<int, int> m_values;
  Object lockObject = new Object();

  public int GetData(int key) {
    int result;
    lock (lockObject) {
      if (!m_values.TryGetValue(key, out result)) {
        result = VeryExpensiveComputationMethod(key);
        m_values[key] = result;
      }
    }
    return result
  }
}

This is safe but problem is that it is not very effective. Some idea how to do it better using .NET 2.0-compatible code? (in best scenario only threads waiting for same result for same keys should be waiting)

Answer 1

A simple solution given your .NET 2.0 constraint would be to keep a Dictionary<int, object> where you lookup the lock object for that key, and lock on that object. Thus your locking is more fine-grained and hence supports more concurrency. That said, you'd need another lock of some kind dealing with the case that you have a new unseen int.

Something like this:

internal class Memory
{
    public int GetData(int key)
    {
        int result;
        object locker;

        // short time lock, blocks all readers
        lock (lockObject)
            if (!m_locks.TryGetValue(key, out  locker))
            {
                locker = m_locks[key] = new object();
            }

        // long time lock, but only for readers of this key during expensive op
        lock (locker)
            if (!m_values.TryGetValue(key, out result))
            {
                result = m_values[key] = VeryExpensiveComputationMethod(key);
            }

        return result;
    }

    private readonly Object lockObject = new Object();
    private Dictionary<int, int> m_values;
    private Dictionary<int, object> m_locks;
}

Answer 2

If you use ConcurrentDictionary instead of a Dictionary you get two key improvements:

1. You don't need to bother with explicit locking
2. You have a (guaranteed to be observably atomic) GetOrAdd method that lets you get a value from the dictionary or add a value if one doesn't exist.

Combine that with use of Lazy<T>, which lets you create an object that defines its value as the result of an expensive computation that it ensures is run only once, run only when needed, and then cached and returned again and again if asked for the value repeatedly.

We can now create a ConcurrentDictionary<int, Lazy<int>>, and between these two types, it basically does all of our work for us:

Note that, once we get the Lazy returned from GetOrAdd it means that either:

1. it's a new lazy that hasn't even started computing the value, in which case it will compute the value and return it.
2. It's an existing lazy with an already computed value that can be returned immediately.
3. It's an existing lazy with a value that hasn't finished being computed; it'll wait until the operation finishes, and then that value will be returned to all of the calls waiting on its computation.

Under no circumstances will VeryExpensiveComputationMethod be called multiple times for the same key.

private ConcurrentDictionary<int, Lazy<int>> values =
    new ConcurrentDictionary<int, Lazy<int>>();

public int GetData(int key)
{
    //Note that this doesn't actually run VeryExpensiveComputationMethod 
    //until .Value is called on it
    var lazy = new Lazy<int>(() => VeryExpensiveComputationMethod(key));
    return values.GetOrAdd(key, lazy).Value;
}

---

As far as a .NET 2.0 solution, you don't have either type. Using a Dictionary and locking is of course doable, just less clean:

private Dictionary<int, Lazy<int>> values;
private object sync = new object();
public int GetData(int key)
{
    Lazy<int> lazy;
    lock (sync)
    {
        if (!values.TryGetValue(key, out lazy))
        {
            lazy = new Lazy<int>(delegate
            {
                return VeryExpensiveComputationMethod(key);
            });
            values.Add(key, lazy);
        }
    }
    return lazy.Value;
}

As far as Lazy, you simply need to create your own version:

public delegate T Func<T>();
public class Lazy<T>
{
    private object key = new object();
    private Func<T> generator;
    private T value;
    public Lazy(Func<T> generator)
    {
        this.generator = generator;
    }

    private volatile bool hasComputedValue;
    public bool HasComputedValue { get { return hasComputedValue; } }

    public T Value
    {
        get
        {
            lock (key)
            {
                if (HasComputedValue)
                    return value;
                else
                {
                    value = generator();
                    hasComputedValue = true;
                    generator = null;
                    return value;
                }
            }
        }
    }
}

Answer 3

Pure .NET2.0 solution:

public delegate T Compute<T,TParameter>(TParameter parameter);

public sealed class Lazy<T,TParameter>
{
  private T m_Result;
  private volatile bool m_IsInitialized;
  private object m_SyncRoot = new object();
  private Compute<T,TParameter> m_Compute;
  private TParameter m_Context;

  public Lazy(Compute<T,TParameter> compute, TParameter context)
  {
    if (compute == null)
    {
      throw new ArgumentNullException("compute");
    }

    m_Compute = compute;
    m_Context = context;
  }

  public T Value
  {
    get
    {
      if (!m_IsInitialized)
      {
        lock (m_SyncRoot)
        {
          if (!m_IsInitialized)
          {
            m_Result = m_Compute.Invoke(m_Context);
            m_Compute = null;
            m_Context = default(TParameter);
            m_IsInitialized = true;
          }
        }
      }
      return m_Result;
    }
  }
}

class Memory
{
  static int VeryExpensiveComputationMethod(int key)
  {
    return key;
  }

  private Dictionary<int, Lazy<int,int>> m_Values = new Dictionary<int, Lazy<int,int>>();
  private object m_SyncRoot = new object();

  public int GetData(int key)
  {
    Lazy<int,int> result;
    lock (m_SyncRoot)
    {
      if (!m_Values.TryGetValue(key, out result))
      {
        result = new Lazy<int,int>(VeryExpensiveComputationMethod, key);
        m_Values[key] = result;
      }
    }
    return result.Value;
  }
}