4. Datenstruktur für Matrizen

Datenstruktur für Matrizen

  • T

    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 🙂

    0
  • R

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

    0
  • R
    Mod

    rüdiger schrieb:

    Templates erlauben doch Spezialisierungen.

    nur codespezialisierung vom compiler, keine algorithmischen.

    0
  • T

    rapso schrieb:

    rüdiger schrieb:

    Templates erlauben doch Spezialisierungen.

    nur codespezialisierung vom compiler, keine algorithmischen.

    Wie meinst du das jetzt? Sag mal ein Beispiel.

    0
  • T

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

    0

  • 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 😉

    0
  • R
    Mod

    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 😉

    0
  • R

    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?

    0
  • T

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

    0

  • Muss ich dann bei der Spezialisierung die ganzen Methoden nochmal implementieren?

    ja

    Und was ist jetzt dieses geheimnisvolle Template-Loop-Unrolling?

    vielleicht meint er damit sowas:

    template<class T, class U, std::size_t d>
class dot_expand
{
public:
	static U eval(const T& a, const T& b)
	{
		return a[d-1]*b[d-1] + dot_expand<T, U, d-1>::eval(a, b);
	}
};

template<class T, class U>
class dot_expand<T, U, 1>
{
public:
	static U eval(const T& a, const T& b)
	{
		return a[0]*b[0];
	}
};

template<class T, std::size_t d>
inline const T dot(const vector<T, d>& a, const vector<T, d>& b)
{
	return dot_expand<vector<T, d>, T, d>::eval(a, b);
}

    und das coole daran ist, dass dieses dot product jetzt im prinzip nicht nur mit vektoren funktioniert, sondern mit jedem typ der einen [] operator unterstützt (also auch z.b. mit arrays). man müsste die sache allerdings ein bisschen anders angehen wie ich da oben (z.b. noch traits verwenden...).

    nur als bsp wie gut ein C++ compiler sowas optimieren kann:

    int main()
{

	vector<int, 3> a, b;

	a[0] = a[1] = a[2] = 2;
	b[0] = b[1] = b[2] = 2;

	int d = dot(a, b);

	return d;
}

    VS2005 macht aus dem folgenden code:

    00401000  mov         eax,0Ch 
00401005  ret

    ich denke dass das gleiche rauskäme wenn man das mit schleifen macht oder wenn man eine handgeschriebene vektor klasse verwendet (wenn die zu stark "optimiert" ist, dann wird der erzeugt code in dem fall vermutlich sogar schlechter sein, da der compiler nichtmehr so gut optimieren kann. VS2005 z.b. dreht afaik jegliche optimierungen ab sobald inline asm ins spiel kommt...)

    0
  • R
    Mod

    rüdiger schrieb:

    rapso schrieb:

    rüdiger schrieb:

    Templates erlauben doch Spezialisierungen.

    nur codespezialisierung vom compiler, keine algorithmischen.

    äh klar...
    wo ist nun das Problem?

    rapso schrieb:

    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.

    0
  • T

    @dot: lol, und das is also nicht frickelig? 😃
    Und wenn ich für die spezialisierten Klassen eh alles nochmal neu implementieren muss, kann ich es auch gleich ohne Template schreiben.
    Naja, ich werds auf alle Fälle weiterhin ohne Templates machen. 🙂

    0
  • T

    this->that schrieb:

    Und wenn ich für die spezialisierten Klassen eh alles nochmal neu implementieren muss, kann ich es auch gleich ohne Template schreiben.

    Nee, muss man nicht. Kann man mit Vererbung sehr leicht umgehen (kein virtual oder so, also bitte nicht "Laangsam!" schreien ;)).

    0
  • T

    Jo klar, ich werd meine simple Vec3 Klasse mittels Templates und Vererbung hinbiegen.
    Leute, ihr braucht mich nicht weiter in meiner Nicht-Template-Umsetzung bestärken. 😉

    0
  • T

    Es läuft auf den gleichen Maschinencode heraus, nur dass du in deinem Fall mehrere Klassen per Hand pflegen musst und mit dem Template nur eine Stelle hast, wo du Änderungen machen musst.

    0
  • P

    rapso schrieb:

    (bzw vielleicht 10 falls der anfaenger-template-gott zuschlaegt)

    Meinst du da was bestimmtest, oder soll das ne generelle Aussage sein. Man liest das dauernd, aber immer nicht, was den Code der Templates so aufblähen soll
    (Ich weis is Off Topic, aber die Matrix Sache scheint ja geklärt zu sein^^

    0

  • templates können den code aufblähen und vor allem anfänger tun sich oft schwer die gründe dafür auszumachen und zu eliminieren. ich denk das hat er gemeint.

    0
  • R
    Mod

    Pellaeon schrieb:

    rapso schrieb:

    (bzw vielleicht 10 falls der anfaenger-template-gott zuschlaegt)

    Meinst du da was bestimmtest, oder soll das ne generelle Aussage sein. Man liest das dauernd, aber immer nicht, was den Code der Templates so aufblähen soll
    (Ich weis is Off Topic, aber die Matrix Sache scheint ja geklärt zu sein^^

    geht um das resultierende binary. das liegt daran das alles unnuetzerweise immer geinlined wird. wenn du also etwas aufwendiges machst wie z.b. die inverse einer matrix44 (oder selbst ne multiplikation davon), dann wird das ueberall direkt in den code eingebracht, das macht die binary sehr viel groesser als noetig und kann am ende langsammere programme bedeuten. manche nutzen templates auch explizit um z.b. loop unrolling zu machen weil sie das mal irgendwo mitbekommen haben wie das geht, dann wird auch oft viel unperformanter code generiert z.b. wird die branch prediction eventuell viel effizienter genutzt falls man eine bedingung drinnen hat ohne unrolling.

    das tykische ist ja leider das viele meinen durch templates irgendwas schneller/besser gemacht zu haben obwohl es richtig gebenchmarkt dann das gegenteil ist. doch leider ist das oft etwas was ohne benchmarks am anfang vorweg genommen wird und als tatsache eklaert wird. normalerweise lernt jeder juniorprogrammer dass erst der code stehen muss und dann die optimierungen kommen, doch hinsichtlich templates scheint diese philosophie oft zu versagen.

    0
  • T

    rapso schrieb:

    das liegt daran das alles unnuetzerweise immer geinlined wird.

    Das ist schlichtweg falsch. Hier wird die "add"-Methode nicht geinlined (zumindest nicht zwangweise):

    #include <iostream>

template<typename T> class Adder
{
public:
	Adder(const T& v1, const T& v2)
		: v1(v1), v2(v2)
	{
	}

	T add() const;

private:
	T v1, v2;
};

template<typename T> T Adder<T>::add() const
{
	return v1 + v2;
}

int main()
{
	float v1, v2;
	std::cin >> v1 >> v2;
	Adder<float> adder(v1, v2);
	std::cout << adder.add();
	return 0;
}
    0
  • V

    TomasRiker schrieb:

    Vertexwahn schrieb:

    http://loop.servehttp.com/~vertexwahn/public_html_an_turing/MatrixHtml/_matrix_8h-source.html

    Benutzt du die auch für 4x4-Transformationsmatrizen?

    Nein - für 4x4 Matrizen habe ich eine spezielle Implementierung

    0
Anmelden zum Antworten