[C++] Gleitkomma- zu Ganzzahlen runden

[Krishty]

Hi,

Es geht, wie der Titel sagt, um das Runden von Gleitkommazahlen zu Ganzzahlen. Ich möchte die Situation, so wie sie mir erscheint, mal schnell rekapitulieren … wenn was nicht stimmt, bitte sofort korrigieren:


Es gibt keine Funktion round() in C++. Die Funktion wurde zwar in den Standard C99 aufgenommen, da sich C++ aber schon früher von C abgespalten hat, ist sie in keinem aktuellen C++-Standard enthalten und wird ergo von vielen Compilern – insbesondere Visual C++ – nicht angeboten.

Die einzige Möglichkeit, eine Rundung in C++ vorzunehmen ist eine Kombination aus einem nativen Cast mit einem positiven oder negativen 0,5er-Offset für positive oder negative Werte – und damit nicht nur furchtbar ineffizient sondern auch hässlich.

Die FPU bietet das Runden von Gleitkommazahlen zu Ganzzahlen nativ an. Weil dabei – im Gegensatz zum in C/C++ nativen Cast – das Umstellen der Rundungsmethode entfällt, ist dies sogar, je nachdem welche Benchmarks man anführt, bis zu 15× schneller als die oben genannte Lösung und sogar noch um ein Vielfaches schneller als der in C/C++ native Cast, der die Nachkommastellen immer nur abschneidet und dafür die FPU umstellen muss.

Es ist möglich, diese FPU-Funktion per Inline-Assembler zu nutzen … mit einer Länge von nur zwei Befehlen sieht der Code sogar besser aus als der zur Rundung nötige C++-Code. Allerdings ist immer davon die Rede, dass Inline-Assembler die Optimierung durch den Compiler erschwert oder bricht, und noch schlimmer: Inline-Assembler ist unter x64 kaum noch möglich und wird durch Intrinsics verdrängt. Abgesehen davon, dass Intrinsics keine standardkonforme Lösung sind, hat z.B. Microsoft ein Intrinsic zur Rundung bereits abgelehnt.


Jetzt mal beiseite gelassen, dass ich diesen Umstand vollkommen lächerlich finde: Wen muss ich nun also schmieren, um an eine hocheffiziente, x64-fähige, standardkonforme C++-Methode zu kommen, Gleitkommazahlen zu Ganzzahlen zu runden? :(

Gruß, Ky

[Krishty]

Soo … mal was aus der Kategorie „gut zu wissen“:

Wollt ihr eine Gleitkommazahl zwischen 0 und 1 (und nichts sonst!) schnell zu einer 8-Bit-Ganzzahl runden:

Code: Alles auswählen

unsigned char FastFloatToChar(float p_Value) {
    p_Value = 256.5f + 255.0f * p_Value;
    return static_cast<unsigned char>((reinterpret_cast<unsigned int &>(p_Value) & 0x007F8000) >> 15);
}

(das „&“ soll ein „&“ sein)

Bevorzugt ihr das Abschneiden der Nachkommastellen, ersetzt die 256.5f durch 256.0f.

Richtig interessant wird diese Möglichkeit, wenn man gleich vier floats in ein unsigned int packen muss:

Code: Alles auswählen

unsigned int FastFloatToCharRGBA(float4 p_rgbaValue) {
    p_rgbaValue= 256.5f + 255.0f * p_rgbaValue;
    return ((reinterpret_cast<unsigned int &>(p_rgbaValue.r) & 0x007F8000) >> 15)
         | ((reinterpret_cast<unsigned int &>(p_rgbaValue.g) & 0x007F8000) >>  7)
         | ((reinterpret_cast<unsigned int &>(p_rgbaValue.b) & 0x007F8000) <<  1)
         | ((reinterpret_cast<unsigned int &>(p_rgbaValue.a) & 0x007F8000) <<  9);
}

Eine generelle Lösung für schnelle float/double-Rundung fehlt mir aber immernoch … zumal ich mir vorstellen kann, dass dieser Code immernoch bei Weitem nicht an den guten alten Assembler rankommt … :/ Der Credit geht an Nils Pipenbrinck aus dem Devmaster.net-Forum.

[Jörg]

Ich will keine flamewar vom Zaun brechen, aber statt aliasing-verletzenden casts wuerde ich hier doch lieber den inline-assembler bemuehen.
Das sichert zu, dass auf neuen Platformen wenigstens der drueber stolpert, der den Code portiert ;) Und IEEE floats muessen ja auch nicht unbedingt sein, falls man mal mit aelterem IBM-Code zu tun hat.

[Krishty]

Inline-Assembler habe ich aber unter x64 nicht :(

[Jörg]

Koennte das kein Grund sein, sich vom MS-Compiler zu verabschieden?

[Jörg]

Mir faellt da gerade ein, dass man da was machen koennte, mit Aufwand :)

1. Eine dummy-Funktion definieren, welche mit emit-Direktiven Platzhalter schafft.
2. Vom Compiler nicht direkt .obj-Files generieren lassen , sondern einen asm-Output
3. Dort mit einem eigenen Tool die dummy-Aufrufe ersetzen
4. Den Assembler anwerfen

[Schrompf]

Ich sehe nix Böses an der Lösung. Erst recht nichts, um dafür den Aufwand auf sich zu nehmen, einen alternativen Compiler in Visual Studio zu integrieren. Ich weiß allerdings nicht, ob die vorgestellte BitSchiebe-Lösung tatsächlich schneller ist als ein schlichter "static_cast<uchar> (wert * 255.99f)".

[edit] Mir fällt gerade auf, dass es doch Probleme geben könnte, wenn die FPU beschließt, z.B. eine 0.2f als 0.8 * 2^-2 darzustellen. Ist ja theoretisch auch eine valide Fließkommazahl. Hat mit Aliasing zwar immernoch nix zu tun, aber sollte man evtl. mal betrachten, ob sowas vorkommen kann.

[Richard Schubert]

[edit] Mir fällt gerade auf, dass es doch Probleme geben könnte, wenn die FPU beschließt, z.B. eine 0.2f als 0.8 * 2^-2 darzustellen. Ist ja theoretisch auch eine valide Fließkommazahl. Hat mit Aliasing zwar immernoch nix zu tun, aber sollte man evtl. mal betrachten, ob sowas vorkommen kann.

Da kann man beruhigt sein, sowas kann nicht vorkommen. Wäre auch eine Verschwendung von möglichen Zuständen, wenn es mehrere Möglichkeiten gäbe ein und die selbe Zahl mehrmals darzustellen.

[Krishty]

@Schrompf: Der gewöhnliche Cast rundet nicht sondern knippst ab, darum die Pfriemelei.

@Schrompf, Richard: Stimmt, Gleitkommazahlen sind immer normalisiert damit sowas nicht vorkommen kann, ähnlich wie Dezimalzahlen immer zwischen 1 und 10 normalisiert werden (3,64x10^5 statt 36,4x10^4).


Die Sache an dem Code ist, dass er nur für 8-Bit-UInts funktioniert. Für 16 Bits müsste er schon wieder umgeschrieben werden, mit Vorzeichen wird er nochmal komplizierter und 32 Bits sind nicht möglich. Ich würde gerne beliebige Gleitkommazahlen runden ... daher habe ich ihn auch nur als "gut zu wissen" angeführt.

Den Compiler werde ich wegen einem fehlenden Feature, das ich in zwei aus 50k Zeilen brauche, sicher nicht wechseln ... ich habe Hinweise gefunden, dass man Assembler durch Drittdateien in x64 einbinden kann. Ist natürlich die schlechteste Lösung nach standardkonformen Funktionen und Intrinsics, aber alles andere führt ja scheinbar zu nichts.

Danke übrigens dass ihr euch damit beschäftigt, ich dachte schon, das Thema würde einfach wieder im Sand verlaufen ... :)

[Jörg]

Ja das geht, externe Module zu nehmen. Aber damit bekommst Du normalerweise den Funktionsaufruf-Overhead mit, der fuer einen 2Zeiler dann doch erheblich ist. Ich weiss nicht, wie gut LTCG funktioniert, um das abzufangen und ob du dann am Ende nicht genauso langsam dastehst. Bezgl. 32 Bit....irgendwann hast Du eh keine Nachkomma-Stellen mehr, kannst dich also auf 24 Bit beschraenken ;)
Aus dem Kopf weiss ich auch nicht, ob fastcall in x64 funktioniert, und wo die float-Parameter liegen. Wenn Du Pech hast, sind die in den SSE-Registern, da die FPU eh optional ist, dann musst Du noch umstaendlich rumkopieren.
Brauchst Du wirklich round-to-nearest Verhalten ? Wuerde CVTTSS2SI sonst empfehlen.

[Schrompf]

Hast Du das mal durch einen Unittest gejagt? Floats >1 werden doch auch als nicht als 000101011 * 2^-1 abgelegt, sondern die führende 1 wird immer an die Spitze der Mantisse hochgezogen und der Unterschied durch den Exponenten ausgeglichen. Nach meinem Verständnis müsstest Du dann bereits ab Zahlen >0.5 falsche Ergebnisse bekommen.

Mein Vorschlag würde übrigens auch runden, glaube ich... ich expandiere den Wertebereich ja auch 255.999f... also der höchste Float-Wert ergibt gerade noch so 255, und auch ein gewisser Bereich kleiner 1 ergibt noch 255. Im unteren Bereich hilft der Trick dagegen nicht.

[Jörg]

Hast Du das mal durch einen Unittest gejagt? Floats >1 werden doch auch als nicht als 000101011 * 2^-1 abgelegt, sondern die führende 1 wird immer an die Spitze der Mantisse hochgezogen und der Unterschied durch den Exponenten ausgeglichen.

Das stimmt, aber durch das Bias 256 und die Einschraenkung, dass das Original wirklich nur zwischen 0 und 1 liegen darf, bleibst du in einer 2er-Dekade (aehm...wie waere das richtige Wort hier??? Duade? Biade?), so dass die fuehrende virtuelle 1 wegfaellt und die Mantisse den Bereich abdeckt.

[Schrompf]

Ach, stimmt. Ich habe die Vorbereitung der Zahl bislang übersehen. Damit passt's immer, denke ich.

Ist es denn wirklich schneller als ein static_cast von (zahl * 255.0f + 0.5f)?

[Krishty]

Ist es denn wirklich schneller als ein static_cast von (zahl * 255.0f + 0.5f)?

Theoretisch schon, praktisch müsste man das mit dem Pointer-Aliasing benchen … vom Assembler-Code ist sicher, dass er 10- bis 20× so schnell wie ein static_cast ist, darum brauche ich es unbedingt implementiert.

Ja das geht, externe Module zu nehmen. Aber damit bekommst Du normalerweise den Funktionsaufruf-Overhead mit, der fuer einen 2Zeiler dann doch erheblich ist. Ich weiss nicht, wie gut LTCG funktioniert, um das abzufangen und ob du dann am Ende nicht genauso langsam dastehst.

Ich brauche die Funktion in einer statischen Bibliothek, da ist LTGC immer so eine Sache …

Aus dem Kopf weiss ich auch nicht, ob fastcall in x64 funktioniert, und wo die float-Parameter liegen. Wenn Du Pech hast, sind die in den SSE-Registern, da die FPU eh optional ist, dann musst Du noch umstaendlich rumkopieren.

Das ist das Nächste …

Brauchst Du wirklich round-to-nearest Verhalten?

Definitiv - mir fällt eigentlich, von Ganzzahlarithmetik abgesehen, keine Situation ein, in der Abschneiden round-to-nearest vorzuziehen wäre …


Ich sehe schon, heute kommt ein Tag voll Benchmarking auf mich zu.

[Krishty]

So, die ersten Benchmarks unter x86 … einzelner Core-2-Quad-Kern mit 2.4 Ghz, 128 Mi Floats zu Ints, Visual C++ 2008 mit allen Optimierungen:

Konvertierung zu 8-Bit-Ints (Rundung mit Skalierung auf 255):
static_cast: 2,24117 s
Bitshift: 2,22062 s (= 100,9% Speed)
Assembler: 0,0911915 s (= 24.576,5% Speed)

Rundung zu 32-Bit-signed-Ints (also die „echte“ Rundung):
static_cast: 1,87883 s
Assembler: 0,0794671 s (= 23.642,9% Speed)

Die Bitschieberei ist also quasi kein Gewinn … auch wenn ich davon überzeugt bin, dass sich das in der RGBA-Situation ein bisschen wendet, weil bei static_cast ein paar zusätzliche Shifts anfallen … aber bewegend dürfte es nicht sein. Assembler ist immer mindestens 23× so schnell … ich will das!

x64-Ergebnisse kommen in den nächsten Tagen, wenn alles implementiert ist.

[Schrompf]

Wow, will haben! Pack's in eine kleine Funktion und mach einen dicken Kommentar drumrum, dass das im Falle einer Portierung geändert werden muss, dann hast Du nach meiner Meinung ausreichend Portabilität erreicht :-) Man sollte sich bei all diesen Überlegungen halt auch mal vor Auge halten, wer denn am Ende den Source wirklich mal in die Hand bekommt und auf welchen Compilern/Systemen der dann übersetzt werden soll. Wenn man da ehrlich zu sich selbst ist, ist bei 90% der Leute die Antwort: ein Rechner. Nämlich der eigene. Von daher: Portabilität wird allgemein überbewertet.

In Deinem Fall ist die Sache wohl kniffliger, weil Du tatsächlich selbst die 64Bit-Variante brauchst. In dem Fall musst Du wirklich weitersuchen. Ich würde mich dagegen freuen, wenn Du einfach mal Deinen bisherigen 32Bit-Inline-ASM-Code posten könntest... zu ähh... Lernzwecken :-)

Bye, Thomas

[kimmi]

Zum Thema Portabilität: bei privaten Projekten stimme ich Schrompf voll zu.
Bei beruflich motivierten Projekten: Ich habe schon unzähliche Überstunden geschoben, weil jemand Portabilität auf die zu leichte Schulter genommen hat und ein Compilerwechsel von x.00x auf x.00x+1 unerklärbare Abstürze provozierte :) . Also bitte beruflich zumindest mehr als einmal drüber nachdenken, danke ;) . Eure Nachfolger werden es euch danken.
Und ja, ich weiß, gehörte nicht zum Thema.

Gruß Kimmi

[Schrompf]

Öhm... ich rede von Compile-Time-Fehlern, die die zu portierenden Funktionen auf einem anderen System werfen sollten. Fehler zur Laufzeit sind unbedingt zu vermeiden. Im einfachsten Fall packt man einfach ein Boost-StaticAssert in die entsprechende Funktion, um Compiler und Prozessorarchitektor zu verifizieren, für die der Inline-ASM gedacht ist.

[kimmi]

Und ich rede von Laufzeitfehlern, die aufgrund einer schlecht portierten Funktion / Methode entstanden sind, da jemand leider keine StaticAsserts um besagte Stelle gebaut hat. Gerade beim Erben von Legacy-Code habe ich derartige Probleme schon oft miterleben dürfen ( bei Compilerwechsel, Systemwechsel, OS-Wechsel, auch gern mal Wetterwechsel ;) ). Nicht jeder geht da so bewußt ran wie Schrompf :(.

Gruß Kimmi

[Krishty]

Ich würde mich dagegen freuen, wenn Du einfach mal Deinen bisherigen 32Bit-Inline-ASM-Code posten könntest... zu ähh... Lernzwecken :-)

Gern, hier ist er. Ich habe einfach mal Referenzen statt einem Rückgabewert benutzt, weil das für die Benchmarks wahrscheinlich vorteilhaft ist:

Code: Alles auswählen

inline void RoundSingle(const float & p_Source, signed int & p_Dest) {
	__asm fld p_Source
	__asm mov edx, p_Dest
	__asm FRNDINT
	__asm fistp dword ptr [edx];
}

Und was zum Lernen dazu: Die FPU arbeitet standardmäßig im Modus "round" (weil die Rechenergebnisse dann am nächsten an den mathematisch richtigen Ergebnissen liegen). Führt man einen static_cast<signed int>() durch, wird ftoi() aufgerufen. Diese speichert den aktuellen FPU-Modus, flusht alle Anweisungen, setzt den Modus auf "chop" (Abschneiden der Nachkommastellen), konvertiert die float zur signed int, stellt den zuvor gespeicherten Modus wieder her und fährt dann fort ... darum ist er so langsam, eine komplette Verschwendung wenn man eh runden möchte.
The Code Project bietet einen guten Artikel mit Haufen von nützlichen Float-Utilities, dort habe ich auch die Funktion her (die gibt es aber im Netz an jeder Ecke).

[kimmi]

Da sag ich ebenfalls Danke! Und der Link beinhaltet einiges sehr interessantes Zeug.

Gruß Kimmi

[Krishty]

Ähm, eine Frage am Rande … ich habe ja nicht viel Assembler-Erfahrung …

Ich habe die Funktion jetzt so umgebaut, dass sie einen Rückgabewert hat (signed int RoundSingle(float p_Value)). Da die Funktion keine lokalen Variablen benötigt und keine großen Parameter handhabt, habe ich sie __declspec(naked) gemacht und die Aufrufmethode __fastcall gewählt.

Darum meine Frage an die Experten: Ist das akzeptabler Stil? Werden „nackte“ Funktionen auch von anderen Compilern als VCpp unterstützt? Habe ich irgendwelche Probleme zu erwarten?

[kimmi]

Wenn ich die Postings von der gcc-ML richtig verstanden habe, unterstützen die ein __attribute__((naked)) , welches aber nicht auf allen Plattformen unterstützt wird: http://www.mailinglistarchive.com/gcc-h ... 08166.html
Müsste man mal probieren bzw. auf jemanden warten, der das genauer weiß als ich :-).

Gruß Kimmi

[Krishty]

Stimmt, auf x86 bspw. ist es ungültig und wird es wohl auch immer bleiben. Ich sehe aber gerade, dass ich scheinbar kein naked mehr angeben muss, wenn ich die Funktion in einer externen Datei assembliere – was ich der x64-Kompatibilität wegen ja sowieso machen muss.

Momentan habe ich aber noch Probleme mit MASM, ich melde mich zurück, wenn es funktioniert.

[Jörg]

Wozu frndint in der Funktion? fistp allein rundet auch....

[Krishty]

Nicht immer … zumindest nicht immer auf der Pentium-FPU :D

[Jörg]

Oh, das wuerde mich sehr erstaunen, in welchen Faellen unterscheidet sich fistp von frndint im Rundungsverhalten?

[Krishty]

Laut dem Artikel käme bei 65535.5 das Ergebnis 0 statt 65536 raus, wenn man frndint nicht explizit voran stellte.
Das ist ein Bug im Pentium-Prozessor, genau wie diese leidige fdiv-Sache damals … eigentlich ewig her und man könnte es weglassen … nur weiß man ja nie, worauf ihr den Code ausführt.

[Jörg]

Wenn ich das richtig lese, kannst du das ignorieren, da du fuer das Auftreten eh den Wertebereich der Ziels ueberschreiten musst.
http://support.microsoft.com/kb/126455/en-us

[Krishty]

Stimmt :)