Beschleunigte Funktion für Quadratwurzel
-
Geschwindigkeit ist beim Game-Proggen sehr wichtig. Welche Funktion verwendet ihr für das Wurzelziehen?
-
Mit was erkaufst du dir das? Ist die Funktion weniger genau?
Meine Richtlinie: möglichst nicht die Wurzel ziehen. :p
-
Man kann die Präzision erhöhen, indem man die Iteration mehrfach durchführt, z.B. dreifach.
..
-
Ach so, jetzt seh ichs grad. Naja, für ne Größenordnung reicht es sicherlich oft aus. Könnte (wenn es denn wirklich schneller ist) nützlich sein, um Längen aufzuaddieren (da kann man nicht mit den Quadraten arbeiten).
Kommt bei mir aber eigentlich nicht vor, dass es an einer Wurzel scheitert, meine Probleme sind meistens eine Ebene höher angesiedelt.
-
http://www.c-plusplus.net/forum/viewtopic.php?t=69304
rapso->greets();
-
Danke für den Link.
Methode ist also wirklich brauchbar. Präzision über Tiefe der Iteration einstellbar.
-
Ich benutze die Funktionen aus <cmath>, da ich noch kein Problem damit hatte.
Bye, TGGC \-/
-
@TGGC: Du wirst doch kein "lamer" sein? Fakt ist, dass die o.g. Funktion in der Regel nur etwa halb so lange braucht wie sqrt(...). Probiere es doch einfach mal aus.
-
Erhard Henkes schrieb:
@TGGC: Du wirst doch kein "lamer" sein? Fakt ist, dass die o.g. Funktion in der Regel nur etwa halb so lange braucht wie sqrt(...). Probiere es doch einfach mal aus.
Wen interessiert das, wenn eine Wurzel nur 3x pro Frame gezogen werden muß, die äußerst komplexen Physikoperationen und KI-Berechnungen (auch ohne Wurzel) aber 98% der Rechenleistung verschlucken...??!
-
Ich finde das recht praktisch wenn man bei Keyframe Animation die Normalen eines Zwischenergebnis zwischen zwei Frames (linear interpoliert) renormalisieren will.
Da spart man (natürlich abhängig von der Anzahl der Vertices und der Modelle) doch etwas ein.cya
liquid
-
Für so kleine Optimierungen bin ich immer zu haben, auch wenn man nicht viel rausholt. Aber nicht auf Kosten der Genauigkeit. Es gibt fast immer einem besseren Algorithmus oder eine geeignetere Datenstruktur (ich hab doch tatsächlich mal ein array wie eine queue verwendet
).Es bringt nichts, wenn ich die Wurzel 3mal so schnell ziehe und sie aber immer noch 982374mal pro Frame ziehen muss.
-
Die Speeds - Wie ist der Compiler da eingestellt ? Für Debug oder "Maximize Speed"...
-
Da ich letztens selbst diverse sqrt-Funktionen getestet hab, hab ich FastSQRT einfach mal dagegen verglichen. Und was soll ich sagen, so fast is die nicht, ganz im Gegenteil, es war die langsamste.
Testsystem:
AMD Athlon XP Barton 2,6 GHz
MSC 7.1 (Maximize Speed /O2, debug disabled, SSE instruction set)die Testkandidaten:
// fpu inline float sqrt1(float x) { asm { fld x fsqrt fstp x } return x; } // sse inline float sqrt2(float x) { asm { movss xmm0, x sqrtss xmm0, xmm0 movss x, xmm0 } return x; } // sse inverse approximation (12-bit precision) inline float sqrt3(float x) { asm { movss xmm0, x rsqrtss xmm1, xmm0 mulss xmm0, xmm1 movss x, xmm0 } return x; } // sse inverse approximation (23-bit precision) inline float sqrt4(float x) { const float const_0_5 = 0.5; const float const_3 = 3; __asm { movss xmm1, x movss xmm2, const_3 rsqrtss xmm0, xmm1 mulss xmm1, xmm0 mulss xmm1, xmm0 subss xmm2, xmm1 mulss xmm0, const_0_5 mulss xmm0, xmm2 mulss xmm0, x movss x, xmm0 } return x; } // 3dnow inverse approximation (15-bit precision) inline float sqrt5(float x) { asm { movd mm0, x pfrsqrt mm1, mm0 punpckldq mm0, mm0 pfmul mm0, mm1 movd x, mm0 femms } return x; } // 3dnow inverse approximation (24-bit precision) inline float sqrt6(float x) { asm { movd mm0, x pfrsqrt mm1, mm0 movq mm2, mm1 pfmul mm1, mm1 punpckldq mm0, mm0 pfrsqit1 mm1, mm0 pfrcpit2 mm1, mm2 pfmul mm0, mm1 movd x, mm0 femms } return x; }das Testprogramm:
float f0 = 1234.5678f; float f1 = 0; chronometer cm; for (unsigned int i2 = 0; i2 != 4; i2++) { cm.start(); for (unsigned int i = 0; i != 100000000; i++) { f1 += sqrt1(f0); // sqrt2, sqrt3, etc. } cm.stop(); std::cout << "[" << i2 << "] " << "time: " << cm.elapsed().milliseconds() << std::endl; cm.reset(); }die Testergebnisse:
sqrt1: ~1308 (~1,093e-08 Fehler)
sqrt2: ~838 (~1,093e-08 Fehler)
sqrt3: ~686 (~3,356e-05 Fehler)
sqrt4: ~1052 (~1,093e-08 Fehler)
sqrt5: ~612 (~1,093e-08 Fehler)
sqrt6: ~914 (~1,093e-08 Fehler)
FastSQRT: ~1447 (~1,093e-08 Fehler)Natürlich ist das ein rein synthetischer Test. Bei diversen anderen Testalgorithmen kommen zum Teil völlig andere Ergebnisse raus (also andere Zeiten, das Verhältnis der Ergebnisse zwischen den einzelnen Funktionen bleibt aber ungefähr gleich). So waren zB bei einfachem Ausrechnen (ohne f1 aufzuaddieren) die SSE Funktionen fast doppelt so schnell.
Wie auch immer, ich denk der Test zeigt wo's lang geht:
1. ich seh keinen wirklichen Verwendungszweck von FastSQRT
2. enorme Performancegewinne lassen sich hier nicht erzielen und wie Optimizer schon gesagt hat, ist es besser, Algorithmen zu verwenden wo man möglichst nicht die Wurzel ziehen braucht (wobei das imo nicht immer möglich ist)
-
Es geht eben nichts über optimalen ASS-Code.
Hast Du auch sqrt(...) unter diesen Bedingungen getestet?
-
Nein, hab ich nicht. Da sqrt() letztendlich auch nur eine Implementierung der CPU Möglichkeiten ist, würde ich keine schlechteren Ergebnisse als bei der FPU Version erwarten. Ausserdem muss man davon ausgehen, dass gute Compiler je nach verwendeten Instruction Set Erweiterungen sqrt() unterschiedlich in den Code "einbauen".
-
nimm mal die hier raus:
if( r == 0.0f ) return 0.0f; if( r < 0.0f ) r = -r ;dann wird das Ergebnis für FastSquad ein bisschen besser aussehen. ansonsten bekomme ich ähnliche Ergebnisse.
-
// Null und negative Zahlen abfangen //if( r == 0.0f ) return 0.0f; if( r < 0.0f ) r = -r ;Die negativen Zahlen sollte man schon abfangen, sonst ergibt es: -1.#IND
-
ja, schon klar. aber dann in jeder funktion.
-
Erhard Henkes schrieb:
// Null und negative Zahlen abfangen //if( r == 0.0f ) return 0.0f; if( r < 0.0f ) r = -r ;Die negativen Zahlen sollte man schon abfangen, sonst ergibt es: -1.#IND
dafür gibt es eine funktion, die ist schneller als ein conditinal jump.
rapso->greets();
-
Ich denke rapso meint hier fabs (oder auch fabsf für single precision Werte) aber da die Funktion viel mit der Integerunit arbeitet, würde ich hier mit einem weiteren Integer das Signbit wegmaskieren. Sonst lädt man den Wert in die FPU, generiert dort den absoluten Wert um in kurz danach wieder zurück in ein GPR zu verschieben.
cya
liquid
