¿Usando una tabla hash dentro de un Parallel.ForEach?

Question

Tengo un bucle Parallel.ForEach ejecutando una operación intensiva dentro del cuerpo.

La operación puede usar una tabla Hash para almacenar los valores, y puede reutilizarse para otros elementos de bucle consecutivos. Agrego a Hashtable después de completar la operación intensiva, el siguiente elemento de bucle puede buscar en el Hashtable y reutilizar el objeto, en lugar de ejecutar nuevamente la operación intensiva.

Sin embargo, como estoy usando Parallel.ForEach, existe un problema inseguro, que hace que las llamadas Hashtable.Add y ContainsKey (clave) no estén sincronizadas, ya que podrían estar ejecutándose en paralelo. La introducción de bloqueos puede causar problemas de rendimiento.

Aquí está el código de ejemplo:

Hashtable myTable = new Hashtable; 
Parallel.ForEach(items, (item, loopState) => 
{ 
    // If exists in myTable use it, else add to hashtable 
    if(myTable.ContainsKey(item.Key)) 
    { 
     myObj = myTable[item.Key]; 
    } 
    else 
    { 
     myObj = SomeIntensiveOperation(); 
     myTable.Add(item.Key, myObj); // Issue is here : breaks with exc during runtime 
    } 
    // Do something with myObj 
    // some code here 
} 

Debe haber alguna API, el establecimiento de la propiedad dentro de la biblioteca TPL, que pudiera manejar esta situación. ¿Esta ahí?

Answer 1

Está buscando System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue>. Las nuevas colecciones simultáneas utilizan mecanismos de bloqueo significativamente mejorados y deben funcionar de forma excelente en algoritmos paralelos.

Editar: El resultado podría tener este aspecto:

ConcurrentDictionary<T,K> cache = ...; 
Parallel.ForEach(items, (item, loopState) => 
{ 
    K value; 
    if (!cache.TryGetValue(item.Key, out value)) 
    { 
     value = SomeIntensiveOperation(); 
     cache.TryAdd(item.Key, value); 
    } 

    // Do something with value 
}); 

Una palabra de advertencia: si los elementos en items No todos tienen item.Key única, entonces podría conseguir SomeIntensiveOperation llamado dos veces para esa tecla. En el ejemplo, la clave no se pasa al SomeIntensiveOperation, pero significa que el código "Hacer algo con valor" podría ejecutar pares clave/valorA y clave/valorB, y solo un resultado se almacenaría en el caché (no necesariamente el el primero calculado por SomeIntensiveOperation tampoco). Necesitaría una fábrica perezosa paralela para manejar este si es un problema. Además, por razones obvias, SomeIntensiveOperation debe ser seguro para subprocesos.

Answer 2

No veo otra opción correcta que utilizar bloqueos (más o menos explícitos) (Una tabla Hash sincronizada simplemente anula todos los métodos con bloqueos).

Otra opción podría ser permitir que el diccionario se desincronice. La condición de carrera no dañará el diccionario, solo requerirá que el código realice cálculos superfluos. Perfile el código para verificar si el bloqueo o la falta de memoria tienen peores efectos.

Answer 3

Utilice un ReaderWriterLock, este tiene un buen rendimiento para el trabajo que tiene muchas lecturas y pocas escrituras que son de corta duración. Tu problema parece ajustarse a esta especificación.

Todas las operaciones de lectura se ejecutarán rápidamente y se desbloquearán, el único momento en que alguien será bloqueado es cuando se está escribiendo, y esa escritura es solo lo que se requiere para meter algo en una Hashtable.

ReaderWriterLockSlim on MSDN

Creo que voy a tirar abajo algo de código ...

ReaderWriterLockSlim cacheLock = new ReaderWriterLockSlim(); 
Hashtable myTable = new Hashtable(); 
Parallel.ForEach(items, (item, loopState) => 
{ 
    cacheLock.EnterReadLock(); 
    MyObject myObj = myTable.TryGet(item.Key); 
    cacheLock.ExitReadLock(); 

    // If the object isn't cached, calculate it and cache it 
    if(myObj == null) 
    { 
     myObj = SomeIntensiveOperation(); 
     cacheLock.EnterWriteLock(); 
     try 
     { 
      myTable.Add(item.Key, myObj); 
     } 
     finally 
     { 
      cacheLock.ExitWriteLock(); 
     }   
    } 
    // Do something with myObj 
    // some code here 
} 

static object TryGet(this Hashtable table, object key) 
{ 
    if(table.Contains(key)) 
     return table[key] 
    else 
     return null; 
} 

Answer 4

comprobación del espacio de nombres System.Collections.Concurrent creo que es necesario ConcurrentDictionary