线程安全的memoization

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

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

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

 Func 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 Memoize(this Func f) { var map = new Dictionary(); 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将无法工作。

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

假设一个Lazy评估的Lazy类（见这里 ）：

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

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

 public static Func Memoize(this Func f) { var map = new Dictionary(); var mapSync = new Dictionary(); 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没有不必要的Lazy 。
关键是GetOrAdd(A, Func) ，它呈现出一个非常琐碎的lambda。

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

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

如果这对您至关重要，您可以将值包装在Lazy但每次读取都会产生成本。

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

对于预先填充的1000项缓存的一百万次读取的更新时序测试显示ConcurrentDictionary 19ms – 与常规Dictionary相同 – 但是对于Lazy版本为720ms 。

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

 public static Func Memoize(this Func f) { var cache = new ConcurrentDictionary(); var syncMap = new ConcurrentDictionary(); 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类型，我假设你使用的是.net 4.0，所以你也可以使用ConcurrentDictionary ：

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

Answer 3

由于Lazy构造函数的枚举参数，Thomas的答案似乎不能在.NET 4.0下编译。 我在下面修改了它。 我还添加了一个可选参数，用于提供自己的相等比较器。 如果TInput没有实现自己的Equals，或者TInput是一个字符串，并且你想让它不区分大小写，那么这很有用。

  public static Func Memoize( this Func func, IEqualityComparer comparer = null) { var map = comparer == null ? new ConcurrentDictionary>() : new ConcurrentDictionary>(comparer); return input => { var lazy = new Lazy(() => func(input), LazyThreadSafetyMode.ExecutionAndPublication); return map.TryAdd(input, lazy) ? lazy.Value : map[input].Value; }; } 

我用这个作为我的测试对这个方法进行了一些基本的测试：

  public void TestMemoize() { Func mainFunc = i => { Console.WriteLine("Evaluating " + i); Thread.Sleep(1000); return i.ToString(); }; var memoized = mainFunc.Memoize(); Parallel.ForEach( Enumerable.Range(0, 10), i => Parallel.ForEach(Enumerable.Range(0, 10), j => Console.WriteLine(memoized(i)))); } 

它似乎工作正常。

Answer 4

扩展Nigel Touch的优秀答案，我想提供一个可重用的组件，从他的解决方案中提取，限制了f（a）的调用次数。

我称它为SynchronizedConcurrentDictionary，它看起来像这样：

 public class SynchronizedConcurrentDictionary : ConcurrentDictionary { private readonly ReaderWriterLockSlim _cacheLock = new ReaderWriterLockSlim(); public new TValue GetOrAdd(TKey key, Func valueFactory) { TValue result; _cacheLock.EnterWriteLock(); try { result = base.GetOrAdd(key, valueFactory); } finally { _cacheLock.ExitWriteLock(); } return result; } } 

然后Memoize函数变成了两行：

 public static Func Memoize(this Func f) { var cache = new SynchronizedConcurrentDictionary(); return key => cache.GetOrAdd(key, f); } 

干杯!

Answer 5

不，他们不是更好的选择。

具有惰性评估的版本毫无意义，因为您无论如何都会立即对其进行评估。 具有同步字典的版本无法正常工作，因为您在使用之前未保护锁内的地图字典。

你称之为可怕的版本实际上是最好的选择。 您必须保护锁内的地图字典，以便一次只能有一个线程访问它。 字典不是线程安全的，所以如果你让一个线程从中读取而另一个线程正在更改它，那么你将遇到问题。

请记住，在地图对象上使用锁不会保护地图对象本身，它只使用地图引用作为标识符来一次保留多个线程来运行锁内的代码。 您必须将访问对象的所有代码放在锁内，而不仅仅是更改对象的代码。

Answer 6

您不希望计算两次相同的值，并且您希望许multithreading能够同时计算值和/或检索值。 要做到这一点，您需要使用某种条件变量和细粒度锁定系统。

inheritance人的想法。 当没有值存在时，你将一个值放入同步映射，然后任何需要该值的线程将等待它，否则你将只获取当前值。 这样，地图的锁定最小化，以查询值和返回值。

  public static Func Memoize(this Func f) { var map = new Dictionary(); var mapSync = new Dictionary(); return a => { R value; object sync = null; bool calc = false; bool wait = false; lock (map) { if (!map.TryGetValue(a, out value)) { //its not in the map if (!mapSync.TryGetValue(a, out sync)) { //not currently being created sync = new object(); mapSync[a] = sync; calc = true; } else { calc = false; wait = true; } } } if(calc) { lock (sync) { value = f(a); lock (map) { map.Add(a, value); mapSync.Remove(a); } Monitor.PulseAll(sync); return value; } } else if (wait) { lock (sync) { while (!map.TryGetValue(a, out value)) { Monitor.Wait(sync); } return value; } } lock (map) { return map[a]; } }; } 

这只是一个快速的第一次尝试，但我认为它演示了该技术。 在这里，您正在为速度交换额外的内存。

Answer 7

您是否在文章中阅读了Dyer关于线程安全的评论 ？

使Memoize线程安全的最简单方法可能是锁定地图。

这将确保正在被记忆的函数仅对每组不同的参数运行一次。

在我的RoboRally游戏的例子中，我实际上使用了函数记忆来充当“代理单身人士”。 它实际上不是单例，因为每个工厂实例可以有一个实例（除非工厂是静态的）。 但这正是我想要的。