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

Ja, es hat etwas mit der Speicherzuweisung zu tun. Die erste Schleife indiziert die innere Dimension von img die sich jeweils nur über 3 Bytes erstreckt. Das ist innerhalb einer Speicherseite leicht (ich glaube, eine übliche Größe ist hier 4kB für eine Seite). Aber bei Ihrer zweiten Version ändert sich der Index der äußeren Dimension schnell. Das führt zu Lesevorgängen, die sich über einen viel größeren Bereich des Speichers erstrecken - nämlich sizeof (char[IMGX][3]) Bytes, das sind 24kB. Und bei jeder Änderung des inneren Index beginnen diese Sprünge erneut. Das betrifft verschiedene Seiten und ist wahrscheinlich etwas langsamer. Ich habe auch gehört, dass die CPU den Speicher vorausliest. Das wird der ersten Version zugute kommen, denn zum Zeitpunkt des Lesens sind die Daten wahrscheinlich schon im Cache. Ich kann mir vorstellen, dass die zweite Version davon nicht profitiert, weil sie diese großen Sprünge im Speicher hin und her macht.

Ich würde vermuten, dass der Unterschied nicht so groß ist, aber wenn der Algorithmus viele Male durchläuft, macht er sich irgendwann bemerkbar. Sie möchten wahrscheinlich den Artikel lesen Row-major Order auf wikipedia. Das ist das Schema, das verwendet wird, um mehrdimensionale Arrays in C zu speichern.