4. Datenstruktur für Matrizen

Datenstruktur für Matrizen

  • 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
  • R
    Mod

    TomasRiker schrieb:

    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;
}

    😮
    ich nehm das einfach mal als sarkasmus hin.

    0
  • T

    rapso schrieb:

    😮
    ich nehm das einfach mal als sarkasmus hin.

    Was soll denn dieser Kommentar? Natürlich ist der Code sinnlos. Er soll dir nur zeigen, dass Template-Methoden nicht zwangsweise geinlined werden, wie du vorhin behauptet hast.
    Wenn du mir nicht glaubst - nimm den Code, kompilier ihn und schau dir den Assembler-Code an. "add" wird durch ein "call" aufgerufen, also wird nicht geinlined.
    Wenn du die Methoden direkt in der Klasse deklarierst, ist das natürlich was Anderes - genau wie bei Nicht-Template-Klassen.

    0
  • R
    Mod 

    00401022  fld         dword ptr [v2] 
00401025  fadd        dword ptr [v1] 
00401028  add         esp,8 
0040102B  fstp        qword ptr [esp]

    btw. default projekt im releasebuild mit VC++

    0
  • T

    Klar, so kleine Methoden inlined er bereitwillig (würde er auch bei einer Nicht-Template-Klasse tun, hab ich grade getestet).
    Nimm mal:

    Inline function expansion:
    Only __inline (/Ob1)

    0
  • R
    Mod

    und du nimm mal die optionen die man bei einem spiel normalerweise verwendet (vermutlich inline all suitable, 03 usw.) und zeig mir ein beispiel das in der praxis trotz template nicht inlined wird in deiner matrix.

    0
  • T

    Inline all suitable, Full Optimization

    template<typename T> T Adder<T>::aBitMoreComplicatedMethod() const
{
	T x = v1;
	for(int i = 0; i < 16; i++)
	{
		x += (v2 - x) * v1;
	}

	return x;
}

    wird nicht geinlined,

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

    hingegen schon.
    Ist zwar jetzt nicht aus meinem Matrix-Template, aber diese Funktion ist immer noch simpler als z.B. eine Invertierung.

    Warum sollte der Compiler auch einen Unterschied machen?
    Ein Template ist doch einfach nur eine Vorlage. Daraus erzeugt er eine Klasse und die kompiliert er so wie eine normale Klasse auch.

    0
Anmelden zum Antworten