Speicheranordnung von C-Arrays

[Ineluki]

Diese Antwort lasse ich als richtig gelten. Magor ist dran.

Hier die genaue Aufloesung:

Prozessoren greifen nicht direkt auf den RAM zu, sondern haben idR zwei Cache Level, ueber die sie gehen. Das heisst, will man ein einzelnes Byte aus dem RAM holen, so wird zuerst ein grosser RAM Block (Eine sogenannte Cache Line) in den Second Level Cache geladen. Ein kleiner Ausschnitt daraus wird dann in den First Level Cache geladen, und das einzelne Byte von dort in ein Register der CPU. Brauch man nun das Byte neben dem zuvor geladenen Speicher, so befindet es sich bereits im Cache und kann schnell geladen werden. Das hat entscheidende Geschwindigkeitsvorteile, denn ein Zugriff auf den L1 Cache kann in ca 10 Prozessorcycles erfolgen, Zugriff auf L2 dauert bereits etwa 100 Zyklen und direkter Zugriff auf den RAM laesst die CPU auch schon mal gerne 1000 Zyklen warten.

Warum nun also die Verzoegerung auf dem Zweiprozessorsystem ? Ganz einfach: Jede der zwei CPUs hat mindestens einen einzigen L1 Cache. Im Fall das der eine gerade und der andere ungerade Indices bearbeitet passiert folgendes. Beide Prozessoren kopieren zu begin den selben Speicherinhalt in ihren Cache. Der erste Prozessor 1 (P1) liest nun seine Speicheraddresse und veraendert ihren Inhalt. P2 tut das selbe, muss aber feststellen, das P1 schon Daten in der selben Cache Line geaendert hat, also muss er die Cach Line aus dem Cache von P1 erst in den Cache von P2 kopieren, seinen Index laden und veraendern. Nun sieht aber P1 das die Cache Line veraendert wurde, usw ...

Im Falle des Einprozessorsystems und der falschen Schleifenanordnung ist es sehr aehnlich: nehmen wir folgenden einfachen C-Code:

Code:

int x,y;
for (x=0; x<width; ++x) {
  for (y=0; y<height; ++y) {
    A[x][y]+=1;
  }
}

C speichert mehrdimensionale Arrays zeilenweise ab. Das heisst, das im Speicher zuerst alle Elemente fuer y=0 stehen, danach die Elemente fuer y=1 usw. (In Fortran ist es z.B. genau andersrum). Dadurch das aber y in der inneren Schleife steht, muss jedes Mal eine andere Zeile in den Cache kopiert werden. Allein durch das Vertauschen der beiden Schleifen kann der Code bis zu acht mal schneller ausgefuehrt werden, da dann die Elemente jeder Zeile bereits im Cache stehen und auch verwendet werden koennen.

[Drakes]

Diese Antwort lasse ich als richtig gelten. Magor ist dran.

Hier die genaue Aufloesung:

Prozessoren greifen nicht direkt auf den RAM zu, sondern haben idR zwei Cache Level, ueber die sie gehen. Das heisst, will man ein einzelnes Byte aus dem RAM holen, so wird zuerst ein grosser RAM Block (Eine sogenannte Cache Line) in den Second Level Cache geladen. Ein kleiner Ausschnitt daraus wird dann in den First Level Cache geladen, und das einzelne Byte von dort in ein Register der CPU. Brauch man nun das Byte neben dem zuvor geladenen Speicher, so befindet es sich bereits im Cache und kann schnell geladen werden. Das hat entscheidende Geschwindigkeitsvorteile, denn ein Zugriff auf den L1 Cache kann in ca 10 Prozessorcycles erfolgen, Zugriff auf L2 dauert bereits etwa 100 Zyklen und direkter Zugriff auf den RAM laesst die CPU auch schon mal gerne 1000 Zyklen warten.

Warum nun also die Verzoegerung auf dem Zweiprozessorsystem ? Ganz einfach: Jede der zwei CPUs hat mindestens einen einzigen L1 Cache. Im Fall das der eine gerade und der andere ungerade Indices bearbeitet passiert folgendes. Beide Prozessoren kopieren zu begin den selben Speicherinhalt in ihren Cache. Der erste Prozessor 1 (P1) liest nun seine Speicheraddresse und veraendert ihren Inhalt. P2 tut das selbe, muss aber feststellen, das P1 schon Daten in der selben Cache Line geaendert hat, also muss er die Cach Line aus dem Cache von P1 erst in den Cache von P2 kopieren, seinen Index laden und veraendern. Nun sieht aber P1 das die Cache Line veraendert wurde, usw ...

Im Falle des Einprozessorsystems und der falschen Schleifenanordnung ist es sehr aehnlich: nehmen wir folgenden einfachen C-Code:

Code:

int x,y;
for (x=0; x<width; ++x) {
  for (y=0; y<height; ++y) {
    A[x][y]+=1;
  }
}

C speichert mehrdimensionale Arrays zeilenweise ab. Das heisst, das im Speicher zuerst alle Elemente fuer y=0 stehen, danach die Elemente fuer y=1 usw. (In Fortran ist es z.B. genau andersrum). Dadurch das aber y in der inneren Schleife steht, muss jedes Mal eine andere Zeile in den Cache kopiert werden. Allein durch das Vertauschen der beiden Schleifen kann der Code bis zu acht mal schneller ausgefuehrt werden, da dann die Elemente jeder Zeile bereits im Cache stehen und auch verwendet werden koennen.

...

Dein Beispiel verwirrt mich, denn die Erste Zahl sagt bei einer Matrix die Zeile/Reihe aus, also hier x, zudem wenn ich eine Mehrdimensionale Array erzeugen möchte, ist die erste Array ja eine Array von Zeigern auf Arrays, woraus folgt, dass durch die 2. Zahl das Element der Zeile festgelegt wird.

[dead_orc]

Dein Beispiel verwirrt mich, denn die Erste Zahl sagt bei einer Matrix die Zeile/Reihe aus, also hier x, zudem wenn ich eine Mehrdimensionale Array erzeugen möchte, ist die erste Array ja eine Array von Zeigern auf Arrays, woraus folgt, dass durch die 2. Zahl das Element der Zeile festgelegt wird.

...

Danke das du das sagst. Mir ging es bei dem Beispiel genau so, ich bin auch der Meinung, dass es so genau richtig ist. Immerhin kann ich ja ein Array auch anders schreiben:

Code:

&array[a][b] == *(array+a)+b

Zumindest wenn ich mich recht erinnere. Das würde aber bedeuten, dass array[0][0] und array[0][1] im Speicher direkt nebeneinander liegen.

[Cherry]

*(array+a*b)+b, oder? sonst würden ja array[2][3] und array[4][1] aufeinander liegen.

[dead_orc]

*(array+a*b)+b, oder? sonst würden ja array[2][3] und array[4][1] aufeinander liegen.

...

Habe ich auch erst gedacht, aber Experimente zeigen das Gegenteil.
Außerdem hast du anscheinend das *() um array+a übersehen, das dereferenziert einen Pointer. Unter den Speicheradressen array, array+1 etc. liegen also die Pointer auf die Zeilen, in *(array+a) liegen die Pointer auf den Inhalt der Zeilen. Zumindest habe ich das so verstanden. Etwas unsicher bin ich mir, ob da die Pointer zum Inhalt oder der Inhalt selber liegt oder ob das abhängig vom Typ ist, aber Pointer habe ich eh noch nie verstanden.

Code:

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

int main(int argc, char *argv[])
{
  unsigned int array[4][4];
  if(&array[1][3] == *(array+1)+3)
    puts("true!");
  return 0;
}

Wie du nach Kompilieren und Ausführen sehen wirst, gibt dieses kleine Progrämmchen "true!" aus, was zeigt, dass der Zusammenhang wohl so sein muss. ^^'

[DFYX]

Äh, dir ist bewusst, dass ein unsigned int array[4][4] kein Element array[1][4] hat, oder? Der höchste Index wäre 3, nicht 4.

[dead_orc]

Äh, dir ist bewusst, dass ein unsigned int array[4][4] kein Element array[1][4] hat, oder? Der höchste Index wäre 3, nicht 4.

...

Selfpwnage! xD
Nein, war mir irgendwie nicht bewusst, aber jetzt wo du es sagst...
Ändert aber nix. Ich hab den Source eben korrigiert, er "funktioniert" immer noch.

[Ineluki]

Soweit ist weiss ist ein int[a][b] eben KEIN Array von Pointern, sondern ein zusammenhaengender int[a*b] Datenblock im Speicher. Das das ganze als Array von Pointern gehandhabt werden kann ist afaik Compilermagic. Das heisst, da der Compiler weiss, wo welches Element liegt, kann er bei einer einfachen Dereferenzierung die eigentliche Addresse zurueck geben. Zusaetzlich dazu die Pointer zu speichern bzw die zur Addressierung zu benutzen waere nicht nur Platzverschwendung sondern auch ineffektiv, da ja bei jedem Zugriff erst der Pointer und dann erst die Daten gelesen wuerden, zwei zugriffe, die zudem noch die Ausnutzung der Cache-Vorteile verhindern wuerde. Ein echtes Array von Pointern verwendet man idR nur, wenn man mit sehr grossen Matrizen arbeiten muss, bei denen sich nicht gewaehrleisten laesst, das sie zusammenhaengend im Speicher stehen.

Was das Beispiel angeht, da ich hab die beiden schleifen bezueglich meiner Argumentation vertauscht und die schnellere Variante aufgeschrieben (ich war an dem Tag in Eile, weil ich auf dem Weg zu einer Hochzeit war). Ich hab die Bezeichnung X und Y ungluecklich gewaehlt und haette Z(eile) und S(palte) verwenden sollen. Bei einem Array (bzw einer Matrix) wird der Index ja als A[y][x] angesprochen, da die X-Achse ueber alle Spalten und die Y-Achse ueber alle Zeilen geht, was genau anders herum als in kartesischen Koordinatensystemen ueblich ist.

Ich hab das Beispiel aus der Erinnerung geschrieben und es eben genau richtig gemacht und damit natuerlich falsch bezueglich meiner Argumentation. Das aendert aber im Prinzip nichts an dem Zustand, das eine Vertauschung der beiden Schleifen einen erheblichen Geschwindigkeitsunterschied verursachen kann (ohne Optimierungsflags).

Tut mir leid, wenn ich damit fuer verwirrung gesorgt habe.

[Lukas]

Soweit ist weiss ist ein int[a][b] eben KEIN Array von Pointern, sondern ein zusammenhaengender int[a*b] Datenblock im Speicher.

...

Korrekt:

Code:

$ cat foo.c 
#include <stdio.h>
#include <string.h>

char *MEMORY = "\
\x01\x00\x00\x00\x02\x00\x00\x00\x03\x00\x00\x00\
\x04\x00\x00\x00\x05\x00\x00\x00\x06\x00\x00\x00\
\x07\x00\x00\x00\x08\x00\x00\x00\x09\x00\x00\x00\
\x0a\x00\x00\x00\x0b\x00\x00\x00\x0c\x00\x00\x00\
\x0d\x00\x00\x00\x0e\x00\x00\x00\x0f\x00\x00\x00";


int main(int argc, char *argv[])
{
    int i, j;
    int foo[5][3];
    
    memcpy(foo, MEMORY, 60);
    for(i = 0; i < 5; ++i)
    {
        for(j = 0; j < 3; ++j)
            printf("%02i ", foo[i][j]);
        printf("\n");
    }
    
    return 0;
}
$ gcc -Wall -o foo foo.c
$ ./foo 
01 02 03 
04 05 06 
07 08 09 
10 11 12 
13 14 15 
$

(geht jetzt von sizeof(int) == 4 und little endian aus)