Erklärung des Codes einer Klasse mit überladenem Operator

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).