线程安全的memoization

Question

让我们以Wes Dyer的函数memoization方法为出发点:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new Dictionary<A, R>();
  return a =>
    {
      R value;
      if (map.TryGetValue(a, out value))
        return value;
      value = f(a);
      map.Add(a, value);
      return value;
    };
}

问题是,当从多个线程使用它时,我们可能会遇到麻烦:

Func<int, int> f = ...
var f1 = f.Memoize();
...
in thread 1:
var y1 = f1(1);
in thread 2:
var y2 = f1(1);
// We may be recalculating f(1) here!

我们试着避免这种情况.锁定map:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new Dictionary<A, R>();
  return a =>
    {
      R value;
      lock(map) 
      {
        if (map.TryGetValue(a, out value))
          return value;
        value = f(a);
        map.Add(a, value);
      }
        return value;
    };
}

显然是一个可怕的想法,因为它阻止我们立刻计算f1许多不同的论点.a如果a具有值类型,则锁定将不起作用(并且无论如何都是一个坏主意,因为我们无法控制a,外部代码也可能锁定它).

以下是我能想到的两个选项:

假设有一个Lazy<T>懒惰评估类(见这里):

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new Dictionary<A, Lazy<R>>();
  return a =>
    {
      Lazy<R> result;
      lock(map) 
      {
        if (!map.TryGetValue(a, out result))
        {  
          result = () => f(a);
          map.Add(a, result);
        }
      }
      return result.Value;
    };
}

或者保留一个额外的对象字典以进行同步:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new Dictionary<A, R>();
  var mapSync = new Dictionary<A, object>();
  return a =>
    {
      R value;
      object sync;
      lock(mapSync)
      { 
        if (!mapSync.TryGetValue(a, out sync))
        { 
          sync = new object();
          mapSync[a] = sync;
        }
      }
      lock(map)
      {
        if (map.TryGetValue(a, out value))
          return value;
      }
      lock(sync)
      {
        value = f(a);
        lock(map)
        {
          map[a] = value;
        }
        return value;
      }
    };
}

有更好的选择吗？

Answer 1

使用.net 4.0 ConcurrentDictionary<A, R>没有必要Lazy<R>.
关键是GetOrAdd(A, Func<A, R>)渲染成一个美丽琐碎的lambda.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var cache = new ConcurrentDictionary<A, R>();
    return a => cache.GetOrAdd(a, f);
};

更新上述解决方案确实允许多个同时读写器具有最小的开销.但是,它不会阻止f(a)对同一个值执行多次(在计算期间).

如果这对您来说至关重要,您可以将价值包装起来,Lazy<R>但每次阅读都会产生费用.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var cache = new ConcurrentDictionary<A, Lazy<R>>();
    return a => cache.GetOrAdd(a, new Lazy<R>(() => f(a))).Value;
}

更新一百万计时测试预先填充的1000项高速缓存秀读取19ms的ConcurrentDictionary-同样作为常规Dictionary-但720ms的Lazy版本.

如果这听起来太陡,你可以通过更复杂的解决方案获得两全其美.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var cache = new ConcurrentDictionary<A, R>();
    var syncMap = new ConcurrentDictionary<A, object>();
    return a =>
    {
        R r;
        if (!cache.TryGetValue(a, out r))
        {
            var sync = syncMap.GetOrAdd(a, new object());
            lock (sync)
            {
                r = cache.GetOrAdd(a, f);
            }
            syncMap.TryRemove(a, out sync);
        }
        return r;
    };
}

Answer 2

如果你已经有这种Lazy<T>类型,我假设你使用.net 4.0,所以你也可以使用ConcurrentDictionary<A,R>:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new ConcurrentDictionary<A, Lazy<R>>();
  return a =>
    {
      Lazy<R> lazy = new Lazy<R>(() => f(a), LazyExecutionMode.EnsureSingleThreadSafeExecution);
      if(!map.TryAdd(a, lazy))
      {
        return map[a].Value;
      }
      return lazy.Value;
    };
}