4. Datenstruktur für Matrizen

Datenstruktur für Matrizen


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

    TomasRiker schrieb:

    Inline all suitable, Full Optimization
    ...
    wird nicht geinlined,

    dann machst du etwas bei deinen settings falsch

    int main()
{
00401930  sub         esp,8 
00401933  push        esi  
	float v1, v2;
	scanf("a %f\n",&v1);
00401934  mov         esi,dword ptr [__imp__scanf (4020B0h)] 
0040193A  lea         eax,[esp+4] 
0040193E  push        eax  
0040193F  push        offset type_info::`vftable'+2Ch (40212Ch) 
00401944  call        esi  
	scanf("b %f\n",&v2);
00401946  lea         ecx,[esp+10h] 
0040194A  push        ecx  
0040194B  push        offset type_info::`vftable'+34h (402134h) 
00401950  call        esi  
	Adder<float> adder(v1, v2);
 	printf("%f\n",adder.add());
00401952  movss       xmm0,dword ptr [esp+14h] 
00401958  movss       xmm1,dword ptr [esp+18h] 
0040195E  add         esp,10h 
00401961  movaps      xmm3,xmm0 
00401964  mov         eax,2 
00401969  pop         esi  
0040196A  lea         ebx,[ebx] 
00401970  sub         eax,1 
00401973  movaps      xmm2,xmm1 
00401976  subss       xmm2,xmm3 
0040197A  mulss       xmm2,xmm0 
0040197E  addss       xmm2,xmm3 
00401982  movaps      xmm3,xmm1 
00401985  subss       xmm3,xmm2 
00401989  mulss       xmm3,xmm0 
0040198D  addss       xmm3,xmm2 
00401991  movaps      xmm2,xmm1 
00401994  subss       xmm2,xmm3 
00401998  mulss       xmm2,xmm0 
0040199C  addss       xmm2,xmm3 
004019A0  movaps      xmm3,xmm1 
004019A3  subss       xmm3,xmm2 
004019A7  mulss       xmm3,xmm0 
004019AB  addss       xmm3,xmm2 
004019AF  movaps      xmm2,xmm1 
004019B2  subss       xmm2,xmm3 
004019B6  mulss       xmm2,xmm0 
004019BA  addss       xmm2,xmm3 
004019BE  movaps      xmm3,xmm1 
004019C1  subss       xmm3,xmm2 
004019C5  mulss       xmm3,xmm0 
004019C9  addss       xmm3,xmm2 
004019CD  movaps      xmm2,xmm1 
004019D0  subss       xmm2,xmm3 
004019D4  mulss       xmm2,xmm0 
004019D8  addss       xmm2,xmm3 
004019DC  movaps      xmm3,xmm1 
004019DF  subss       xmm3,xmm2 
004019E3  mulss       xmm3,xmm0 
004019E7  addss       xmm3,xmm2 
004019EB  jne         main+40h (401970h) 
004019ED  sub         esp,8 
004019F0  cvtss2sd    xmm0,xmm3 
004019F4  movsd       mmword ptr [esp],xmm0 
004019F9  push        offset type_info::`vftable'+3Ch (40213Ch) 
004019FE  call        dword ptr [__imp__printf (4020A8h)] 
	return 0;
00401A04  xor         eax,eax 
}

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

    Warum sollte der Compiler auch einen Unterschied machen?

    tja, wieso macht er das? steck doch mal deine templates in ein header in nutze sie testweise paar mal... geht... und mach das gleiche nun ohne templates... ploetzlich gibt es mehrere definitionen der selben funktion und es geht nicht mehr... templates werden lokal in jedes .o (oder .bin bei vc++) neu erstellt, das kannst du nicht verhindern, der code wird zwangsweise groesser und bei normalen optimierungsoptionen wird das auch immer in-place gemacht.

    Ein Template ist doch einfach nur eine Vorlage. Daraus erzeugt er eine Klasse und die kompiliert er so wie eine normale Klasse auch.

    nicht ganz, ein template ist quasi annonym (der linker muss nichts von dessen existenz wissen) und wird von vielen compilern einfach in den code gepatcht. selbst ewig lange funktionen stopft dir der compiler in-place rein und wenn du die 100 mal machst, dann packt er dir die auch so oft rein und manche compiler hoeren dann nie auf zu compilieren (woertlich) statt einfach nen call zu machen was in jeglicher hinsicht besser waere.

    0
  • T

    ... und nun ersetz mal die Template-Klasse durch eine normale Klasse, wo float statt T drinsteht. Es kommt derselbe Code raus. Ebenfalls alles inline reingeklatscht.

    Mit SSE inlined er, ohne SSE nicht.

    Also zeig du mir doch bitte mal ein Beispiel, wo er die Methode einer Template-Klasse anders inlined als die Methode der äquivalenten normalen Klasse.

    0
  • P

    rapso schrieb:

    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.

    Und wie soll man das umgehen? Weil du schreibst ja oben was von "Anfänger-Gott ...".
    Ist doch erstmal das Prinzip von Templates, dass in jeder o Datei eine entsprechende "Template-Instanz" erzeugt wird. Wie soll man das verhindern?
    Ok inline kann man weglassen, in eurem Disput scheint das ja ne Compiler-Optimierung zu sein, dass er ohne inline Schlüsselwort trotzdem inlined.
    Aber im Allgemeinen?

    0
Anmelden zum Antworten