Verwirrendes Caching-Verhalten eines einfachen C-Programms

Question

Ich experimentiere mit einem Programm, um zu sehen, ob sein Caching-Verhalten mit meinem konzeptionellen Verständnis übereinstimmt.

Um dies zu tun, ich den Perf Befehl bin mit:

int main() { 
    int N = 10000; 
    double *arr = malloc(sizeof(double) * N * N); 

    for(int i = 0; i < N; i++) { 
     for(int j = 0; j < N; j++){ 
      arr[i * N + j] = 10.0; 
     } 
    } 
    return 0; 
} 

ich einen Cache:

perf stat -e cache-misses ./a.out 

das Cache-Miss-Verhältnis des folgenden einfachen C Programms aufzeichnen -miss-Verhältnis von 50,212%. Wenn ich das Array-Zugriffsmuster wie folgt ändere:

Ich bekomme, dass das Cache-Miss-Verhältnis 22,206% ist.

Diese Ergebnisse sind überraschend für mich.

1. Der Cache-miss-Verhältnis von 50,212% scheint für ein solches einfaches Programm mit einem sehr regelmäßigen Speicherzugriffsmuster sehr hoch. Ich würde erwarten, dass dies näher bei 1/(Anzahl Wörter pro Cache-Zeile) liegt, was definitiv größer als 1/2 ist. Warum ist das Cache-Miss-Verhältnis so hoch?
2. Mein (begrenztes) Verständnis von Speicher schlägt vor, dass das Iterieren über das Array in der Reihenfolge der Spalten-Major zu viel schlechterem Caching-Verhalten führen sollte, aber die Ergebnisse, die ich erhalte, zeigen das Gegenteil an. Was ist los?

Answer 1

Die Antwort ist ziemlich einfach: Compiler optimieren Sie Ihre Aufgaben. Hier ist, wie die Demontage wie für Ihren Code aussieht:

10 int main() { 
    0x00000000004004d6 <+0>: mov $0x2710,%edx 
    0x00000000004004db <+5>: jmp 0x4004e7 <main+17> 

15   for(int j = 0; j < N; j++){ 
    0x00000000004004dd <+7>: sub $0x1,%eax 
    0x00000000004004e0 <+10>: jne 0x4004dd <main+7> 

14  for(int i = 0; i < N; i++) { 
    0x00000000004004e2 <+12>: sub $0x1,%edx 
    0x00000000004004e5 <+15>: je  0x4004ee <main+24> 

10 int main() { 
    0x00000000004004e7 <+17>: mov $0x2710,%eax 
    0x00000000004004ec <+22>: jmp 0x4004dd <main+7> 

16    arr[i * N + j] = 10.0; 
17   } 
18  } 
19  return 0; 
20 } 
    0x00000000004004ee <+24>: mov $0x0,%eax 
    0x00000000004004f3 <+29>: retq 

Wie Sie sehen, gibt es keine Assembler-Anweisungen für die Linie erzeugt arr[i * N + j] = 10.0;, so dass diejenigen, Cache-Misses Sie beobachten mit perf nicht verwandt sind.

Die Lösung ist ziemlich einfach. Einfach volatile auf den Zeiger Erklärung hinzuzufügen, Compiler die Zuordnungen zu erzeugen zwingen, d.h .:

volatile double *arr = malloc(sizeof(double) * N * N); 

der Demontage jetzt:

10 int main() { 
    0x0000000000400526 <+0>: sub $0x8,%rsp 

11  int N = 10000; 
12  volatile double *arr = malloc(sizeof(double) * N * N); 
    0x000000000040052a <+4>: mov $0x2faf0800,%edi 
    0x000000000040052f <+9>: callq 0x400410 <malloc@plt> 
    0x0000000000400534 <+14>: mov $0x0,%edx 

16    arr[i * N + j] = 10.0; 
    0x0000000000400539 <+19>: movsd 0xc7(%rip),%xmm0  # 0x400608 
    0x0000000000400541 <+27>: jmp 0x40055f <main+57> 
    0x0000000000400543 <+29>: movslq %edx,%rcx 
    0x0000000000400546 <+32>: lea (%rax,%rcx,8),%rcx 
    0x000000000040054a <+36>: movsd %xmm0,(%rcx) 
    0x000000000040054e <+40>: add $0x1,%edx 

15   for(int j = 0; j < N; j++){ 
    0x0000000000400551 <+43>: cmp %esi,%edx 
    0x0000000000400553 <+45>: jne 0x400543 <main+29> 
    0x0000000000400555 <+47>: mov %esi,%edx 

14  for(int i = 0; i < N; i++) { 
    0x0000000000400557 <+49>: cmp $0x5f5e100,%esi 
    0x000000000040055d <+55>: je  0x400567 <main+65> 
    0x000000000040055f <+57>: lea 0x2710(%rdx),%esi 
    0x0000000000400565 <+63>: jmp 0x400543 <main+29> 

17   } 
18  } 
19  return 0; 
20 } 
    0x0000000000400567 <+65>: mov $0x0,%eax 
    0x000000000040056c <+70>: add $0x8,%rsp 
    0x0000000000400570 <+74>: retq 

Und es gibt viel mehr Cache als auch vermisst.

Wenn Sie Ihren Test nur einmal ausführen, erhalten Sie möglicherweise sehr laute Ergebnisse. Sie sollten Ihre Messungen einige Male durchführen und einen Median nehmen. Es gibt Benchmark-Frameworks wie Google Benchmark, schauen Sie sich das bitte an.

Und der letzte. Beide Ihrer Muster, wie i * N + j und j * N + i sind leicht durch den CPU-Prefetcher zu erkennen, so dass das Cache-Miss-Verhältnis in beiden Fällen ziemlich ähnlich sein sollte ...