Warum beeinflusst die Reihenfolge der Schleifen die Leistung bei der Iteration über ein 2D-Array?

Question

Nachfolgend finden Sie zwei Programme, die fast identisch sind, mit der Ausnahme, dass ich die i y j Variablen um. Sie laufen beide in unterschiedlichen Zeitabständen. Kann mir jemand erklären, warum das passiert?

Version 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Version 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

Answer 1

Diese Zeile ist der Übeltäter:

x[j][i]=i+j;

Die zweite Version verwendet kontinuierlichen Speicher und wird daher wesentlich schneller sein.

Ich habe es mit

x[50000][50000];

und die Ausführungszeit beträgt 13 Sekunden für Version 1 und 0,6 Sekunden für Version 2.

Answer 2

_{Ich versuche, eine allgemeine Antwort zu geben.}

Denn i[y][x] ist eine Abkürzung für *(i + y*array_width + x) in C (probieren Sie das klassische int P[3]; 0[P] = 0xBEEF; ).

Bei der Iteration über y iterieren Sie über Abschnitte der Größe array_width * sizeof(array_element) . Wenn Sie das in Ihrer inneren Schleife haben, dann haben Sie array_width * array_height Iterationen über diese Chunks.

Wenn Sie die Reihenfolge umdrehen, haben Sie nur array_height Chunk-Iterationen, und zwischen jeder Chunk-Iteration haben Sie array_width Iterationen von nur sizeof(array_element) .

Während dies auf sehr alten x86-CPUs keine große Rolle spielte, führen die heutigen x86-Prozessoren eine Menge Prefetching und Caching von Daten durch. Sie produzieren wahrscheinlich viele Cache-Missgeschicke in Ihrer langsameren Iterationsreihenfolge.