Performance von Test gegen Null mit kleinem Epsilon für floats

hellihjb

oder Intel VTune - laeuft nur auf intel-cpus, ist aber sehr maechtig und kostet geld.
der code analyst laeuft ueberall.

flammenvogel

Also ich wollte eigentlich kein Geld dafür ausgeben, ich lade mir jetzt erstmal dieses Tool von Amd runter. Die große Frage ist nur ob das auf Intel CPUs funktioniert/Probleme macht.

FelixManke

Um nochmal auf meinen Test zurückzukommen :). Hab nochmal nen Test gemacht mit der Assembler-Version:

bool IsZero1(float f)
{
    return fabs(f) <= CUtils::ZERO;
};
bool IsZero1Asm(float f)
{
    bool result;
    _asm 
    {
        xor     bl,bl
        fld     f
        fabs
        fcomp   CUtils::ZERO
        fstsw   ax
        fwait    
        sahf      
        adc     bl,0
        mov     result,bl
    };
    return result;
};
bool IsZero2(float f)
{
    return (f >= -CUtils::ZERO) && (f <= CUtils::ZERO);
};

Ergebnisse (100000000 Durchläufe):

IsZero1(): 11,70925581
IsZero1Asm(): 5,12243133
IsZero2(): 4,59284843

Fazit: Der Unterschied zwischen selbst kontrolliertem fabs (IsZero1Asm) und Variante zwei ist ziemlich gering. Die Implementierung von Microsoft fabs() macht offenbar interessante Sachen...

Gib's noch ne Assembler-Variante zu IsZero2()?? Und wie ist der Code für gcc? Und Inkompatibilitäten habe ich nicht zu befüchten, sofern ich für nen x86er kompiliere? Gibt's da nen Compiler-Define, was man abfragen kann? Dann könnte man sowas machen wie

#ifdef _X86 && _GCC
asm mit '%'
#elif _X86 && _MSC_VER
asm ohne '%'
#else
normal 
#endif

hellihjb

das waere vielleicht noch einen test wert:

float EPS= 0.0001f;
inline bool zero(float a)
{
	_asm {
		mov ecx,a
		xor eax,eax
		and ecx,0x7fffffff
		sub ecx,EPS
		adc eax,0
	};
}

voraussetzung ist, dass "EPS" positiv ist.
da (positive) wachsende floating-point-zahlen in ihrer binaer-repraesentation streng monoton steigend sind, kann man sich das auslesen der fpu-flags sparen...

bzgl gcc gibt's irgendwelche flags die auch inline-assembler mit intel-syntax erlauben, hab's aber auch nicht mehr im kopf - muesste sich per suche finden lassen.

FelixManke

hellihjb schrieb:

das waere vielleicht noch einen test wert:
float EPS= 0.0001f;
inline bool zero(float a)
{
	_asm {
		mov ecx,a
		xor eax,eax
		and ecx,0x7fffffff
		sub ecx,EPS
		adc eax,0
	};
}
voraussetzung ist, dass "EPS" positiv ist.

Äh, fehlt da nicht noch ein bool result; über und nen mov result,eax im asm block? Und EPS ist doch positiv. Ist doch oben definiert. Wobei ich den code so gar nicht verstehe :)...

LordJaxom

Der "Trick" ist hier, dass eax das Register ist in dem der Return-Wert transportiert wird. Brauchst also eax nicht nochmal nach eax kopieren

camper

das können wir sogar ohne inline-assembler machen:

inline bool zero(const float& a)
{
	static const float eps = 0.0001f;
	return (reinterpret_cast<const unsigned&>(a)&(~0u>>1))<reinterpret_cast<const unsigned&>(eps);
}

der erzeugte code ist ggf. sogar noch effizienter. das ist mal ein seltener fall, wo es sich lohnt, builtins als referenz-auf-const zu übergeben, da die funktion eigentlich gar nicht mit dem argument in form eine floats arbeitet - jedenfalls verbleibt mit vc2005ee bei einfacher übergabe als float selbst bei höchster optimierung noch eine fld/fstp kombination, wenn das argument per value übergeben wird.

hellihjb

das "<" wird aber wahrscheinlich wieder in einen conditional-branch uebersetzt...

LordJaxom

Also der VC++2005 macht aus camper's Beispiel (im Kontext einer if-Condition) folgendes.

float f;
if (zero(f)) {
}

00401011  mov         ecx,dword ptr [esp] 
00401014  and         ecx,7FFFFFFFh 
0040101A  cmp         ecx,38D1B717h 
00401020  jae         main+31h (401031h)

Jap, das ist effizienter

EDIT:
Feststellung: Ein gut optimierender Compiler hat schon was.

camper

hellihjb schrieb:

das "<" wird aber wahrscheinlich wieder in einen conditional-branch uebersetzt...

zum glück gibt es seit ewigkeiten (PPro) die setcc befehle

FelixManke

Was passiert da?!?! Kann man den Code vom Compiler nicht einfach übernehmen? Ich versteh nur Bahnhof...

LordJaxom

@FelixManke: Nein, in diesem Fall muss man dem optimierenden Compiler überlassen, aus camper's inline-Funktion und dem Zusammenhang "das Beste" zu machen...

00401011  mov         ecx,dword ptr [esp] ; Kopiert float f (erste Var auf dem Stack, deshalb esp) nach ecx
00401014  and         ecx,7FFFFFFFh       ; s.o.
0040101A  cmp         ecx,38D1B717h       ; Vergleich mit Konstante
00401020  jae         main+31h (401031h)  ; Sprung hinter das if (zero(f)) { ... } wenn nicht zero

EDIT:
Vorteil bei so einer Inline-Expansion ist, dass der Compiler noch weiter optimieren kann (was er bei Inline-Assemblercode nicht mehr kann), und sich nochdazu einen Sprung (in die Fkt. zero) spart.

hellihjb

ihr habt recht.
vc2003 macht so ziemich das gleiche draus:

mov ecx,dword ptr [eax] 
and ecx,7FFFFFFFh 
cmp ecx,dword ptr [EPS (407030h)] 
sbb eax,eax 
neg eax

ein hoch auf den compilerbauer!

jetzt waer' nur noch interessant, warum er das fabs() so verkackt

FelixManke

Der Code (die version mit dem reinterpret_cast und die entsprechende Assembler-Variante) verlässt sich ja ziemlich darauf, dass Floats so repräsentiert werden, wie sie anscheinend werden. Wann kann es da zu Problemen kommen? Nur bei anderen CPUs? Sind x86er immer so? Was ist mit 64 Bit Architekturen?

Ich muss das mal auf Geschwindigkeit testen. Aber wenn das nicht soo viel bringt, fühle ich mich mit C++ Code besser ;). Oder ich könnte nen #ifdef drumstricken und hätte noch ne Alternative im #else Zweig (z.B. die return (f >= -ZERO) && (f <=ZERO) Variante). Welche Präprozessor-Symbole brauche ich dann?

FelixManke

Was mir zum fabs() einfällt: Der Profiler braucht Debugcode. Da kann das alles natürlich etwas anders ausehen...

hellihjb

Der Code verlässt sich ja ziemlich darauf, dass Floats so repräsentiert werden, wie sie anscheinend werden. Wann kann es da zu Problemen kommen?

damit's nicht funktioniert muesste deine architektur keine 32bit-floats entsprechend IEEE-norm haben.
da kenn ich so spontan - keine.
irgendwer anders?

camper

auf maschinen mit little-endian byte-order dürfte das sogar funktionieren, solange die representation der gleitkommazahl selbst IEEE konform ist und die größe dieser wenigstens so groß wie int ist. d.h. z.b. eine variante für double sollte auch funktionieren, ohne dass wir deswegen einen größeren integer benötigen (dabei geht nur etwas genauigkeit beim vergleich verloren, bei so einem epsilontest spielt das keine rolle).

FelixManke

Hab mal mit vs2002 Release kompilieren lassen (sorry für den häßlichen Output):

Meine IsZero1() { return fabs(f) <= CUtils::ZERO; }:

PUBLIC    ?IsZero1@@YA_NM@Z                ; IsZero1
; Function compile flags: /Ogty
;    COMDAT ?IsZero1@@YA_NM@Z
_TEXT    SEGMENT
_f$ = 8
?IsZero1@@YA_NM@Z PROC NEAR                ; IsZero1, COMDAT

; 753  :     return fabs(f) <= CUtils::ZERO;

    fld    DWORD PTR _f$[esp-4]
    fabs
    fld    DWORD PTR ?ZERO@CUtils@@2MB        ; CUtils::ZERO
    fcompp
    fnstsw    ax
    test    ah, 1
    jne    SHORT $L123904
    mov    eax, 1

; 754  : };

    ret    0
$L123904:

; 753  :     return fabs(f) <= CUtils::ZERO;

    xor    eax, eax

; 754  : };

IsZero2() { return (f >= -CUtils::ZERO) && (f <= CUtils::ZERO); }:

PUBLIC    ?IsZero2@@YA_NM@Z                ; IsZero2
; Function compile flags: /Ogty
;    COMDAT ?IsZero2@@YA_NM@Z
_TEXT    SEGMENT
_f$ = 8
?IsZero2@@YA_NM@Z PROC NEAR                ; IsZero2, COMDAT

; 774  :     return (f >= -CUtils::ZERO) && (f <= CUtils::ZERO);

    fld    DWORD PTR ?ZERO@CUtils@@2MB        ; CUtils::ZERO
    fchs
    fcomp    DWORD PTR _f$[esp-4]
    fnstsw    ax
    test    ah, 65                    ; 00000041H
    jp    SHORT $L123910
    fld    DWORD PTR _f$[esp-4]
    fcomp    DWORD PTR ?ZERO@CUtils@@2MB        ; CUtils::ZERO
    fnstsw    ax
    test    ah, 65                    ; 00000041H
    jp    SHORT $L123910
    mov    eax, 1

; 775  : };

    ret    0
$L123910:

; 774  :     return (f >= -CUtils::ZERO) && (f <= CUtils::ZERO);

    xor    eax, eax

; 775  : };

IsZero3() {return (reinterpret_cast<const unsigned&>(f)&(~0u>>1))<reinterpret_cast<const unsigned&>(CUtils::ZERO);}

PUBLIC    ?IsZero3@@YA_NABM@Z                ; IsZero3
; Function compile flags: /Ogty
;    COMDAT ?IsZero3@@YA_NABM@Z
_TEXT    SEGMENT
_f$ = 8
?IsZero3@@YA_NABM@Z PROC NEAR                ; IsZero3, COMDAT

; 778  :     return (reinterpret_cast<const unsigned&>(f)&(~0u>>1))<reinterpret_cast<const unsigned&>(CUtils::ZERO);

    mov    eax, DWORD PTR _f$[esp-4]
    mov    ecx, DWORD PTR [eax]
    mov    eax, DWORD PTR ?ZERO@CUtils@@2MB
    and    ecx, 2147483647                ; 7fffffffH
    cmp    ecx, eax
    sbb    eax, eax
    neg    eax

; 779  : }

camper

die optimierung, die reinterpret_cast<const unsigned&>(CUtils::ZERO) wie konstanten ausdruck behandelt, wird offenbar erst durch vc++8.0 durchgeführt.
behelfsmäßig könnte man ja soetwas machen:

inline IsZero3()
{
    assert(0x38D1B717h==reinterpret_cast<const unsigned&>(CUtils::ZERO));
    return (reinterpret_cast<const unsigned&>(f)&(~0u>>1))<0x38D1B717h;
}

und so auch mit älteren compilern besseren code erhalten. die funktion sollte im übrigen unbedingt inline sein.

FelixManke

hellihjb schrieb:

damit's nicht funktioniert muesste deine architektur keine 32bit-floats entsprechend IEEE-norm haben.
da kenn ich so spontan - keine.
irgendwer anders?

camper schrieb:

auf maschinen mit little-endian byte-order dürfte das sogar funktionieren, solange die representation der gleitkommazahl selbst IEEE konform ist und die größe dieser wenigstens so groß wie int ist. d.h. z.b. eine variante für double sollte auch funktionieren, ohne dass wir deswegen einen größeren integer benötigen (dabei geht nur etwas genauigkeit beim vergleich verloren, bei so einem epsilontest spielt das keine rolle).

Ich frag ja nur, weil der Code einfach funktionieren MUSS. Da darf nicht plötzlich Mist rauskommen, nur weil ich ein bisschen mit Assembler rumgespielt habe, und keiner merkt etwas :). So einen Fehler zu finden ist ja fast unmöglich.

Wie schaut's denn aus mit meinen Präprozessor-Symbolen? Gibt's welche?