Hilo de seguridad memoization

Question

Tomemos Wes Dyer's enfoque para funcionar memoization como punto de partida:

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; 
    }; 
} 

El problema es que cuando se utiliza desde varios subprocesos, podemos tener problemas:

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! 

Tratemos de evitar esto. Bloqueo en 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; 
    }; 
} 

es claramente una idea horrible, porque no permite calcular la f1 en muchas diferentes argumentos a la vez. Bloquear en a no funcionará si a tiene un tipo de valor (y en cualquier caso es una mala idea, ya que no controlamos a y el código externo también puede bloquearse).

Aquí hay dos opciones que se me ocurre:

Suponiendo una clase Lazy<T> para la evaluación perezosa (ver here):

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; 
    }; 
} 

o mantener un diccionario adicional de objetos para la sincronización:

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; 
     } 
    }; 
} 

¿Alguna mejor opción?

Answer 1

Utilice .net 4.0's ConcurrentDictionary<A, R> sin el innecesario Lazy<R>.
La clave es GetOrAdd(A, Func<A, R>) que se convierte en una lambda bellamente trivial.

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); 
}; 

actualización La solución anterior hace permitir que varios lectores simultáneos & escritores con el mínimo de gastos generales. Sin embargo, no impide que se ejecute f(a) más de una vez por el mismo valor (durante el período mientras se calcula).

Si eso es vital para usted, puede ajustar el valor en Lazy<R>, pero tiene un costo por cada lectura.

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; 
} 

actualización las pruebas de tiempo de un millón lee de un pre-poblada 1000 demostración del artículo caché 19ms para ConcurrentDictionary - igual que regular de Dictionary - pero 720ms para la versión Lazy.

Si eso suena demasiado empinado, puede obtener lo mejor de ambos mundos con una solución más compleja.

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

No, no son mejores opciones.

La versión con la evaluación perezosa no tiene sentido ya que la evalúas inmediatamente de todos modos. La versión con el diccionario de sincronización no funciona correctamente, ya que no está protegiendo el diccionario de mapas dentro de un bloqueo antes de usarlo.

La versión que llamas horrible es en realidad la mejor opción. Debe proteger el diccionario de mapas dentro de un bloqueo para que solo un hilo a la vez pueda acceder a él. El diccionario no es seguro para subprocesos, por lo que si deja que un hilo lo lea mientras otro hilo lo está modificando, tendrá problemas.

Recuerde que el uso del bloqueo en el objeto del mapa no protege el objeto del mapa en sí mismo, solo utiliza la referencia del mapa como identificador para mantener más de un hilo a la vez para ejecutar el código dentro del bloqueo. Debe colocar todo el código que accede al objeto dentro del bloqueo, no solo el código que está cambiando el objeto.

Answer 3

Si ya tiene que Lazy<T> tipo, supongo que está utilizando .NET 4.0, por lo que también podría utilizar el 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; 
    }; 
} 

Answer 4

¿Ha leído el comment from Dyer relacionada con hilo de fallos en el artículo ?

Probablemente la forma más fácil de hacer que Memoize sea seguro para subprocesos es colocar un candado en el mapa.

Esto asegurará que la función que se está recordando solo se ejecutará una vez para cada conjunto de argumentos distintos.

En mi ejemplo del juego RoboRally, en realidad usé la función de memoria para actuar como "singleton sustituto".No es realmente un singleton ya que puede haber una instancia por instancia de fábrica (a menos que la fábrica sea estática). Pero eso es exactamente lo que quería.

Answer 5

No desea calcular el mismo valor dos veces y desea que muchos subprocesos puedan calcular valores o recuperar valores al mismo tiempo. Para hacer esto, necesitará usar algún tipo de variable de condición y sistema de bloqueo de grano fino.

Aquí está la idea. cuando no hay ningún valor presente, usted coloca un valor en el mapa de sincronización y luego cualquier hilo que necesite ese valor lo esperará, de lo contrario, simplemente obtendrá el valor actual. de esta forma, el bloqueo del mapa se minimiza para consultar valores y devolver valores.

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 = 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]; 
      } 

     }; 
    } 

Esto es solo un primer intento rápido, pero creo que demuestra la técnica. Aquí está intercambiando memoria adicional por velocidad.

Answer 6

La respuesta de Thomas no parece compilarse en .NET 4.0 debido al parámetro enum del constructor Lazy. Lo revisé a continuación. También agregué un parámetro opcional para suministrar el propio comparador de igualdad. Esto es útil si TInput no implementa sus propios equivalentes o si TInput es una cadena y desea que no distinga entre mayúsculas y minúsculas, por ejemplo.

public static Func<TInput, TResult> Memoize<TInput, TResult>(
     this Func<TInput, TResult> func, IEqualityComparer<TInput> comparer = null) 
    { 
     var map = comparer == null 
         ? new ConcurrentDictionary<TInput, Lazy<TResult>>() 
         : new ConcurrentDictionary<TInput, Lazy<TResult>>(comparer); 

     return input => 
       { 
        var lazy = new Lazy<TResult>(() => func(input), LazyThreadSafetyMode.ExecutionAndPublication); 

        return map.TryAdd(input, lazy) 
           ? lazy.Value 
           : map[input].Value; 
       }; 
    } 

Hice algunas pruebas básicas de este método usando esto como mi prueba:

public void TestMemoize() 
    { 
     Func<int, string> 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)))); 
    } 

Parece estar funcionando correctamente.

Answer 7

Ampliando excelente respuesta táctil de Nigel, quería ofrecer un componente reutilizable extrae de su solución de limitar el recuento de invocación para f (a).

lo llamé SynchronizedConcurrentDictionary, y se ve así:

public class SynchronizedConcurrentDictionary<TKey, TValue> : ConcurrentDictionary<TKey, TValue> 
{ 
    private readonly ReaderWriterLockSlim _cacheLock = new ReaderWriterLockSlim(); 

    public new TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory) 
    { 
     TValue result; 

     _cacheLock.EnterWriteLock(); 
     try 
     { 
      result = base.GetOrAdd(key, valueFactory); 
     } 
     finally 
     { 
      _cacheLock.ExitWriteLock(); 
     } 

     return result; 
    } 
} 

Entonces la función memoize se convierte en un dos-liner:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var cache = new SynchronizedConcurrentDictionary<A, R>(); 

    return key => cache.GetOrAdd(key, f); 
} 

Salud!