Perché la modifica simultanea degli array è così lenta?

Question

Stavo scrivendo un programma per illustrare gli effetti della contesa della cache nei programmi multithread. Il mio primo taglio è stato quello di creare un array di long e mostrare come la modifica degli oggetti adiacenti causa conflitto. Ecco il programma.

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

Io corro Visual Studio 2010, programma compilato in modalità di rilascio, NET 4.0 bersaglio, "Any CPU", ed eseguito nel runtime a 64 bit senza il debugger (Ctrl + F5).

Questo programma viene eseguito in circa 1.700 ms sul mio sistema, con una singola discussione. Con due thread, ci vogliono più di 25 secondi. Capendo che la differenza era la contesa della cache, ho impostato Multipler = 8 e ho eseguito nuovamente. Il risultato è 12 secondi, quindi la contesa era almeno parte del problema.

L'aumento di Multiplier oltre 8 non migliora le prestazioni.

Per confronto, un similar program that doesn't use an array richiede solo circa 2.200 ms con due thread quando le variabili sono adiacenti. Quando separo le variabili, la versione a due thread viene eseguita nella stessa quantità di tempo della versione a thread singolo.

Se il problema era l'overhead di indicizzazione degli array, ci si aspetta che venga visualizzato nella versione a thread singolo. Mi sembra che ci sia una sorta di mutua esclusione in corso quando si modifica la matrice, ma non so cosa sia.

Guardare l'IL generato non è molto illuminante. Né stava visualizzando lo smontaggio. Lo smontaggio mostra un paio di chiamate a (credo) la libreria di runtime, ma non sono stato in grado di intervenire su di esse.

Attualmente non sono esperto con windbg o altri strumenti di debug di basso livello. È passato molto tempo da quando avevo bisogno di loro. Quindi sono perplesso.

La mia unica ipotesi al momento è che il codice runtime imposta un flag "dirty" su ogni scrittura. Sembra che sia necessario qualcosa del genere per supportare il lancio di un'eccezione se la matrice viene modificata mentre viene enumerata. Ma ammetto prontamente di non avere prove dirette per sostenere quell'ipotesi.

Qualcuno può dirmi che cosa sta causando questo grande rallentamento?

Answer 1

Hai false condivisioni. Ho scritto un articolo a riguardo here