thread-safe Memoizzazione

Question

Diamo Wes Dyer's approccio a funzionare Memoizzazione come punto di partenza:

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

Il problema è, quando lo si utilizza da più thread, siamo in grado di mettersi nei guai:

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! 

Proviamo a evitare questo. Chiudendo 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; 
    }; 
} 

è chiaramente un'idea orribile, perché ci impedisce di calcolo f1 su molti differenti argomenti contemporaneamente. Il blocco su a non funziona se a ha un tipo di valore (e in ogni caso è una cattiva idea, dal momento che non controlliamo a e il codice esterno potrebbe bloccarlo anch'esso).

Qui ci sono due opzioni che posso pensare:

Ipotizzando una classe Lazy<T> per la valutazione pigra (vedi 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 mantenere un dizionario aggiuntivo di oggetti per la sincronizzazione:

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

Qualche opzione migliore?

Answer 1

Usa NET 4.0 del ConcurrentDictionary<A, R> senza inutili Lazy<R>.
La chiave è GetOrAdd(A, Func<A, R>) che rende in un lambda splendidamente banale.

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

Aggiornamento La soluzione di cui sopra non consentire a più lettori simultanei & scrittori con il minimo di spese generali. Tuttavia, non impedisce di eseguire f(a) più volte per lo stesso valore (durante il periodo in cui viene calcolato).

Se ciò è vitale per te, puoi inserire il valore in Lazy<R> ma devi sostenere un costo per ogni lettura.

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

Aggiornamento test Timing per un milione di legge di un pre-popolato 1000 oggetto cache show 19ms per ConcurrentDictionary - come normale Dictionary - ma 720ms per la versione Lazy.

Se ciò sembra troppo ripido, è possibile ottenere il meglio da entrambi i mondi con una soluzione più complessa.

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, non sono opzioni migliori.

La versione con la valutazione lenta è inutile, in quanto la si valuta immediatamente. La versione con il dizionario di sincronizzazione non funziona correttamente poiché non si sta proteggendo il dizionario della mappa all'interno di un lucchetto prima di utilizzarlo.

La versione che hai chiamato orribile è in realtà l'opzione migliore. È necessario proteggere il dizionario della mappa all'interno di un blocco in modo che solo un thread alla volta possa accedervi. Il dizionario non è thread-safe, quindi se si lascia leggere un thread mentre un altro thread lo sta cambiando, si avranno dei problemi.

Ricordare che l'utilizzo del blocco sull'oggetto mappa non protegge l'oggetto della mappa in sé stesso, è solo utilizzando il riferimento mappa come identificativo per mantenere più di un thread alla volta per eseguire il codice all'interno del blocco. Devi mettere tutto il codice che accede all'oggetto all'interno del lucchetto, non solo il codice che sta cambiando l'oggetto.

Answer 3

Se si dispone già di che tipo Lazy<T>, presumo che si sta utilizzando .NET 4.0, così si potrebbe anche utilizzare il 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

Hai letto il comment from Dyer relative al thread-safe in questo articolo ?

Probabilmente il modo più semplice per rendere Memoize thread-safe è mettere un lucchetto sulla mappa.

Ciò garantisce che la funzione che viene memoized verrà eseguita una sola volta per ogni serie di argomenti distinti.

Nel mio esempio del gioco RoboRally, ho effettivamente utilizzato la funzione memoization per fungere da "surrogate singleton".Non è realmente un singleton dato che può esserci un'istanza per istanza di fabbrica (a meno che la fabbrica non sia statica). Ma è esattamente quello che volevo.

Answer 5

Non si desidera calcolare lo stesso valore due volte e si desidera che molti thread siano in grado di calcolare valori o recuperare valori contemporaneamente. Per fare ciò è necessario utilizzare una sorta di condizione variabile e un sistema di bloccaggio a grana fine.

Ecco l'idea. quando nessun valore è presente, inserisci un valore nella mappa di sincronizzazione e quindi qualsiasi thread che ha bisogno di quel valore lo aspetterà, altrimenti prenderai il valore corrente. in questo modo il blocco della mappa è ridotto al minimo per interrogare i valori e restituire i valori.

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

     }; 
    } 

Questa è solo una rapida prima prova, ma penso che dimostri la tecnica. Qui stai scambiando memoria aggiuntiva per la velocità.

Answer 6

risposta di Thomas non sembra per compilare sotto .NET 4.0 grazie al parametro enum al costruttore Pigro. L'ho revisionato di seguito. Ho anche aggiunto un parametro opzionale per fornire il proprio comparatore di uguaglianza. Ciò è utile se TInput non implementa i propri Equals o se TInput è una stringa e, ad esempio, si desidera renderlo non sensibile al maiuscolo/minuscolo.

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

ho fatto dei test di base di questo metodo che utilizza questo come il mio test:

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

E sembra funzionare correttamente.

Answer 7

Ampliando eccellente risposta di Nigel Touch, ho voluto offrire un componente riutilizzabile estratto dalla sua soluzione di limitare il conteggio l'invocazione per la f (a).

ho chiamato SynchronizedConcurrentDictionary, e sembra che questo:

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

Poi la funzione Memoize diventa un due-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); 
} 

Cheers!