4. Wurzeln schnell ziehen

Wurzeln schnell ziehen

  • 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

  • Flow_cplus schrieb:

    gerade weil carmack meinte das er euf dem gebiet noch einen genie gebrauchen könnte ....

    Na ich hab jedenfalls keine Zeit. 😎

    Bye, TGGC (Reden wie die Großen)

    0
  • E

    siehe auch:
    http://www.c-plusplus.net/forum/viewtopic.php?t=75441

    0
  • A

    hier mein code den ich benutze und der die besten ergebnisse bringt:

    float Sqrt3DNow(float x)
{
	__asm
	{
		femms
		movd		MM0, x
		pfrsqrt		MM1, MM0
		punpckldq	MM0, MM0
		pfmul		MM0, MM1
		movd		x, MM0
		femms
	}
	return x;
}

float SqrtSSE(float x)
{
	_asm
	{
		sqrtss		XMM0, x
		movss		x, XMM0
	}
	return x;
}

    hmm, wie kriegt man die tabs hier richtig formatiert?

    0
  • L

    Sowohl 3DNow als auch SSE benutzen im CPU integrierte Tabellen mit approximierten Ergebnissen um die Werte zu generieren. Bei 3DNow sind es afaik 14 Bits an Präzision, die man so bekommt. Das ist nicht gerade viel und AMD empfiehlt deshalb auch mit einer Newton-Raphson Iteration das Ergebnis zu verbessern. Intel weist darauf auch an verschiedenen Stellen in seinen Dokumentationen hin.
    14 Bit sind nicht gerade viel und das kann zu derben Fehlern in der Darstellung führen.

    cya
    liquid

    0
Anmelden zum Antworten