Frage zur Speicherreservierung von 2 dim. Arrays

c_d_e

Wenn ich für ein 2x3 Array den Speicher dynamisch Anfordern möchte, dann gibt es einmal die klassische Variante dies zu tun über einen doppelten pointer wie z.B int **p.
Nun gibt es noch folgende zweite Möglichkeit dies zu tun:

int (*p)[3];   
p = (int (*)[N])calloc(2*3,sizeof(int));

Was klar ist, ist das insgesamt 6 Arrayfelder des Typs int reserviert werden. Was ich mich jetzt aber Frage, es gibt ja noch ein Array welches 2 Felder hat, die jeweils die Adressen zu dem jeweiligen Array enthaelt, was wiederum 3 Felder hat. Man hat den Speicher für die 6 Felder reserviert, was ist aber mit dem Speicher für das 2 dim Array, welches die Adressen zu den einzelnen 3 dim Arrays enthaelt? Wie gesagt, wenn man soetwas über einen doppelten Pointer macht, dann ist es klar ersichtlich bzw. es wird jeder Schritt einzeln gemacht(Man wuerde erst den Speicher fuer das zweier Array frei geben und dann jeweils einzeln fuer die 3 dim Arrays)
Nur mich wundert, warum das gerade richtig sein soll.

DirkB

@c_d_e Den Speicher gibt es nicht.
Die Werte dafür berechnet der Compiler mit Zeigerarithmetik.

c_d_e

Die Werte fuer dieses Array liegen doch im Speicher oder was meinst du mit Zeigerarithmetik?
Ich meine der Compiler berechnet den freien Speicherbereich mit der Anfangsadresse von calloc(also der rückgabewert ist das erste Element des Arrays). Und in diesem Beispiel kann ich ja auf p mit p[0][1] = 1 z.B auf einzelne Elemente zugreifen. Was natürlich Arithmetik ist(ist ja das gleiche wie ((p+0)+1) = 1. Mir geht es jetzt aber um die Reservierung des Speicherbereichs. Er hat insgesamt 6 * 4 Bytes reserviert wovon man z.B wiederum 4 Bytes als einzelnes Feld betrachten kann. Und die ersten 34 Bytes als erstes Array der größe 3. Nur was ist mit dem Speicherbereich für p[0] und p[1], diese enthalten ja die Adressen zu den einzelnen Arrays also p[0] enthaelt ja die Adresse zu dem ersten Speicherbereich bzw. 3 Elementen großen int Array bzw. die erste Adresse der 64 Bytes, die reserviert worden sind. Und p[1] würde 3*4 im Adressbereich springen zu dem zweiten Array mit 3 Elementen. Nur die Frage ist jetzt, wo wurde mit dem Ausdruck

p = (int (*)[N])calloc(2*3,sizeof(int));

Speicherbereich für p[0] p[1] reserviert. Es wurde nur Speicher für 6*4 Bytes reserviert und nicht noch für die 2 Adressen.
Ich hoffe es ist verständlich, worauf ich hinaus möchte.

DirkB

@c_d_e Den Speicher für p[0] .... gibt es nicht.

Die Werte, die diese Pointer enthalten würden, werden berechnet.

HarteWare

Schonmal im Internet nachgelesen?
"C++ Using a 1D array as 2D array"
"C++ creating a 2D array on the heap"
"C++ memory layout of 2D array on the stack"
"..."

Tobiking2

@c_d_e sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Die Werte fuer dieses Array liegen doch im Speicher oder was meinst du mit Zeigerarithmetik?
Ich meine der Compiler berechnet den freien Speicherbereich mit der Anfangsadresse von calloc(also der rückgabewert ist das erste Element des Arrays). Und in diesem Beispiel kann ich ja auf p mit p[0][1] = 1 z.B auf einzelne Elemente zugreifen. Was natürlich Arithmetik ist(ist ja das gleiche wie ((p+0)+1) = 1.

Ein einfaches zweidimensionales Array ist kein Array aus Zeigern, sondern einfach ein zusammenhängender Speicherbereich den man über zwei Koordinaten adressieren kann.

p[a][b] entspricht *(p + a * Arraylänge + b). Damit lassen sich die Adressen alle direkt aus deinen Koordinaten berechnen. p[0] ist damit auch nichts anderes als p[0][0].

c_d_e

wenn ich jetzt auf das 2te Array zugreifen möchte, dann geht das natürlich über ((p+1)+0). Wenn ich *(p+1) schreibe, dann gibt er mir ja die Adresse aus, an welcher mein 2. Array mit 3 Integern beginnt. Und bei doppelter Dereferenzierung, also **(p+1) würde ich den zu dieser Adresse gehoerigen Wert bekommen. Woher weiß dann der Compiler, dass er bei *(p+1) 3 mal 4 Bytes hochspringen muss, wenn diese beiden Adresswerte nicht irgendwo gespeichert sind? Vor allem da sich bei:

int (*p)[3];
p = (int (*)[N])calloc(2*3,sizeof(int));

int ( p)[3] doppelt dereferenzieren kann, müssen bei dem Sprung von 34 Bytes, welchen er macht, wenn ich *(p+1) höchzaehle, die beiden Adresswerte also von *(p+0) und *(p+1) irgendwo hinterlegt sein. Und ich frage mich, ob diese nicht auch noch reserviert sein müssten? Oder ist es so das der Compiler speziell für diesen Pointer int (*p)[3] eben aus dem Wissen um den Typ Integer und der Speicherreservierung von 3 Bytes einfach alles selbst berechnet?

c_d_e

@HarteWare
wwenn ich jetzt auf das 2te Array zugreifen möchte, dann geht das natürlich über ((p+1)+0). Wenn ich *(p+1) schreibe, dann gibt er mir ja die Adresse aus, an welcher mein 2. Array mit 3 Integern beginnt. Und bei doppelter Dereferenzierung, also **(p+1) würde ich den zu dieser Adresse gehoerigen Wert bekommen. Woher weiß dann der Compiler, dass er bei *(p+1) 3 mal 4 Bytes hochspringen muss, wenn diese beiden Adresswerte nicht irgendwo gespeichert sind? Vor allem da sich bei:

int (*p)[3];
p = (int (*)[N])calloc(2*3,sizeof(int));

int ( p)[3] doppelt dereferenzieren kann, müssen bei dem Sprung von 34 Bytes, welchen er macht, wenn ich *(p+1) höchzaehle, die beiden Adresswerte also von *(p+0) und *(p+1) irgendwo hinterlegt sein. Und ich frage mich, ob diese nicht auch noch reserviert sein müssten? Oder ist es so das der Compiler speziell für diesen Pointer int (*p)[3] eben aus dem Wissen um den Typ Integer und der Speicherreservierung von 3 Bytes einfach alles selbst berechnet?

DirkB

@c_d_e sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Woher weiß dann der Compiler, dass er bei *(p+1) 3 mal 4 Bytes hochspringen muss, wenn diese beiden Adresswerte nicht irgendwo gespeichert sind?

Die 3 hast du bei der Definition vom Zeiger festgelegt, die 4 indirekt, da es ein Zeiger auf int ist.
Das ist Zeigerarithmetik.

Finnegan

@c_d_e sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Woher weiß dann der Compiler, dass er bei *(p+1) 3 mal 4 Bytes hochspringen muss, wenn diese beiden Adresswerte nicht irgendwo gespeichert sind?

Der Compiler weiss dass, weil der Typ des Objekts, auf das p zeigt int[3] ist, und sizeof(int[3]) = sizeof(int) * 3 = 12 gilt. Somit ist p + 1 für den Compiler die Adresse von p plus 12 Bytes. Die Typen und deren Größen ist etwas, das der Compiler immer kennt und auf dieser Basis auch den Code generiert. Das muss nirgendwo gespeichert werden, sondern diese Information wird vom Compiler in den Code "eingewoben", indem er an dieser Stelle z.B. einfach einen relativen Index 12 oder eine Addition um 12 in den erzeugten Code einbettet.

Noch eine Anmerkung: int (*)[3] hat nichts mit einem "2D-Array" zu tun, sondern ist lediglich ein "Zeiger auf ein Array der Länge 3". Die 2D-Array-Verwirrung kommt möglicherweise nur dadurch zustande, dass man annimmt, dass sich hinter dem int[3] noch weitere int[3] befinden, wie man bei einem char* davon ausgeht, dass sich hinter dem einen char auf den gezeigt wird, noch weitere chars befinden, und das Ding einen String repräsentiert. Das ist aber nur eine Konvention - für den Compiler ist das nur ein Zeiger auf einen einzigen char bzw. in deinem Fall auf ein einziges int[3]-Array. Genau wie bei einem char* auf die nachfolgenden chars greifst du also mit dem Subscript-Operator (variable[index]) z.B. mit p[1][0] auf das int[3]-Array zu, das im Speicher hinter demint[3]-Array liegt, auf das p zeigt. Ob sich dort wirklich ein solches befindet, kann der Compiler nicht unbedingt wissen, das hast du nur dadurch sichergestellt, indem du genügend Speicher reserviert hast. Aus dem Typ von p geht das jedenfalls nicht hervor. Dass sich p wie ein 2D-Array benutzen lässt ist hier lediglich dadurch möglich, dass C++ für *(p + i) die "bequemere Kurzschreibweise" p[i] erlaubt. p ist kein Array, sondern lediglich ein Pointer. p[0] und *p sind dagegen allerdings sehr wohl Arrays. Das ist einem allerdings oft nicht so bewusst, weil C++ meist implizit zwischen Pointern und Arrays konvertiert, so dass man beide für dasselbe halten könnte.

It0101

int N = 3, M = 2;
std::vector<int> Matrix( N * M, 0 );

oder

std::vector<std::vector<int>> Matrix;

?

Wenn ihr im C-Style rumspielen wollt, gibts da einen gesonderten Bereich für

*john 0

@It0101 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Wenn ihr im C-Style rumspielen wollt, gibts da einen gesonderten Bereich für

Weder das eine noch das andere ergibt für Matrizen einen Sinn. Wenn man Matrizen nutzen muss, nimmt man entweder eine existierende Matrizenklasse oder schreibt sie sich selbst. Aufpassen muss man falls man etwa die BLAS oder LAPACK nutzen will, dass das passende Format verwendet wird Row Major Order bzw Column Major Order, welches zur der BLAS bzw. LAPACK passt. Da diese beiden Bibliotheken von Fortran her kommen, ist die Adressierung der Spalten und Zeilen möglichweise unterschiedlich zu C/C++. Die leading dimension ist für die Interoperabilität mit Fortran notwendig, und in Bezug auf Cache Line Ausrichtung sinnvoll.

Beispiel für das Gerüst einer Matrixklasse

inline
size_t index_calc(const size_t i, const size_t j, const size_t ld) {
    return ((i*ld) + j);
}

class Matrix {
    double* p_;
    size_t  m_, n_;
public:
    Matrix(size_t m, size_t n) : m_(m), n_(n), p_(new double[n*m]) {
    }
    ~Matrix() {
        delete[] p_;
    }
    Matrix (const Matrix& m) = delete;
    Matrix& operator= (const Matrix &m) = delete;
    Matrix (Matrix &&m) = delete;
    double& operator() (const size_t i, const size_t j) { // Update operator () ergänzt, Matrix gelöscht, Rule 5 erfüllt
        return(p_)[index_calc(i,j,n_)];
    }
}

@john-0
Wenn du eine std::vector benutzt hättest, hättest du die 3/5/0 Regel nicht verletzt.

Jockelx

@john-0

Deine letzte Funktion soll wohl sowas wie 'at' oder der Funktionsoperator sein.

*john 0

@manni66 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

@john-0
Wenn du eine std::vector benutzt hättest, hättest du die 3/5/0 Regel nicht verletzt.

"Gerüst" nicht gelesen? Der Rest der 3/5/0 Regel sei dem Leser überlassen.

*john 0

@Jockelx
Ups, da fehlte operator()

@john-0 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

@manni66 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

@john-0
Wenn du eine std::vector benutzt hättest, hättest du die 3/5/0 Regel nicht verletzt.

"Gerüst" nicht gelesen? Der Rest der 3/5/0 Regel sei dem Leser überlassen.

Es gibt keinen Rest, wenn man nicht immer meint new/delete benutzen zu müssen.

Jockelx

@john-0 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Ups, da fehlte operator()

Und das 'Matrix' ist nach wie vor zu viel.
Wobei mir auch überhaupt nicht klar ist, was das Ziel dieses fehlerhaften "Gerüst" sein soll.

It0101

@john-0 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

@It0101 sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Wenn ihr im C-Style rumspielen wollt, gibts da einen gesonderten Bereich für

Weder das eine noch das andere ergibt für Matrizen einen Sinn

Weil?

*john 0

@Jockelx sagte in Frage zur Speicherreservierung von 2 dim. Arrays:

Wobei mir auch überhaupt nicht klar ist, was das Ziel dieses fehlerhaften "Gerüst" sein soll.

Reden wir über Matrizen und deren sinnvoller Nutzung in C++ oder geht es um möglichst schicken C++ Code? Der wesentliche Punkt bei Matrizen ist, dass man mit ihnen üblicherweise HPC macht und da keine der vorhanden Datenstrukturen in der STL wirklich für geeignet ist. Wenn man effizient Matrizrechnung machen muss, wird man auf so etwas wie die BLAS zurückgreifen müssen. Also ist ein ganz wesentlicher Aspekt, dass man kompatible Datenstrukturen verwendet. Denn von Hand eine Matrixmultiplikation zu schreiben, die mit der DGEMM z.B. MKL auch nur im Ansatz mithält, dürfte kaum möglich sein. Es gibt zwar Projekte, die die Funktionalität von BLAS und LAPACK rein als C++ Code umzusetzen versuchen, aber auch dann muss man sich mit den Datenstrukturen dieser Bibliotheken auseinandersetzen.

Die Frage ist daher wie speichert man sinnvoll die Daten einer Matrix in einem linearen Feld, so dass man darauf effizient zugreifen kann und diese Datenstruktur so gestaltet, dass sie z.B. von der vorhandenen BLAS genutzt werden kann. Wichtig dafür sind so Punkte wie Column Major vs. Row Major Order und Leading Dimension, weil das Dinge sind, die bei der BLAS nun einmal wichtig sind. Der ganze 0/3/5-Rule Kram ist zwar formalistisch wichtig, aber für das Problem Matrizen in C++ nur Beiwerk.

Zeiger auf Zeiger Strukturen oder noch schlimmer std::vector<std::vector<T>> sind zwar formalistisch korrekt, aber inkompatibel mit den BLAS Implementationen und nicht unbedingt die performanteste Lösung.