Datenstruktur für Matrizen

[TomasRiker]

Ich habe mir mal eine Template-Matrix-Klasse geschrieben, wo man die Größe und den Datentyp einstellen kann (z.B. 4x4 float oder 3x3 double), mit einigen Spezialisierungen für die üblichen Größen 3x3 und 4x4, damit es etwas schneller geht.

rapso schrieb:

bei sowas klappen sich mir immer die zaehnaegel hoch

Wäre denn

static_cast<float>(i == j)

besser?

[this-*gt*that]

Nein. Wozu bitte Schleifen? Sowas codet man direkt rein.
Ne Matrixklasse muss schnell sein, und sowas wie:
Vererbung, Schleifen, andre Methoden aufrufen, Speicher allokieren, prüfen ob der Index im Intervall is usw usw. gehört nicht in eine Matrix-Klasse.
Ehrlich gesagt halte ich auch Templates für Quatsch - die Algos sind ja eben NICHT Typabhänig und man braucht ja sowieso eh immer nur float Matrizen.

[TomasRiker]

this->that schrieb:

Nein. Wozu bitte Schleifen? Sowas codet man direkt rein.

Geht schlecht, wenn man vorher nicht weiß, wie groß die Matrix ist.

Ehrlich gesagt halte ich auch Templates für Quatsch - die Algos sind ja eben NICHT Typabhänig und man braucht ja sowieso eh immer nur float Matrizen.

Wieso ist das ein Argument gegen Templates, dass die Algorithmen nicht typenabhängig sind?
Und gerade in Sachen Physik reicht float oft nicht aus, da die Simulation dann schneller instabil wird und dir alles auseinanderfliegt.

Es ist doch wesentlich praktischer und weniger fehleranfällig zu schreiben:

typedef Matrix<3, 3, float> Matrix33f;
typedef Matrix<3, 3, double> Matrix44d;
typedef Matrix<4, 4, float> Matrix44f;
typedef Matrix<4, 4, double> Matrix44d;

als 4 Klassen zu schreiben, die alle mehr oder weniger gleich sind.
Natürlich muss man in den Templates dann Schleifen verwenden, aber die werden von guten Compilern aufgerollt (jedenfalls tut das Visual C++ 2005). Und wenn man ganz sicher gehen will, kann man immer noch partielle Spezialisierungen nehmen (z.B. für die Determinante von 3x3- und 4x4-Matrix).

[rüdiger]

this->that schrieb:

Nein. Wozu bitte Schleifen? Sowas codet man direkt rein.

Warum? Schleifen kann der Compiler doch selbst unrollen und so hat man wohl eher ne Chance, dass der daraus vielleicht sogar coolen SIMD-Code generiert. Wenn es wirklich etwas für die Performance ausmacht, dann kann man es ja immer noch händisch unrollen.

Ehrlich gesagt halte ich auch Templates für Quatsch - die Algos sind ja eben NICHT Typabhänig und man braucht ja sowieso eh immer nur float Matrizen.

für Spiele lasse ich das mal stehen. Aber warum sollten Templates Quatsch sein? Mach braucht doch idr. in der größe unterschiedliche Matrizen. Über Template-Spezialisierung kann ich ja auch für einzelne Fälle optimieren.

Templates haben sogar den Vorteil, dass der Compiler "toten" Code eliminieren darf und mit Templates besser optimiert. Bei einigen Embedded-Software Produzenten ist es daher sogar pflicht aus jeder Klasse ein Template zu machen!

@TomasRiker

float f = i == j;

ist doch perfekt legaler Code, der in 1.0f oder 0.0f resultiert.

[TomasRiker]

Danke, rüdiger, ich wäre davon ausgegangen, dass das eine Warnung gibt.
Aber jetzt wo ich drüber nachdenke, ist es eigentlich klar, da float ja der "größere" Typ ist.

[this-*gt*that]

Wir reden hier von Grafikprogrammierung - und das sind für mich vor allem jetzt mal Echtzeit-3D-Anwendungen wie Spiele. Ich habe jetzt schon einge 3D-Echtzeit-Anwendungen geschrieben, und habe noch NIE etwas andres als float 4x4 (ca 99,99% aller Matrizen), float 3x3, float 2x2 und float 4x3 Matrizen benötigt. Wenn man sich diese 3 oder 4 Matrixklassen per Hand schreibt, kann man wesentlich besser optimieren als bei einer Matriklasse für beliebige Größen (grauenhafte Vorstellung beim Anlegen einer Matrix Speicher im Heap alloziieren). Dass es Direct3D genauso macht, hat schon seine Gründe.

Und der (etwas gekünstelte Einwand, dass für irgendwelche Physikberechnungen (was eigentlich eh nicht reinpasst, da wir von Grafik sprechen) eventuell float nicht ausreicht, zieht nicht. Nur weil ich ich vllt ein, zwei mal eine spezialisierte Matrix für Physik brauche, muss ich das bei allen andren Matrizen immer mitschleifen? Kannste vielleicht mal ein Beispiel bringen, wo man ZWINGEND eine Matrix braucht, die etwas anderes als float benutzt?

[TomasRiker]

this->that schrieb:

Wenn man sich diese 3 oder 4 Matrixklassen per Hand schreibt, kann man wesentlich besser optimieren als bei einer Matriklasse für beliebige Größen (grauenhafte Vorstellung beim Anlegen einer Matrix Speicher im Heap alloziieren).

Die Spezialfälle sind auch mit partiellen Template-Spezialisierungen möglich (und habe ich auch verwendet). Und da wird nichts im Heap angelegt, sondern fein auf dem Stack. Stell dir das ungefähr so vor:

template<typename T, unsigned int M, unsigned int N> class Matrix
{
public:
    T element[M][N];
};

this->that schrieb:

Dass es Direct3D genauso macht, hat schon seine Gründe.

Schau dir mal die HLSL-Matrizen an:

Direct3D-Dokumentation schrieb:

The matrix type uses the angle brackets to specify the type, the number of rows, and the number of columns. This example creates a floating-point matrix, with two rows and two columns. Any of the scalar data types can be used.

Here is an example:

matrix <float, 2, 2> fMatrix = { 0.0f, 0.1, // row 1
                                 2.1f, 2.2f // row 2
                               };

this->that schrieb:

Und der (etwas gekünstelte Einwand, dass für irgendwelche Physikberechnungen (was eigentlich eh nicht reinpasst, da wir von Grafik sprechen) eventuell float nicht ausreicht, zieht nicht.

Daran ist nichts gekünstelt. Und niemand hat gesagt, dass es ausschließlich um Grafik geht.

this->that schrieb:

Nur weil ich ich vllt ein, zwei mal eine spezialisierte Matrix für Physik brauche, muss ich das bei allen andren Matrizen immer mitschleifen?

Da wird doch gar nichts "mitgeschleppt". Ich schreibe mir ein einziges Mal ein Template, und danach kann ich alles damit machen. Der Compiler generiert die Klassen doch für mich, und auch nur dann, wenn ich sie wirklich brauche. Wenn ich nur float und 4x4 brauche, dann generiert er die Klasse auch nur für float und 4x4.

this->that schrieb:

Kannste vielleicht mal ein Beispiel bringen, wo man ZWINGEND eine Matrix braucht, die etwas anderes als float benutzt?

Hab ich dir ja schon genannt: wenn mir die Genauigkeit von float nicht reicht

[this-*gt*that]

TomasRiker schrieb:

Die Spezialfälle sind auch mit partiellen Template-Spezialisierungen möglich (und habe ich auch verwendet). Und da wird nichts im Heap angelegt, sondern fein auf dem Stack. Stell dir das ungefähr so vor:

template<typename T, unsigned int M, unsigned int N> class Matrix
{
public:
    T element[M][N];
};

Das sieht schon besser aus. Wie gesagt, finde es dennoch immernoch überflüssig, da man eh immer nur 1 oder 2 Größen braucht und der Datentyp immer float ist.

Schau dir mal die HLSL-Matrizen an:

HLSL != D3D. Die D3D Matrizen sind in C++ geschrieben und somit eine gute Vergleichsmöglichkeit.
Und wenn du schon mal HLSL benutzt hast, dann wirste ja selber wissen, dass man in 99% float4x4 benutzt

Daran ist nichts gekünstelt. Und niemand hat gesagt, dass es ausschließlich um Grafik geht.

Blue5teel schrieb:

Hallo Leute,
mir ist im Kontext der Grafikprogrammierung mit C++ häufig aufgefallen

Wenn mir die Genauigkeit von float nicht reicht.

Was in der Praxis eher durch einen Algorithmenwechsel als durch saulangsame MegaBigDouble gelöst wird

[TomasRiker]

this->that schrieb:

Das sieht schon besser aus. Wie gesagt, finde es dennoch immernoch überflüssig, da man eh immer nur 1 oder 2 Größen braucht und der Datentyp immer float ist.

Meine Meinung dazu ist: sobald es schon 2 verschiedene Größen oder Datentypen sind, hat sich das Template bereits gelohnt. Ich habe diese Template-Klassen (Matrix und Vektor) jetzt schon in zwei Projekten benutzt und habe es nicht bereut. Es konnte mir egal sein, dass ich Farben teilweise als 3D-Byte-Vektor (0 bis 255) und teilweise als 4D-float-Vektor (0 bis 1 und Alphakanal) akzeptieren musste. Früher hätte ich mich dann geärgert, dass ich wieder eine neue Vektorklasse hätte schreiben müssen oder hätte irgendwie drumherum programmiert, und mit dem Template ist es eine einzige Zeile.

Und wenn du schon mal HLSL benutzt hast, dann wirste ja selber wissen, dass man in 99% float4x4 benutzt

Mag sein, oft aber auch float4x3, oder wenn man Texturkoordinaten transformieren möchte auch mal float3x3 oder float3x2 ...

Blue5teel schrieb:

Hallo Leute,
mir ist im Kontext der Grafikprogrammierung mit C++ häufig aufgefallen

Da hätte ich mal besser lesen sollen ...

Was in der Praxis eher durch einen Algorithmenwechsel als durch saulangsame MegaBigDouble gelöst wird

Wohl eher nicht - was willst du z.B. bei einer Koordinatentransformation an anderen Algorithmen anwenden? Außerdem ist double wahrscheinlich wesentlich schneller als du denkst. Der Prozessor rechnet intern sowieso mit 80 Bits Genauigkeit und "rundet" dann am Ende auf 32 Bits (float) oder 64 Bits (double). Vom Rechnen her sollte double also nicht langsamer als float sein, sondern braucht nur mehr Speicher(bandbreite). Der Geschwindigkeitsnachteil sollte sich in Grenzen halten, solange man nicht sowas wie Signalverarbeitung macht.

[this-*gt*that]

Mir ist einfach zum einen diese Aussage "der Compiler sollte die Schleifen unrollen" zu unsicher. Kann ich mir sicher sein, dass er das immer macht? Da schreib ichs lieber selber aufgerollt rein und kann mir sicher sein.
Desweiteren unterscheiden sich Vektoren/Matrizen unterschiedlicher länge durchaus. So haben meine Vec3 z.B. eine statische Methode Cross, die in Vec4 und Vec2 keinen Sinn machen. Ferner hat meine Matrix-Klasse (meine 4x4 Matrix heißt einfach Matrix, da ich sowieso nie was andres brauche) statische Hilfsmethoden wie CreateLookAtLH etc, die in einer 2x2 Matrix auch keinen Sinn macht. Klar könnte man das auch durch globale Funktionen lösen (bei mir nicht, da ich C# verwende ), aber ich finde es passt einfach in die Klassen und ist schönere OOP.

Klar gibt es mit floats derbe Rundungsfehler, nur kann man oft diese Ungenauigkeiten zugunsten der Geschwindigkeit in Kauf nehmen.
Ich bin mir da nicht 100%ig sicher, aber glaube mal gelesen zu haben, dass nahezu alle GPU Register mit Quad-Floats arbeiten und somit floats am schnellsten verarbeiten können - andere Datentypen werden lediglich über floats simuliert.

[rapso]

ich habe viele klassen statt templates weil sie spezialisiert sind. (btw. 99% der objekte sind bei mir matrix34), ansonsten waere es eh egal ob 33 22 weil man alle berechnungen mit 44 durchfuehren koennte. aber manche algorithmen sind nunmal besser spezialisierbar.

@tomas... als ist besser als if(true)

[TomasRiker]

this->that schrieb:

Mir ist einfach zum einen diese Aussage "der Compiler sollte die Schleifen unrollen" zu unsicher. Kann ich mir sicher sein, dass er das immer macht? Da schreib ichs lieber selber aufgerollt rein und kann mir sicher sein.

Auch das kannst du mit dem Template machen
Aber bei sowas kann man m.M.n. schon auf den Compiler vertrauen. Er weiß ja schon zur Kompilierzeit, wie oft die Schleife durchlaufen wird, und kann dann entscheiden, ob sich das Aufrollen lohnt.

Desweiteren unterscheiden sich Vektoren/Matrizen unterschiedlicher länge durchaus. So haben meine Vec3 z.B. eine statische Methode Cross, die in Vec4 und Vec2 keinen Sinn machen.

Auch das geht beim Template, habe ich auch eingebaut. Vector<T, 3> hat eine statische cross-Methode, die anderen nicht. Dafür hat Vector<T, 2> eine perp-Methode. Es hat zwar ein paar Tricks gebraucht, um das hinzukriegen, aber es klappt
Was z.B. auch sehr nett ist: wenn ich zwei Matrizen multipliziere und das von der Anzahl der Zeilen und Spalten her nicht passt, gibt's direkt zur Kompilierzeit einen Fehler (es gibt ja da die Bedingung mit der Anzahl der Zeilen und Spalten). Wenn es passt, kriege ich automatisch eine Matrix mit der richtigen Größe zurück. Ähnliches gilt beim Transformieren eines Vektors mit einer Matrix.

Klar gibt es mit floats derbe Rundungsfehler, nur kann man oft diese Ungenauigkeiten zugunsten der Geschwindigkeit in Kauf nehmen.
Ich bin mir da nicht 100%ig sicher, aber glaube mal gelesen zu haben, dass nahezu alle GPU Register mit Quad-Floats arbeiten und somit floats am schnellsten verarbeiten können - andere Datentypen werden lediglich über floats simuliert.

Jo, von den GPUs rede ich ja auch gar nicht - die können soweit ich weiß überhaupt keine 64-Bit-Floats und rechnen nur mit 32 oder 16 Bits (ältere sogar nur mit Fixed).

Naja, die Diskussion bringt wohl nicht mehr viel. Ich werde bei den Templates bleiben und ihr bei euren Einzelklassen. Trotzdem gut, dass man mal drüber geredet hat

[rüdiger]

Templates erlauben doch Spezialisierungen. Loop-Unroll mittels Templates ist auch prima möglich. Jedes mal eine eigene Klasse zu bauen, wenn man mal eine andere Matrix braucht, halte ich eher für gefährlich.

Wie gesagt der Compiler kann bei Templates sogar eher toten Code wegoptimieren, was er bei euren Einzelklassen nicht darf. Ich finde überhaupt sind einige eurer Argumente wohl eher auf Angst oder Vorurteilen gegenüber Templates begründet...

Mir ist einfach zum einen diese Aussage "der Compiler sollte die Schleifen unrollen" zu unsicher. Kann ich mir sicher sein, dass er das immer macht? Da schreib ichs lieber selber aufgerollt rein und kann mir sicher sein.

Vielleicht kann es auch mal Sinn haben das nicht unzurollen oder der Compiler würde deine Funktion erst inlinen und unrollen, aber da dein ungerollter Code zu groß ist macht er erst gar kein inlining etc.

(bei mir nicht, da ich C# verwende )

lol, da ist dein Optimierungsansatz doch eh absolut anders als der eines C++-Programmierers. Du kannst dir im Grunde bei nichts sicher sein was da für Code rauskommt...

[rapso]

rüdiger schrieb:

Templates erlauben doch Spezialisierungen.

nur codespezialisierung vom compiler, keine algorithmischen.

[TomasRiker]

rapso schrieb:

rüdiger schrieb:

Templates erlauben doch Spezialisierungen.

nur codespezialisierung vom compiler, keine algorithmischen.

Wie meinst du das jetzt? Sag mal ein Beispiel.

[this-*gt*that]

Ok ich schreibs jetzt nochmal (aber zum letzen Mal, dachte wir wären eigentlich durch;) ):
Ich BRAUCHE keine 2x7, 3x11 oder was auch immer Matrizen. Ich brauche lediglich 2, 3 Matrizen, die teilweise unterschiedliche Methoden haben und in denen ich unterschiedlich optimiere.
Ich BRAUCHE keine char, short, oder void* Matrizen. Ich brauche NUR FLOAT Matrizen. Und sollte ich dann in 4 Jahren doch mal eine mit double brauchen (was unwahrscheinlich ist, da in Spielen die Genauigkeit nicht so wichtig ist - lieber 0.03 Grad-Abweichung, aber dafür 80fps ), kann ich sie dann ja schnell schreiben.

Loop-Unroll mittels Templates sagt mir nichts. Aber genauso wie TomasRikers' Methode spezifische Methoden für bestimmte Dimensionen in eine Template-Klasse einzubauen, hört es sich frickelig an.
Was meinst du mit totem Code wegoptimieren? Einfach niemals aufgerufene Methoden nicht in das Object File packen? Falls es das is: so einen Fall habe ich eh nicht und einen Geschwindigkeitsvorteil würde es auch net bringen.

Zu C#: Ich benutze jetzt C#, hab davor aber auch C++ benutzt; hab also durchaus schon mal in C++ eine Matrix geschrieben. (Aber wieso bei C# unklar is welcher Code entsteht, leuchtet mir nicht ganz ein...).

[dot]

this->that schrieb:

Ok ich schreibs jetzt nochmal (aber zum letzen Mal, dachte wir wären eigentlich durch;) ):
Ich BRAUCHE keine 2x7, 3x11 oder was auch immer Matrizen. Ich brauche lediglich 2, 3 Matrizen, die teilweise unterschiedliche Methoden haben und in denen ich unterschiedlich optimiere.
Ich BRAUCHE keine char, short, oder void* Matrizen. Ich brauche NUR FLOAT Matrizen. Und sollte ich dann in 4 Jahren doch mal eine mit double brauchen (was unwahrscheinlich ist, da in Spielen die Genauigkeit nicht so wichtig ist - lieber 0.03 Grad-Abweichung, aber dafür 80fps ), kann ich sie dann ja schnell schreiben.

gut, was genau spricht jetzt gegen templates!?
und wer sagt eigentlich das double so langsam ist?
warum sollte man templates nicht genauso per hand mit sse optimieren können wie normale klassen?

this->that schrieb:

Loop-Unroll mittels Templates sagt mir nichts. Aber genauso wie TomasRikers' Methode spezifische Methoden für bestimmte Dimensionen in eine Template-Klasse einzubauen, hört es sich frickelig an.

es ist aber das genaue gegenteil von frickelig

[rapso]

TomasRiker schrieb:

rapso schrieb:

rüdiger schrieb:

Templates erlauben doch Spezialisierungen.

nur codespezialisierung vom compiler, keine algorithmischen.

Wie meinst du das jetzt? Sag mal ein Beispiel.

mal am einfachen beispiel, du machst ne klasse fuer polynome, machst du eine spezialisierte klasse fuer geraden und parabeln, dann kannst du ohne naehrung mit simplen berechnungen nullstellen finden, du kannst auch beim schneiden mit diesen spezialfaellen optimierten code nutzen... (nateurlich ist es moeglich alles auch in eine templateklasse zu packen und zig abfragen fuer sonderfaelle einzubauen oder sonstige spezialisierungen, nur ist damit eben spezialcode vorhanden und kein template-generic-code.

anderes beispiel, loop unrolling oder inlining, ein compiler kann fuer eine architektur optimiert unrollen/inlinen. wenn du ahnung hast, kannst du bei spezialisierten klassen es auch selbst machen. jemand mit 0 plan denkt je mehr er unrollt/inlined, desto schneller muss es sein und zerschiesst jeglichen codecache und profiling moeglichkeit. und selbst wenn er das mal in einem kleinen programm von 4kb testet das komplett in den cache passt, hat das 0 aussage fuer ein 2MB grosses program (bzw vielleicht 10 falls der anfaenger-template-gott zuschlaegt).

edit: das ist kein angriff gegen dich tomas, ich denke du weisst was du tust

[rüdiger]

rapso schrieb:

rüdiger schrieb:

Templates erlauben doch Spezialisierungen.

nur codespezialisierung vom compiler, keine algorithmischen.

äh klar

template<std::size_t N, typename T=float>
struct Foo {
 T data[N];
};

template<typename T>
struct Foo<4, T> {
 // Spezialisierung für N = 4
};

template<std::size_t N, typename T>
void crazy_operation(Foo<N, T> const &param);

template<typename T>
void crazy_operation(Foo<3, T> const &param);

wo ist nun das Problem?

[this-*gt*that]

Muss ich dann bei der Spezialisierung die ganzen Methoden nochmal implementieren? Und was ist jetzt dieses geheimnisvolle Template-Loop-Unrolling?