El uso de una tabla hash dentro de un Parallel.ForEach?

Question

Tengo un bucle Parallel.ForEach ejecuta una operación intensiva en el interior del cuerpo.

La operación se puede utilizar una tabla hash para almacenar los valores, y puede ser reutilizado para otros artículos de bucle consecutivos. Añado a la tabla hash después de la operación intensiva se ha completado, el siguiente elemento de bucle puede mirar hacia arriba en la tabla hash y reutilizar el objeto, en lugar de ejecutar la operación intensiva de nuevo.

Sin embargo, debido a que estoy usando Parallel.ForEach hay un problema de inseguridad, haciendo que el Hashtable.Add y la ContainsKey llamadas (clave) no están sincronizados, ya que podrían estar ejecutándose en paralelo. La introducción de las cerraduras puede causar problemas perf.

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
}

Tiene que haber alguna API, el establecimiento de la propiedad dentro de la biblioteca TPL, que pudiera manejar esta situación. ¿Hay?

Answer 1

System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue> . Las nuevas colecciones concurrentes uso mejorado significativamente mecanismos de bloqueo y deben realizar excellectly en algoritmos paralelos.

Edit: 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 único, entonces podría conseguir SomeIntensiveOperation llamado dos veces para esa tecla. En el ejemplo, la clave no se pasa a SomeIntensiveOperation, sino que significa que el código "Hacer algo con valor" podría ejecutar pares de claves / ValorA y clave / ValorB, y sólo uno de los resultados conseguiría almacenado en la memoria caché (no necesariamente el primero uno computado por SomeIntensiveOperation tampoco). Se necesitaría una fábrica perezosa paralelo para manejar este si es un problema. Además, por razones obvias SomeIntensiveOperation debe ser de subprocesos.

Answer 2

System.Collections. concurrente espacio de nombres creo que necesita ConcurrentDictionary

Answer 3

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

Todas las operaciones de lectura se ejecutará de forma rápida y bloqueo de la libre, la única vez que alguien va a ser bloqueado es cuando una escritura está sucediendo, y que escribir es sólo el tiempo que se necesita para empujar algo en una tabla hash.

ReaderWriterLockSlim en 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

No veo ninguna otra opción correcta que utilizar (más o menos explícito) cerraduras (una tabla hash sincronizada simplemente anula todos los métodos con cerraduras).

Otra opción podría ser la de permitir que el diccionario de ir fuera de sincronización. La condición de carrera no corromper el diccionario, se acaba de requerir que el código para hacer algunos cálculos superfluos. Perfil el código para comprobar si el bloqueo o desaparecidos memoization tiene peores efectos.