Optimierung von Floatvergleichen

[joggel]

Hallo,

ich habe mich letzte Woche mal mit Optimierung etwas beschäftigt.
In meinem Programm vergleiche ich relativ oft Floats miteinander:

Code: Alles auswählen

float a=10.5;
float b=10.5;
const float eps = 1.0e-10;

if( fabs(a-b)>eps)
  floatSindUngleich();
else
  floatSindGleich();

Soweit. Nun habe ich gehört, das ein float-Vergleich relativ "langsam" ist, Also habe ich etwas im Netz recherschiert und folgende Funktion gefunden:

Code: Alles auswählen

bool AlmostEqual2sComplement(float A, float B, int maxUlps)
{
    // Make sure maxUlps is non-negative and small enough that the
    // default NAN won't compare as equal to anything.
    assert(maxUlps > 0 && maxUlps < 4 * 1024 * 1024);
    int aInt = *(int*)&A;
    // Make aInt lexicographically ordered as a twos-complement int
    if (aInt < 0)
        aInt = 0x80000000 - aInt;
    // Make bInt lexicographically ordered as a twos-complement int
    int bInt = *(int*)&B;
    if (bInt < 0)
        bInt = 0x80000000 - bInt;
    int intDiff = abs(aInt - bInt);
    if (intDiff <= maxUlps)
        return true;
   return false;
}

Ich hatte mal mir ein kleines Testprogramm geschrieben, wo ich eine Schleife 1 Mio. mal durchlief, Floats zufällig erzeugt habe und diese einmal mit der 1.Methode ("fasb(a-b)>eps") und einmal mit der 2.Methode ("AlmostEqual2sComplement") getestet habe.

Das eigenartige dabei ist:
In der Debug-Version war der 2.Methode gesamt gesehen schneller, ~20%. .... habe mich schon gefreut.
In der ReleaseVersion war es andersherum, die 1.Methode war schneller..... :shock: .

Nunmal meine Frage:
Wie kann das sein?

[Krishty]

Testaufbau und Compiler.

Die zweite Methode hatte ich vor einiger Zeit in Assimp übernommen; da war sie bedeutend schneller. GCC hat Aliasing-Probleme im Optimizer, wenn man float zu int castet (dort muss man u.U. über union gehen); VC schluckt und optimiert ohne Mucken.

Wahrscheinlich hatte dein Test neben den Vergleichen keine Wirkung konstanter Laufzeit.

Gruß, Ky

[joggel]

Also ich habe unter VC 2005 getestet.
Das heißt dann, dass ich da keine Optimierung mehr rausholen kann?
Gibt es denn keinen CPU/FPU-Befehl der 2 Floats auf ~Gleichheit prüft?

[Edit]
Wie kann ich mir eigentlich mal den DissassamblyCode der Release anschauen? (VS2005)

[Krishty]

Doch, klar kannst du noch optimieren – nur, weil es im Benchmark nicht mehr schneller wurde muss es ja nicht automatisch auch in Real-Life-Situationen langsamer sein. Einen CPU-Befehl für quasi-Gleichheit gibt es nicht. Den Assembler-Code kannst du dir ansehen, indem du mit Debugging-Informationen kompilierst (irgendwo in den Compiler- oder Linkereinstellungen), zur Zeile springst, rechtsklickst und Go to Disassembly auswählst. Poste aber mal deinen Test; ich bin mir sicher, dass wir dann schon die Stelle finden, an der es hakt.

[joggel]

Okay, der Test:

Code: Alles auswählen

	__int64 ctr1 = 0, ctr2 = 0, freq = 0;
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr1);
//******* Test Float-Compare mir herkoemmlicher Methode
	for(int i(0); i<1000000; ++i)
	{
		float scale=RAND_MAX+1.;
		float base1=rand()/scale;
		float fine1=rand()/scale;
		float randomFloat1 = base1+fine1/scale;

		float base2=rand()/scale;
		float fine2=rand()/scale;
		float randomFloat2 = base2+fine2/scale;

		bool ungleich;
		if(fabs(randomFloat1 - randomFloat2 )>eps)
			ungleich = true;
	}

	QueryPerformanceCounter((LARGE_INTEGER *) &ctr2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	float dauer1 = (ctr2 - ctr1) * 1.0 / freq;


	QueryPerformanceCounter((LARGE_INTEGER *) &ctr1);
//******* Test Float-Compare mit alternative Methode
	for(int i(0); i<1000000; ++i)
	{
		float scale=RAND_MAX+1.;
		float base1=rand()/scale;
		float fine1=rand()/scale;
		float randomFloat1 = base1+fine1/scale;

		float base2=rand()/scale;
		float fine2=rand()/scale;
		float randomFloat2 = base2+fine2/scale;

		bool ungleich;
		if(AlmostEqual2sComplement(randomFloat1,randomFloat2,4))     // Dürfte ja für den Test egal sein, welcher Wert der letzte Parametr (Ulps) hat
			ungleich = true;
	}

	QueryPerformanceCounter((LARGE_INTEGER *) &ctr2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	float dauer2 = (ctr2 - ctr1) * 1.0 / freq;

[Krishty]

Du zählst die Zeit zum Erzeugen der Zufallszahlen mit; das ist Bockmist. Der Benchmark wird die Hälfte seiner Zeit in rand() verbringen, ein Drittel mit der Division durch scale und ein Sechstel mit den eigentlichen Vergleichen.

Leg ein Array mit einem Vielfachen von vier als Größe an, füll es mit Zufallszahlen, starte die Zeit und lass dann eine Schleife mit vier Vergleichen auf einmal (damit der Schleifen-Overhead nicht reinspielt) drüberlaufen. Der Optimizer sollte die Schleife komplett wegoptimieren können und die Zeit bei 0 landen. Dann haben wir eine Ausgangslage für Messungen.

Edit: Hmm, das mit der Nullzeit wird wahrscheinlich nicht hinkommen. Es kann sehr gut sein, dass der Compiler das Lesen von Speicher als Wirkung ansieht (z.B. zwecks Prefetching) …

[Helmut]

Naja, die Performance von solchen Minifunktionen messen zu wollen ist sowieso sinnlos, wie ich finde.
Mach erstmal dein Programm fertig. Wenn dann irgendwann die ToDo und Nice-To-Have Liste leer ist, das Programm ausreichend getestet ist, noch Zeit zum vorgenommenen Release ist und du noch Lust hast, kannst du die Funktion austauschen und gucken, ob das Programm dann besser läuft. Ist dann ne Sache von einer Minute.
Ich finde man sollte darauf achten, dass die investierte Zeit in eine Optimierung weniger sein sollte, als die Summe der ersparten Zeit bei den Anwendern.

Ciao
Helmut

[joggel]

Nun gut....
Nun habe ich folgenden Code:

Code: Alles auswählen

	float* floatArray = new float[10000000];
	for(int i(0); i<10000000; ++i)
	{
		float scale=RAND_MAX+1.;

		float base1=rand()/scale;
		float fine1=rand()/scale;
		float randomFloat1 = base1+fine1/scale;
	
		floatArray[i] = randomFloat1;	
	}
	
	__int64 ctr1 = 0, ctr2 = 0, freq = 0;
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr1);
//******* Test Float-Compare herkoemlich
	for(int i(0); i<10000000 - 1; ++i)
	{
		float a = floatArray[i];
		float b = floatArray[i+1];

		bool ungleich;
        if(fabs(a - b )>eps)
                ungleich = true;

        if(fabs(a - b )>eps)
                ungleich = true;

		if(fabs(a - b )>eps)
                ungleich = true;

		if(fabs(a - b )>eps)
                ungleich = true;
	}
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	float dauer1 = (ctr2 - ctr1) * 1.0 / freq;


	QueryPerformanceCounter((LARGE_INTEGER *) &ctr1);
//******* Test Float-Compare Alternative
	for(int i(0); i<10000000 - 1; ++i)
	{
		float a = floatArray[i];
		float b = floatArray[i+1];

		bool ungleich;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich=true;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich=true;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich=true;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich=true;
	}
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	float dauer2 = (ctr2 - ctr1) * 1.0 / freq;

Ich hoffe du meintest das mit den 4mal in einer Schleife Vergleichen auch so.... :oops:

Nun ist im Release ausgegeben, dass beide Methoden 0 Sekunden brauche...

[joggel]

@Helmut
Ja, sehe ich evtl. auch so.
Also ich widme mich diesem Thema nur, weil es mich eben mal interessiert!
Mich hat es halt verwirrt, das es in der Release langsamer ist, als in der Debug.

[Krishty]

Ich hoffe du meintest das mit den 4mal in einer Schleife Vergleichen auch so.... :oops:

Nein :) Der Compiler erkennt jetzt, dass alle vier Vergleiche genau dasselbe machen und optimiert drei davon weg. Du sollst immer vier unterschiedliche Vergleiche durchführen (z.B. auf i, i+1, i+2, i+3) und die Schleife dafür nur ein Viertel so oft ausführen (i+=4). Damit sinkt der Schleifen-Overhead auf ein Viertel, während die Vergleichsarbeit gleich bleibt.

[Krishty]

Nun ist im Release ausgegeben, dass beide Methoden 0 Sekunden brauche...

Perfekt! Jetzt baust du vor die Schleife eine volatile bool (das bedeutet, dass der Compiler Operationen auf diese bool ausführen muss, selbst, wenn sie überflüssig aussehen und verhindert, dass die Schleife als Ganzes wegoptimiert wird – benutzt man z.B. beim Auslesen von Sensoren, wo bestimmte Variablen ihre Werte auch dann ändern, wenn das Programm garnicht auf sie zugreift). Die füllst du innerhalb der Schleife mit dem Ergebnis aus allen vier Vergleichen: ungleich = Vergleich1 | Vergleich2 | Vergleich3 | Vergleich4; (ja, bitweise – damit der Compiler definitiv alle vier Vergleiche ausführt, auch, wenn einer false evaluiert, sonst würde abgebrochen werden müssen und die ganzen bedingten Sprünge würden die sorgsam abgerollte Schleife wieder zunichte machen. Kombiniert weil, wenn jeder Vergleich auf die Variable zugreifen würde, würde das viele Laden und Speichern wahrscheinlich wieder genauso lange dauern wie die Vergleiche selber).

Achja, noch an Helmut und joggel zusammen: Ihr dürft nicht vergessen, dass die beiden Funktionen völlig unterschiedliche Funktionsweisen haben und nicht wahllos austauschbar sind. Die Epsilon-Version wird bei kleinen und großen Zahlen versagen; die bitweise Version funktioniert bei allen Größenordnungen gleich gut. Es ist also keine pure Performance-Optimierung …

[joggel]

Uff... solche Tricks... :D
Okay, der Code sieht nun so aus:

Code: Alles auswählen

	__int64 ctr1 = 0, ctr2 = 0, freq = 0;
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr1);
//******* Test Float-Compare herkoemlich
	volatile bool krishtysVolatileBool; 
	for(int i(0); i<10000000 - 4; i += 4)
	{
		float a = floatArray[i];
		
		float b = floatArray[i+1];
		bool ungleich1;
        if(fabs(a - b )>eps)
           ungleich1 = true;

		b = floatArray[i+2];
		bool ungleich2;
        if(fabs(a - b )>eps)
           ungleich2 = true;

		b = floatArray[i+3];
		bool ungleich3;
        if(fabs(a - b )>eps)
           ungleich3 = true;

		a = floatArray[i+1];
		b = floatArray[i+3];
		bool ungleich4;
        if(fabs(a - b )>eps)
           ungleich4 = true;

		krishtysVolatileBool= ungleich1 | ungleich2 | ungleich3 | ungleich4;
	}
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	float dauer1 = (ctr2 - ctr1) * 1.0 / freq;

	QueryPerformanceCounter((LARGE_INTEGER *) &ctr1);
//******* Test Float-Compare Alternative
	for(int i(0); i<10000000 - 4; i += 4)
	{
		float a = floatArray[i];
		float b = floatArray[i+1];
		bool ungleich1;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich1=true;

		b = floatArray[i+2];
		bool ungleich2;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich2=true;

		b = floatArray[i+3];
		bool ungleich3;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich3=true;

		a = floatArray[i+1];
		b = floatArray[i+3];
		bool ungleich4;
        if(!AlmostEqual2sComplement(a,b,4))
			ungleich4=true;

		krishtysVolatileBool= ungleich1 | ungleich2 | ungleich3 | ungleich4;

	}
	QueryPerformanceCounter((LARGE_INTEGER *) &ctr2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	float dauer2 = (ctr2 - ctr1) * 1.0 / freq;

Und Ergebniss....*tadaaa*:
Methode1: 0.0456831
Methode2: 0.041815 (die alternative)

Resumee:
Die Alternative ist wirklich immer schneller.(?)

[Krishty]

Ja, der Code ist so in Ordnung. Bischl mickrig, der Gewinn … 10 % … es hätten schon mindestens 30 sein sollen. Optimierungseinstellungen vergessen? Full Optimization (/Ox), Enable Function-Level Linking (/Gy), Use Link-Time Code Generation (/LTCG) (auch bei Whole Program Optimization) eingeschaltet (LTCG erlaubt über das wahrscheinlich sowieso geschehende Inlining hinaus noch die komplette Re-Organisation der Aufrufer)? Alles Inlining aktiviert? Ansonsten mal die Vergleichsmenge verhundertfachen (ich habe hier auch einen Benchmark im 10-ms-Bereich, der ist bei der ersten Ausführung doppelt so schnell wie bei allen folgenden – bei so kleinen Zeitintervallen kann schonmal der Task-Scheduler dazwischenkommen) und gucken, ob sich der Vorsprung zementiert …

[joggel]

So....
nun habe ich etwas die Compile- bzw. Linkeinstellun geändert, und zwar:
1.) komplette Optimierung ==> /Ox
2.) Inlinefunktionserweiterung: Alles Geeignete ==> /Ob2.... nicht sicher, ob das auch so ok ist!
3.) Größe oder Geschw. bevorugen: Schnellen Code bevorzugen ==> /Ot
4.) Komplette Programmoptimierung: Link-Zeitcodegenerierung aktivieren /Gl
5.) Linkereinstellung: Link-Zeitcodegenerierung: Link-Zeitcodegenerierung verwenden ==> /ltcg

Vlt. habe ich auch bei der einen oder anderen Option nicht richtiges gesetzt, oder ein paar vergessen. Ich habe auch nicht alle die von Dir vorgeschlagenen Schalter gefunden.
Jedenfalls:
Ich haben die Schleifendurchgänge auf: 100000000 erhöht, und nun sind die Ergebnisse wie folgt:
a.) mit Epsilonvergleich: 0.64090
b.) mit Bitvergleich: 0.38481
:ugeek:

Cooool, und vielen Dank...

[eXile]

Achja, noch an Helmut und joggel zusammen: Ihr dürft nicht vergessen, dass die beiden Funktionen völlig unterschiedliche Funktionsweisen haben und nicht wahllos austauschbar sind. Die Epsilon-Version wird bei kleinen und großen Zahlen versagen; die bitweise Version funktioniert bei allen Größenordnungen gleich gut. Es ist also keine pure Performance-Optimierung …

Genau darum geht es. Aber noch eine Ergänzung: Bei denormalisierten Zahlen wird der Epsilon-Vergleich genau wie der Integer-Vergleich funktionieren, und hat damit sehr wohl seine Daseinsberechtigung, wenn man ganz genau weiß, dass man numerisch nur auf solche Werte kommt. Was aber kaum der Fall sein dürfte. Darum ist ein Epsilon-Vergleich fast immer falsch, und sollte - wie du schon sagst - vermieden werden.

Wobei mich 128-Bit-Integer-Arithmetik aber schon sehr sehr reizen würde …

[Krishty]

Ja, die Optionen sind schon gut so. Mit den neuen Durchläufen sieht es auch schon viel deutlicher aus, klasse! Es ist noch anzumerken, dass die Funktion im Feldeinsatz u.U. nicht so schnell ist – z.B., wenn die Parameter Zwischenergebnisse sind und darum in der FPU liegen und erst zurück auf den Stack müssen, um als int interpretiert zu werden. Aber selbst dann ist sie noch schneller als mit Epsilon.

Als Ergänzung zu eXile: Es gibt noch einen Epsilon-Vergleich, der sich die Größenordnung der Zahlen zu nutze macht … quasi „Epsilon ist immer so groß wie 1 % von einer der Zahlen“ … irgendwo hatte da mal jemand richtig Zeit investiert und die Größenordnungen beider Zahlen miteinkalkuliert – damit bekommt man bedeutend zuverlässigere Ergebnisse, fast so gut wie bei dem Integer-Vergleich. Dafür wird es dann aber auch richtig langsam; etwa 4× langsamer als der Integer-Vergleich.

Wobei mich 128-Bit-Integer-Arithmetik aber schon sehr sehr reizen würde …

Mich reizt viel mehr gute Festkommaarithmetik – aber die kann man ja leider nicht immer haben.

[eXile]

Wobei mich 128-Bit-Integer-Arithmetik aber schon sehr sehr reizen würde …

Mich reizt viel mehr gute Festkommaarithmetik – aber die kann man ja leider nicht immer haben.

Args, sorry, ich meinte natürlich Festkommaarithmetik. ;) Ich kann übrigens den Vortrag "Epsilon is not 0.00001" nur empfehlen.