Erklärung des Codes einer Klasse mit überladenem Operator

Vielen Dank für die Antworten, das erklärt schon mal einiges!

Zum Thema vector... bei der von mir geposteten Quelle wurde da schon
einiges dazu diskutiert; das Hauptargument für diese Lösung vom Poster
war, dass die vorherige Lösung 20 Pointer erfordert hat und wohl etwas
langsamer war. Von vector war da gar nicht die Rede, sehe ich gerade...
und ich dachte schon einen vector zu benutzen würde mir am Ende
irgendwo Nachteile bringen :).
Ganz so wie 2D Matrizen verhalten sie sich aber dann doch nicht, wie ich
gelesen habe, die Werte sind irgendwie unabhängiger von einander und man
muss mit den Iteratoren aufpassen, aber dazu lese ich mich dann eben
etwas ein.

Danke nochmal!

314159265358979

vector hat nur Vorteile. Er nimmt dir das Verwalten des Speichers ab.

pumuckl

314159265358979 schrieb:

vector hat nur Vorteile. Er nimmt dir das Verwalten des Speichers ab.

Du schreibst "nur Vorteile", nennst aber nur einen. Einen Performance-vorteil hat dein 2D-Vector zum Beispiel nicht, weil bei Zugriffen die doppelte Indirektion über die Datenpointer in Kauf genommen wird, verglichen zu nur einer Indirektion in der vorliegenden Implementierung. Außerdem liegen beim 2D-vector im Ernstfall die verschiedenen Zeilen über den gesamten Heap verteilt, im vorliegenden Fall am Stück. Das macht vor allem dann was aus, wenn du im gesamten Bereich lesen/schreiben musst. Während der vorliegende Einzelblock vermutlich in ein oder zwei Pages in den Cache geschoben werden kann, musst du mit dem 2D-vector schlimmstenfalls so viele Seiten laden, wie du Zeilen hast. Mit solchen Aussagen wie "nur Vorteile" wäre ich also doch eher vorsichtig.

314159265358979

Er stellt sicher, dass operator = und matrix(const matrix&) richtig funktionieren, in C++0x auch die Move-Funktionen.

Aber ich sehe auch keinen Grund, die Größe der Matrix erst zur Laufzeit festzulegen. Da ist eine Matrix<X, Y, T> sinnvoller, man denke an die Matrizenmultiplikation. Dann kann man auch std::array verwenden. -> Speicher an einem Block.

Das ganze ist für eine Tilemap, die in ein Spiel geladen werden soll.
Dabei ist die Datei aus mehreren Long-Werten aufgebaut und die ersten
zwei Long-Werte sollen mir angeben, wie groß die Karte ist und anhand
davon wird dann die Matrix erstellt.
Das geht aber leider nicht, weil C++ bei Matrizen konstante Werte
verlangt. Deshalb muss ich sie zur Laufzeit festlegen.
Fraglich ist nur ob das bei einer vergleichsweisen so einfachen Anwendung
wirklich erhebliche Nachteile hätte.

krümelkacker

314159265358979 schrieb:

Diese Implementierung ist ziemlich schlecht.

Ja. Die Dreierregel wurde verletzt.

314159265358979 schrieb:

Ein einfacher std::vector<std::vector<T>> hätte es schon getan.

Naja, ein lineares Speicherlayout hat auch Vorteile. vector<vector<T>> ist da nicht immer die beste Idee.

'gibt auch noch boost::multi_array.

otze

314159265358979 schrieb:

Aber ich sehe auch keinen Grund, die Größe der Matrix erst zur Laufzeit festzulegen.

Ausser zum Beispiel, wenn man den Datensatz aus einer Datei ließt und nicht weiß, wie viele Werte ein Datensatz haben kann. Ausserhalb der Spieleprogrammierung ist das der Standardfall.

Da ist eine Matrix<X, Y, T> sinnvoller, man denke an die Matrizenmultiplikation.

Hab ich alles mal ausgemessen. Zur Compilezeit bekannte Grenzen helfen nur sehr selten, weil die Compiler eh vektorisierten Code erzeugen. Speicher am Stück hingegen ist super wichtig. Da hauste dir mal locker Faktor 3 mit rein wenn du vector<vector<T> > verwendest.

SeppJ

krümelkacker schrieb:

'gibt auch noch boost::multi_array.

Das ist übrigens auch übelst langsam, wenn wir hier schon von Performance sprechen. Ein guter alter 1D-vector mit einem kleinen Wrapper für 2D drumherum ist bei performancekritischen Sachen doch wohl noch immer mit unter den besten und gleichzeitig noch komfortabel.

314159265358979

otze schrieb:

314159265358979 schrieb:

Aber ich sehe auch keinen Grund, die Größe der Matrix erst zur Laufzeit festzulegen.

Ausser zum Beispiel, wenn man den Datensatz aus einer Datei ließt und nicht weiß, wie viele Werte ein Datensatz haben kann. Ausserhalb der Spieleprogrammierung ist das der Standardfall.

Ja, da hast du natürlich Recht. Hier habe ich zu beschänkt gedacht.

otze schrieb:

314159265358979 schrieb:

Da ist eine Matrix<X, Y, T> sinnvoller, man denke an die Matrizenmultiplikation.

Hab ich alles mal ausgemessen. Zur Compilezeit bekannte Grenzen helfen nur sehr selten, weil die Compiler eh vektorisierten Code erzeugen. Speicher am Stück hingegen ist super wichtig. Da hauste dir mal locker Faktor 3 mit rein wenn du vector<vector<T> > verwendest.

Ich meinte eher wegen der Fehlerüberprüfung zur Compilezeit.

camper

SeppJ schrieb:

krümelkacker schrieb:

'gibt auch noch boost::multi_array.

Das ist übrigens auch übelst langsam, wenn wir hier schon von Performance sprechen. Ein guter alter 1D-vector mit einem kleinen Wrapper für 2D drumherum ist bei performancekritischen Sachen doch wohl noch immer mit unter den besten und gleichzeitig noch komfortabel.

Hast du dafür Benchmarks?

SeppJ

camper schrieb:

SeppJ schrieb:

krümelkacker schrieb:

'gibt auch noch boost::multi_array.

Das ist übrigens auch übelst langsam, wenn wir hier schon von Performance sprechen. Ein guter alter 1D-vector mit einem kleinen Wrapper für 2D drumherum ist bei performancekritischen Sachen doch wohl noch immer mit unter den besten und gleichzeitig noch komfortabel.

Hast du dafür Benchmarks?

Jain. Ich habe das mal früher durch Profiling in einem meiner Projekte als Flaschenhals ausgemacht. Das war so arg langsam, dass es selbst in der zweitinnersten Schleifenebene die Performance des Gesamtprogramms um 50% gegenüber dem 1D-vector gedrückt hat. Was habe ich gemacht? Bei jedem Durchgang ein 2D-Array mit dynamsicher Größe erzeugt, in der innersten Schleife ein paar Werte da rein geschriebnen und hinterher alle Werte zusammen gezählt. Besonders letzteres war übelst lahm. Das acuumulate das ich jetzt drin habe ist so unendlich viel schneller, dass es im Profiler gar nicht sichtbar auftaucht, während vorher diese eigentlich triviale Funktion ein dicker Batzen der Gesamtlaufzeit war. Und ja: Ich habe die Makros gesetzt, die die Bereichsprüfung ausschalten.

Ich kann dir also keinen konkreten Benchmark geben, der zeigt wo und warum es versagt, sondern nur dieses Praxisbeispiel, welches du mir einfach glauben musst, da ich den Code hier nicht zeigen kann. Ein Benchmark wäre auch mal interessant, aber ist mir nicht wichtig genug, um einen zu schreiben. Ich bin jedenfalls nun glücklich mit meiner allgemeinen Wrapperklasse die ich auf alle 2D-Probleme anwenden kann. Ist zwar bei weitem nicht so flexibel und mächtig wie boost::multi_array, aber wenn dessen Vorteile auf Kosten der Laufzeit gehen, dann lehne ich dankend ab.

otze

314159265358979 schrieb:

Ich meinte eher wegen der Fehlerüberprüfung zur Compilezeit.

In der Theorie gut, in der Parix selten Sinnvoll. In den Szenarios in denen du deine Größen kennst, wirst du selten unterschiedlich große Matrizen haben. Dynamisch ist natürlich nicht so konfortabel, aber ich komme gut mit meinen SIZE_CHECK() Makros im Debug Modus klar. Müssen die Unit Tests halt gescheit sein

@camper

simpler Benchmark(eventuell noch Syntaxfehler drin, ich tipp das hier nur runter):

const unsigned int SizeX = 100;
const unsigned int SizeY = 256;
const unsigned int Runs = 100;

double array[SizeX][SizeY];//ground truth data
std::vector<std::vector<double> > arraySlow(SizeX,std::vector<double>(SizeY));
for(unsigned int x = 0; x!= SizeX;++x){
   for(unsigned int y = 0; y!= SizeY;++y){
       array[x][y]=x+y;//oder rand oder whatever
       arraySlow[x][y]=x+y;
   }
}

//version1:
double result = 0;
for(unsigned int r = 0; r != Runs; ++r){
    for(unsigned int x = 0; x!= SizeX;++x){
       for(unsigned int y = 0; y!= SizeY;++y){
           result+=array[x][y];
   }
}

//version2:
double result2 = 0;
for(unsigned int r = 0; r != Runs; ++r){
    for(unsigned int y = 0; y!= SizeY;++y){//nur vertauscht!
        for(unsigned int x = 0; x!= SizeX;++x){
           result2+=array[x][y];
        }
    }
}

//version3:
double result3 = 0;
for(unsigned int r = 0; r != Runs; ++r){
    for(unsigned int x = 0; x!= SizeX;++x){
       for(unsigned int y = 0; y!= SizeY;++y){
           result3+=arraySlow[x][y];//nur vector statt array
   }
}

Den Zeitmesscode musst du natürlich selbst einbauen. Version 2 sollte gegen Version 1 mit steigendem SizeY immer krasser abfallen. Version3 sollte immer schlechter oder maximal gleich gut wie Version2 sein. Version 2 und 3 kranken am selben Problem: Cache Misses

314159265358979

Und wie siehts aus mit new double[x*y] ?

otze

Äquivalent zu version 1 weil das Array dicht ist.

314159265358979

Musst aber die Allokation draufrechnen.

otze

kannste ja selbst machen. Ich kümemre mich nicht um konstante Terme wenn dagegen Algorithmen stehen die 10000 mal häufiger auf den Daten aufgerufen werden.

camper

otze schrieb:

Version 2 sollte gegen Version 1 mit steigendem SizeY immer krasser abfallen.

Belibt die spannende Frage, ob der Compiler damit besser umgehen kann, wenn fastmath erlaubt ist (loop interchange).