4. Wurzeln schnell ziehen

Wurzeln schnell ziehen

  • 0

    Einige werden es wohl schon kennen, die meisten wohl nicht. Ich hab es auch gerade erst entdeckt, und finde es wirklich nützlich.
    Wurzelziehen in konstant kurzer Zeit.

    float InvSqrt( float x )
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

    Das kommt aus irgendeinem id-Quellcode und ist angeblich 4 mal schneller als die sqrt(). Die Division durch 1, die man noch machen muss, ist da schon mit einbezogen. Denn die Funktion gibt den Kehrwert der Wurzel aus (was in manchen Fällen ja von Vorteil ist).

    So, wollt's nur mal gesagt haben.

    0
  • S

    Habs mit 1 mio Zahlen getestet - konnte keinen unterschied bemerken...

    PS: es gibt doch einen unterschied:
    dein sqrt ist ungenauer... bei sqrt(9) gibts bei dir 3.00343
    ka, ob das wichtig ist - aber ich sags halt mal 🙂

    0
  • 0

    Ich hab es jetzt auch mal gemessen, und so toll ist es wirklich nicht.

    100000000 mal eine Wurzel gezogen (dauernd von anderem Wert) ergibt folgende Laufzeiten:

    sqrtf:
    2656 ms

    1 / InvSqrt:
    2375

    War wohl echt ein Schuss in den Ofen. Ich werde es aber trotzdem noch benutzen da in Spielen die Genauigkeit nicht so wichtig ist.
    Die sqrt Funktion ist bestimmt auch auf moderne Hardware optimiert, wenn man das mit der hier auch machen würde könnte es sich noch verbessern. Ist mir leider nur zu blöd :p

    0
  • R
    Mod

    es kommt immer gut wenn man den testcode angibt.

    dann bin ich mal so frei

    #include <stdio.h>
#include <math.h>

const unsigned int LOOPS=2500000;

float InvSqrt( float x )
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

void main()
{
	float div=4365.f,c=0.f,d=0.f;
	int Tim1=GetTickCount();
	for(float a=1;a<LOOPS;a+=0.125f)
	{
		c+=1.f/sqrtf(a);
	}
	int Tim2=GetTickCount();
	for(float a=1;a<LOOPS;a+=0.125f)
	{
		d+=InvSqrt(a);
	}
	int Tim3=GetTickCount();

	printf("%d %d %f %f",Tim2-Tim1,Tim3-Tim2,c,d);
}

    meine schätzung: bringt auf nem AthlonXP wahrscheinlich nichts, auf nem p4 könnte es einiges bringen.

    rapso->greets();

    0
  • K

    der ganz normale sqrt-fpu-befehl benötigt ab dem pentium I konstante 70 takte. auf einem pentium 4 prescott dürfte das vielleicht noch etwas schneller sein. ob es tatsächlich VIEL bringt die "InvSqrt" funktion zu benutzen bezweifle ich, da eine division 39 takte dauert. wenn also der rest in weniger als 31 takten berechnet werden kann, dann spart man ein bischen; dafür verliert man aber genauigkeit. ist es das wert?

    dann lieber doch:

    float Sqrt2(float x)
{
  __asm {
    fld x
    fsqrt
    fstp x
  }
  return x;
}

    die ist auf einem pentium 4 northwood in etwa genauso schnell. bei 100.000.000 durchläufen und geschwindigkeitsmaximierung (vs .net) braucht:

    Sqrt2 2455 millisekunden

    und

    InvSqrt 2422 millisekunden

    dann doch lieber genaue rechenergebnisse.

    #define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <math.h>
#include <stdio.h>

class CTimer
{
public:
	CTimer(void);
	~CTimer(void);

public:
	void Update(void);
	void Reset(void);

public:
	unsigned long GetHours(void);
	unsigned long GetMinutes(void);
	unsigned long GetSeconds(void);
	unsigned long GetMilliSeconds(void);

private:
	LARGE_INTEGER Frequency;
	LARGE_INTEGER Start;
	LARGE_INTEGER Delta;
};

CTimer::CTimer(void)
{
	QueryPerformanceFrequency(&Frequency);
	QueryPerformanceCounter(&Start);
	Delta.QuadPart=0;
}

CTimer::~CTimer(void)
{
}

void CTimer::Update(void)
{
	LARGE_INTEGER end;

	QueryPerformanceCounter(&end);
	Delta.QuadPart=end.QuadPart-Start.QuadPart;
}

void CTimer::Reset(void)
{
	Start.QuadPart=Start.QuadPart+Delta.QuadPart;
	Delta.QuadPart=0;
}

unsigned long CTimer::GetHours(void)
{
	LONGLONG result;

	result=Delta.QuadPart/(Frequency.QuadPart*3600);
	if (result>0xffffffff) result=0xffffffff;

	return((unsigned long)result);
}

unsigned long CTimer::GetMinutes(void)
{
	LONGLONG result;

	result=Delta.QuadPart/(Frequency.QuadPart*60);
	if (result>0xffffffff) result=0xffffffff;

	return((unsigned long)result);
}

unsigned long CTimer::GetSeconds(void)
{
	LONGLONG result;

	result=Delta.QuadPart/Frequency.QuadPart;
	if (result>0xffffffff) result=0xffffffff;

	return((unsigned long)result);
}

unsigned long CTimer::GetMilliSeconds(void)
{
	LONGLONG result;

	result=(Delta.QuadPart*1000)/Frequency.QuadPart;
	if (result>0xffffffff) result=0xffffffff;

	return((unsigned long)result);
}

inline float Sqrt2(float x)
{
  __asm {
    fld x
    fsqrt
    fstp x
  }
  return x;
}

inline float Sqrt3( float x )
{
	float xhalf = 0.5f*x;
	int i = *(int*)&x;
	i = 0x5f3759df - (i >> 1);
	x = *(float*)&i;
	x = x*(1.5f - xhalf*x*x);
	return x;
} 

void main(void)
{
	CTimer timer;
	unsigned long i;
	unsigned long max=100000000;
	float x;
	float a;

	x=9;
	a=0;

	timer.Update();
	timer.Reset();

	for (i=0;i<max;i++)
		a=Sqrt2(x);

	timer.Update();

	printf("%u, %f\n",timer.GetMilliSeconds(),a);

	x=9;
	a=0;

	timer.Update();
	timer.Reset();

	for (i=0;i<max;i++)
		a=1/Sqrt3(x);

	timer.Update();

	printf("%u, %f\n",timer.GetMilliSeconds(),a);
}
    0
  • R
    Mod

    KXII schrieb:

    for (i=0;i<max;i++)
		a=1/Sqrt3(x);
}

    wundert mich dass dein compiler das nicht wegoptimiert, im releasemode macht das mein VC.Net weg.

    meiner werte auf einem p4 2GHz sind
    -für das sqrtf aus <math.h> : 766ms
    -für die id-software methode: 312ms
    -für das assemblat mit 1.f/ : 656ms

    bei gleichvielen schleifendurchläufen, ohne 1.f/ wäre die dritte methode gleich schnell.

    rapso->greets();

    0
  • K

    damit er es nicht wegoptimiert, muss man die ergebnisse weiterverwerten. deshalb auch das "a". mann muss aufpassen welche optimierung mann nimmt und wie man den code schreibt. je nachdem ist die eine oder andere variante schneller. schreibt man z.b.

    for (i=0;i<max;i++)
  x=Sqrt2(x);   //x anstatt a

    dann ist die math.h variante schneller weil er irgendwass optimiert, bei den anderen aber nicht.

    was mich wundert ist, warum schreibt du bei der math.h variante 1.0f/sqrtf(x) und lässt den kehrwert bei der id variante weg. es sollte doch eher umgekehrt sein, da man die wurzel öfters braucht, als den kehrwert der wurzel.

    vielleicht sollte man einfach beide varianten benutzen. wenn man eine wurzel braucht dann die normale, wenn man den kehrwert braucht dann die id variante ?!?

    0
  • 0

    Edit: Blödsinn weggemacht

    @rapso: Wieso soll der Code auf einem Intel schneller als einem AMD sein? Wegen der Pipeline? Beim InvSqrt sind keine Sprünge drin was gut für die Pipeline ist.

    0
  • R
    Mod

    wenn man performance misst, nimmt man die optimierungen die die betste performance geben. aufpassen sollte man eher beim schreiben des codes 😉

    eigentlich braucht man den kehrwert bei 3d grafik öfter, z.b. zum normalisieren, längen braucht man in massen meißt nur für vergleiche, aber da ist y<x*x schneller als sqrtf(y)<x.
    intern berechnen die cpus erst die reciproc squareroot und rechnen dann 1.f/ . deswegen gibt es auch viele floating point einheiten die nur reciproke werte errechnen können, z.b. 3dnow,vertex+pixelshader,altivec(bin mir nich 100% sicher).

    rapso->greets();

    0
  • R
    Mod

    0x00000001 schrieb:

    @rapso: Wieso soll der Code auf einem Intel schneller als einem AMD sein? Wegen der Pipeline? Beim InvSqrt sind keine Sprünge drin was gut für die Pipeline ist.

    ich hab nicht gesagt, dass intel dort schneller wäre als AMD.
    ich habe gesagt, bei amd wäre der code wohl nicht schneller als die fpu
    bei intel sollte der schneller sein als die fpu.

    das liegt daran dass die fpu beim p4 nicht so effizient ist wie bei AMD, die intergerleistung hingegen ist eigentlich ziemlich effizient. deswegen hab ich erwartet dass es beim AMD nichts bringt und beim p4 schon eher.

    rapso->greets();

    ps. effiziens ist nicht mit performance vergleichbar! ein p4 mir 3GHz mag wohl genausoviele operationen wie ein athlonfx mit 2.2ghz verarbeiten, nur die zeitschritte zwischen den stufen der abarbeitung sind anders. mit effiziens meinte ich also rechenleistung/takt.

    0

  • Die Optimierer wieder. 😎

    Bye, TGGC (Zu viele Primitive hier.)

    0
  • S

    Ich glaub' euch sowieso nicht!

    Wenn das echt vom Carmack ist, ist es - per Definition - min. 10 x schneller...!! :p 👍

    0
  • H

    Wer ist Carmack?

    0
  • C

    H.L.T.O schrieb:

    Wer ist Carmack?

    Der Chef Programmierer von ID Software. Eines der Optimier Genies schlechthin.

    0
  • X

    Sgt. Nukem schrieb:

    Ich glaub' euch sowieso nicht!

    Wenn das echt vom Carmack ist, ist es - per Definition - min. 10 x schneller...!! :p 👍

    vielleicht stammt das ja aus den doom source und war bei 486 und 386 echt schneller.

    0
  • O

    so habs auch mal mit dem bcb getestet.
    erstmal vorweg: kann es sein, dass es im bcb kein equivalent zum sqrtf gibt, sondern nur eine für double/long double(was ja in etwa aufs selbe rauskommen sollte)?

    bei meiner Messung hab ich mich zur besseren vergleichbarkeit für einen statischen wert von 200.1 entschieden(ich hatte halt mal lust diese Zahl zu nehmen ;))

    das ergebnis war meiner meinung nach eindeutig:
    1. methode:2093
    2. methode:4817
    3. methode:1983

    meine cpu isn athlon 2200+
    ok, hier mein code:

    #include <math.h>
#include <iostream>
#include <windows>//für GetTickCount
#include <stdio.h>
#pragma hdrstop

using namespace std;
float a;
//---------------------------------------------------------------------------
float InvSqrt( float x )
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}
float Sqrt2(float x)
{
  __asm {
    fld x
    fsqrt
    fstp x
  }
  return x;
}
#pragma argsused
int main(int argc, char* argv[])
{
    //1. methode
    int Tim1=GetTickCount();
    for(int i=0;i<100000000;++i){
        a=InvSqrt(200.1f);
    }
    int Tim2=GetTickCount();
    cout<<(Tim2-Tim1)<<endl;

    //2.methode
    int Tim3=GetTickCount();
    for(int i=0;i<100000000;++i){
        a=1.f/sqrt(200.1f);
    }
    int Tim4=GetTickCount();
    cout<<(Tim4-Tim3)<<endl;

    //3.methode
    int Tim5=GetTickCount();
    for(int i=0;i<100000000;++i){
        a=Sqrt2(200.1);
    }
    int Tim6=GetTickCount();
    cout<<(Tim6-Tim5)<<endl;

    return 0;
}
    0
  • 0

    Also erstmal: Der Carmack hat die nicht erfunden. Der beschäftigt sich nur den ganzen Tag mit so Zeugs dass er es auch schnell findet. Ich habe gelesen (http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf), dass er das in Q3 benutzt hat. Erfunden hats einer bei nvidia.

    Edit: Schon wieder Blödsinn entfernt.

    0
  • P

    H.L.T.O schrieb:

    Wer ist Carmack?

    :D:D:D Also unter Game-Codern ist dieser Name schon Allgemeinbildung schlecht hin. :D:D:D

    0
  • F

    ChockoCookie schrieb:

    H.L.T.O schrieb:

    Wer ist Carmack?

    Der Chef Programmierer von ID Software. Eines der Optimier Genies schlechthin.

    widerspruch, ich hab da zwar nicht soviel ahnung, aber wenn ich mich recht erinner, wie hieß der micheal abrash ... (?)(progammers black book ??? ), zumindest hat cramack den eingestell zum optimieren oder so ...., gerade weil carmack meinte das er euf dem gebiet noch einen genie gebrauchen könnte ....

    ich weiß net 🙂

    0
  • R
    Mod

    Flow_cplus schrieb:

    ChockoCookie schrieb:

    H.L.T.O schrieb:

    Wer ist Carmack?

    Der Chef Programmierer von ID Software. Eines der Optimier Genies schlechthin.

    widerspruch, ich hab da zwar nicht soviel ahnung, aber wenn ich mich recht erinner, wie hieß der micheal abrash ... (?)(progammers black book ??? ), zumindest hat cramack den eingestell zum optimieren oder so ...., gerade weil carmack meinte das er euf dem gebiet noch einen genie gebrauchen könnte ....

    ich weiß net 🙂

    doch kein widerspruch 😉

    rapso->greets();

    0
Anmelden zum Antworten