row-major column-major 2D array

Hallo,

ich finde einfach keine quelle bzw. verstehe folgendes nicht:
Ich habe einen funktionsfähigen code der was mit Matrizen (2D-array) macht.
Meine Frage zielt auf die Performance bzw. cache-hits/misses ab. Ich würde es gern gänzlich von der Theorie verstehen:

Angenommen ich will die Matrix

0 1 2
3 4 5
6 7 8

speichern und tue dies grob so:

int** mtx = new int[3][3]; //ich weiß, ist c++ aber das spielt hier kein rolle

// do something

int* tmp = mtx[0];

tmp[0] = 0;
tmp[1] = 3;
tmp[2] = 6;
...

ist die matrix bzw. das 2 D array dann row-major abgespeichert so dass es cache-performant zugreifbar bleibt bei korrektem schleifenbau? Also im Prinzip habe ich doch einfach die transponierte matrix row-major-mässig abgespeihert und es sollte performant sein !?

danke

volkard

Auf die Theorie und die ganzen Fremdwörter kann ich nicht eingehen, die kenne ich nicht. Möglicherweise ist das hilfreich:

Hängt von den Schleifen ab, die Du darauf benutzen willst.

for(int y=0;y<3;++y)//ja, sehr oft ist die y-schleife die äußere
   for(int x=0;x<3;++x)
      tmp[y*3+x];//ok, index y*3+x rutscht linear von vorne nach hinten durch

for(int y=0;y<3;++y)
   for(int x=0;x<3;++x)
      tmp[x*3+y];//nicht fein, ok, bei 3 isses noch egal.

Ebenso bei zweidimensionalen Arrays macht.
Klar will ich wie in der Schule gewohnt erst X dann Y notieren.

int arr[MAXX][MAXY];
for(int y=0;y<3;++y)//ja, sehr oft ist die y-schleife die äußere
   for(int x=0;x<3;++x)
      arr[x][y];//aua

Darum

int arr[MAXY][MAXX];
for(int y=0;y<3;++y)//ja, sehr oft ist die y-schleife die äußere
   for(int x=0;x<3;++x)
      arr[y][x];//ok

SeppJ

int** mtx = new int[3][3]; //ich weiß, ist c++ aber das spielt hier kein rolle

Spielt wohl eine Rolle. Denn in C++ compiliert das nicht. Ein Array ist kein Pointer, ein Pointer ist kein Array. Und noch viel weniger ist ein 2D-Array ein Doppelzeiger, noch umgekehrt.
In C würde das (mit malloc) ja noch so gerade compilieren, wäre aber natürlich trotzdem falsch.

"Richtiger" wäre:

int (*mtx)[3] = new int[3][3];

Aber wieso new/malloc?
Richtig (egal welche Sprache) wäre:

int mtx[3][3];

Dann geht auch die Initialisierung viel einfacher:

int mtx[3][3] = {{0,1,2},{3,4,5},{6,7,8}};

Allgemein sind in C und C++ Arrays so gespeichert, dass die Zeilen im Speicher hintereinander stehen, du also in der innersten Schleife über die Spalten iterieren solltest:

#include <iostream>

int main()
{
  int mtx[3][3] = {{0,1,2},{3,4,5},{6,7,8}};

  // Der Reihe nach alle Speicherzellen ausgeben:
  int *it = mtx[0];
  for (int i = 0; i < 9; ++i)
    std::cout << *it++ << ' ';
  std::cout << '\n';

  // Korrekter Schleifenbau, damit die Speicherzellen der Reihe nach durchgegangen werden:
  for (int x = 0; x < 3; ++x)
    for (int y = 0; y < 3; ++y)
      std::cout << mtx[x][y] << ' ';
  std::cout << '\n';  
}

Ausgabe:

0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8

Das nennt man dann row-major, ja. Wenn es nicht row-major wäre, wäre es natürlich immer noch performant iterierbar, man würde dann eben die Schleifen genau anders herum aufbauen. In C und C++ gilt aber, dass der rechteste Index in der innersten Schleife iteriert werden sollte, und so weiter. Ob du diese Indizes dann x oder y nennst, ist deine Sache. Den ersten Index Zeile und den zweiten Spalte zu nennen, ist nur Konvention. Wenn du es andersrum benannt haben möchtest, dann benenn es anders herum. Aber achte da drauf, dass du trotzdem mit der innersten Schleife den rechtesten Index iterierst.

volkard

SeppJ schrieb:

Allgemein sind in C und C++ Arrays so gespeichert, dass die Zeilen im Speicher hintereinander stehen,

Jo. Sonnenklar bei Bildschirminhalten und dort

typedef char[80] Zeile;
typedef Zeile[25] Bildschirm

SeppJ schrieb:

du also in der innersten Schleife über die Spalten iterieren solltest:

Jo, aber nur, wenn man zwischendurch Spalten und Zeilen vertauscht, weil man x|y schreiben will.
Das ist recht verwirrend.

SeppJ

Kommt halt drauf an, was wir Zeilen und Spalten, was wir x und y nennen. Daher kommt die Verwirrung.

Gebe ich also nur die technische Antwort:

int mtx[3][3] = {{0,1,2},{3,4,5},{6,7,8}};

wird im Speicher wirklich zu

0|1|2|3|4|5|6|7|8

Benannt sind diese Zellen so:

mtx[0][0] | mtx[0][1] | mtx[0][2] | mtx[1][0] | ... | mtx[2][1] | mtx[2][2]

Und daraus lesen wir dann die optimale Schleifenkonstruktion ab:

Seppj schrieb:

achte da drauf, dass du mit der innersten Schleife den rechtesten Index iterierst.

Egal, ob man diesen Index nun Spalte, x, Zeile, y oder ganz anders nennt.