Algorithmusvergleich in C, was ist der Unterschied?

Question

#define IMGX 8192
#define IMGY 8192
int red_freq[256];
char img[IMGY][IMGX][3];

main(){ 

int i, j;
  long long total;
  long long redness;

  for (i = 0; i < 256; i++) 
    red_freq[i] = 0;

  for (i = 0; i < IMGY; i++) 
    for (j = 0; j < IMGX; j++) 
      red_freq[img[i][j][0]] += 1;

  total = 0;
  for (i = 0; i < 256; i++) 
    total += (long long)i * (long long)red_freq[i];

  redness = (total + (IMGX*IMGY/2))/(IMGX*IMGY); 

was ist der Unterschied, wenn Sie die zweite for-Schleife durch

for (j = 0; j < IMGX; j++) 
    for (i = 0; i < IMGY; i++) 
      red_freq[img[i][j][0]] += 1;

Alles andere bleibt gleich, und warum ist der erste Algorithmus schneller als der zweite Algorithmus?

Hat es etwas mit der Speicherzuweisung zu tun?

Answer 1

Die erste Version ändert den Speicher nacheinander, so dass der Prozessor-Cache optimal genutzt wird. Die zweite Version verwendet einen Wert aus jeder geladenen Cache-Zeile, so dass der Cache nicht optimal genutzt wird.

Es ist wichtig zu verstehen, dass der Cache in Zeilen unterteilt ist, von denen jede viele Werte in der Gesamtstruktur enthalten wird.

Die erste Version könnte auch vom Compiler so optimiert werden, dass mehr clevere Befehle (SIMD-Befehle) verwendet werden, was noch schneller wäre.

Answer 2

Der Grund dafür ist, dass die erste Version den Speicher in der Reihenfolge durchläuft, in der er physisch angelegt ist, während die zweite Version im Speicher von einer Spalte im Array zur nächsten springt. Dies führt zu Cache Thrashing und beeinträchtigt die optimale Leistung der CPU, die dann viel Zeit damit verbringen muss, darauf zu warten, dass der Cache immer wieder aufgefrischt wird.

Answer 3

Das liegt daran, dass große moderne Prozessorarchitekturen (wie die in einem PC) massiv darauf optimiert sind, mit Speicher zu arbeiten, der (adressbezogen) "in der Nähe" des Speichers liegt, auf den sie kürzlich zugegriffen haben. Der tatsächliche physische Speicherzugriff ist viel, viel langsamer als die CPU theoretisch ausführen kann, so dass alles, was dem Prozess hilft, seinen Zugriff auf die effizienteste Art und Weise durchzuführen, zur Leistung beiträgt.

Es ist so gut wie unmöglich, mehr als das zu verallgemeinern, aber die "Lokalität des Bezugs" ist ein gutes Ziel, das man anstreben sollte.

Answer 4

Aufgrund der Anordnung des Speichers behält die erste Version die Datenlokalität bei und verursacht daher weniger Cache-Misses.

Answer 5

Die Speicherzuweisung erfolgt nur einmal und zwar am Anfang, kann also nicht der Grund sein. In beiden Fällen wird die Speicheradresse wie folgt berechnet

(i * (IMGY * IMGX)) + (j * IMGX) + 0

Bei dem ersten Algorithmus

(i * (IMGY * IMGX)) gets calculates 8192 times
(j * IMGX) gets calculated 8192 * 8192 times

Bei dem zweiten Algorithmus

(i * (IMGY * IMGX)) gets calculates 8192 * 8192 times
(j * IMGX) gets calculated 8192 times

Seit

(i * (IMGY * IMGX)) 

zwei Multiplikationen erfordert, braucht es mehr Zeit. Das ist der Grund