Frage zur Speicherreservierung von 2 dim. Arrays

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.

hustbaer

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

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

Man muss aber auch nicht immer std::vector verwenden, speziell wenn man die Grösse schon kennt und nicht dynamisch ändern muss. In dem Fall dann lieber unique_ptr<T[]> -> 2 * sizeof(void*) weniger Overhead.

It0101

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

und nicht unbedingt die performanteste Lösung.

Das mit der Performance ist klar. Aber weder hat der Threadersteller das Wort "Matrix" im Eingangspost verwendet, noch fiel in irgendeiner Form die Anforderung "performant".

Für mich war das nur ein typischer Anfängerthread, wo Hilfe gefragt war und kein "ich bin Doktor der Mathematik und will die Berechnung mit Matrizen revolutionieren, damit ich den Nobelpreis bekomme"-Thread.

@john-0

Ein std::vector ist kompatibel mit C-Funtionen.

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

Der ganze 0/3/5-Rule Kram ist zwar formalistisch wichtig, aber für das Problem Matrizen in C++ nur Beiwerk.

Das ist kein Beiwerk! Deine Matrixklasse erzeugt durch Kopieren UB.

SeppJ

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

@john-0

Ein std::vector ist kompatibel mit C-Funtionen.

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

Der ganze 0/3/5-Rule Kram ist zwar formalistisch wichtig, aber für das Problem Matrizen in C++ nur Beiwerk.

Das ist kein Beiwerk! Deine Matrixklasse erzeugt durch Kopieren UB.

Volle Zustimmung. Die Rule of 0 besagt ja gerade, dass man dieses "Beiwerk" lieber dahin verschieben sollte, wo es hingehört. Wieso sollte eine Matrix Speicher verwalten? Das ist nicht ihre Aufgabe. Das hat gefälligst eine spezialisierte Speicherverwaltungsklasse zu übernehmen, die das dann auch richtig macht. Daher ist das wohl eine der wichtigsten Regeln in C++, kein Formalismus.

*john 0

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

Volle Zustimmung. Die Rule of 0 besagt ja gerade, dass man dieses "Beiwerk" lieber dahin verschieben sollte, wo es hingehört. Wieso sollte eine Matrix Speicher verwalten? Das ist nicht ihre Aufgabe. Das hat gefälligst eine spezialisierte Speicherverwaltungsklasse zu übernehmen, die das dann auch richtig macht. Daher ist das wohl eine der wichtigsten Regeln in C++, kein Formalismus.

Der wichtigste Punkt überhaupt ist es, dass man Code möglichst wiederverwenden sollte und nicht Dinge implementiert, die andere deutlich besser gelöst haben. Die Frage bei einer Matrix Klasse ist nun was da schwerer wiegt, die Implementation der Speicherverwaltung oder die effiziente Umsetzung der Implementation von so Dingen wie die Matrizenmultiplikation. Wenn man sich das Paper von Goto und Geijn anschaut dürfte klar sein, was mehr Arbeit ist. D.h. die Speicherverwaltung ist das leichtere Problem.

Der wichtigste Aspekt bei dem hier geschilderten Problem ist, wie man eine Matrix auf linearen Speicher abbildet. Also wie berechnet man aus zwei Indexvariablen den korrekten Index für den Speicherzugriff? Das ist bei einer Matrix das Wichtigste. Bei C++ muss man damit auch über die Row Major Order (die kommt man bei den statischen zweidimensionalen Felder zum Einsatz) sprechen, sprich wie sind die Elemente im linearen Speicher angeordnet.

Weshalb sollte man in einer Matrix Klasse den Speicher selbst verwalten und kein std::vector nutzen? std::vector hat so einige Eigenschaften, die nicht unbedingt ideal für eine Matrix sind. std::array wäre, wenn es denn auf dem Heap angelegt würde und deine dynamische Größe haben könnte, die bessere Speicherklasse. So ist Matrix Klasse ähnlich fundamental anzusehen wie std::vector und müsste eigentlich Teil der Standardlibrary sein. Wenn es denn da nicht das Problem gäbe, dass in den letzten Revisionen der Standardlibrary immer mehr die Verwendung von Memory Allocatoren zu einem Problem geworden wäre, da sie nicht konsequent genutzt werden.

*john 0

@manni66
Ich habe das Codebeispiel so angepasst, dass klar sein dürfte, dass das nur ein Gerüst ist in die Funktionalität implementiert werden muss. Akzeptabel?

Jockelx

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

std::vector hat so einige Eigenschaften, die nicht unbedingt ideal für eine Matrix sind.

Nenn doch mal konkret einige, dieser einigen nicht idealen Eigenschaften.

HarteWare

Kleine Anmerkung: Für Matrizen in C++ kann ich EigenLib empfehlen, hat auch schon SIMD Optimierungen mit drin, und ist recht umfangreich, und einfach einzubinden.