¿Por qué la modificación concurrente de matrices es tan lenta?

Question

Estaba escribiendo un programa para ilustrar los efectos de la contención de caché en programas multiproceso. Mi primer corte fue crear una matriz de long y mostrar cómo la modificación de elementos adyacentes causa contención. Aquí está el programa.

const long maxCount = 500000000; 
const int numThreads = 4; 
const int Multiplier = 1; 
static void DoIt() 
{ 
    long[] c = new long[Multiplier * numThreads]; 
    var threads = new Thread[numThreads]; 

    // Create the threads 
    for (int i = 0; i < numThreads; ++i) 
    { 
     threads[i] = new Thread((s) => 
      { 
       int x = (int)s; 
       while (c[x] > 0) 
       { 
        --c[x]; 
       } 
      }); 
    } 

    // start threads 
    var sw = Stopwatch.StartNew(); 
    for (int i = 0; i < numThreads; ++i) 
    { 
     int z = Multiplier * i; 
     c[z] = maxCount; 
     threads[i].Start(z); 
    } 
    // Wait for 500 ms and then access the counters. 
    // This just proves that the threads are actually updating the counters. 
    Thread.Sleep(500); 
    for (int i = 0; i < numThreads; ++i) 
    { 
     Console.WriteLine(c[Multiplier * i]); 
    } 

    // Wait for threads to stop 
    for (int i = 0; i < numThreads; ++i) 
    { 
     threads[i].Join(); 
    } 
    sw.Stop(); 
    Console.WriteLine(); 
    Console.WriteLine("Elapsed time = {0:N0} ms", sw.ElapsedMilliseconds); 
} 

estoy ejecutando Visual Studio 2010, programa compilado en modo de lanzamiento, .NET 4.0 objetivo "Cualquier CPU", y ejecutado en el tiempo de ejecución de 64 bits sin el depurador asociado (Ctrl + F5).

Ese programa se ejecuta en aproximadamente 1,700 ms en mi sistema, con un solo hilo. Con dos hilos, lleva más de 25 segundos. Calculando que la diferencia era la contención del caché, configuré Multipler = 8 y volví a ejecutar. El resultado es 12 segundos, por lo que la contención fue al menos parte del problema.

Aumentar Multiplier más allá de 8 no mejora el rendimiento.

Para comparar, un similar program that doesn't use an array toma solo unos 2,200 ms con dos hilos cuando las variables son adyacentes. Cuando separo las variables, la versión de dos hilos se ejecuta en el mismo período de tiempo que la versión de un solo subproceso.

Si el problema era la tara de indexación de matriz, esperaría que apareciera en la versión de subproceso único. Me parece que hay algún tipo de exclusión mutua al modificar la matriz, pero no sé qué es.

En cuanto a la IL generada no es muy esclarecedor. Tampoco estaba viendo el desmontaje. El desmontaje muestra un par de llamadas a (creo) la biblioteca de tiempo de ejecución, pero no pude entrar en ellas.

No soy experto en windbg u otras herramientas de depuración de bajo nivel en estos días. Ha pasado mucho tiempo desde que los necesitaba. Así que estoy perplejo.

Mi única hipótesis en este momento es que el código de tiempo de ejecución establece un indicador "sucio" en cada escritura. Parece que algo así se requeriría para soportar arrojar una excepción si la matriz se modifica mientras se enumera. Pero admito que no tengo evidencia directa para respaldar esa hipótesis.

¿Alguien puede decirme qué está causando esta gran ralentización?

Answer 1

Tiene el intercambio falso. Escribí un artículo al respecto here