Gleitkomma-gegen-Ganzzahl-Berechnungen auf moderner Hardware

Question

Ich mache einige leistungskritische Arbeit in C++, und wir verwenden derzeit Ganzzahlberechnungen für Probleme, die von Natur aus Gleitkomma sind, weil "es ist schneller". Dies verursacht eine Menge ärgerlicher Probleme und fügt eine Menge ärgerlichen Codes hinzu.

Jetzt erinnere ich mich, dass ich gelesen habe, wie langsam Gleitkommaberechnungen ungefähr in den 386 Tagen waren, in denen ich glaube (IIRC), dass es einen optionalen Co-Prozessor gab. Aber heutzutage macht es bei exponentiell komplexeren und leistungsstärkeren CPUs keinen Unterschied in der "Geschwindigkeit", ob es sich um Gleitkomma- oder Ganzzahlberechnungen handelt? Zumal die tatsächliche Rechenzeit im Vergleich zu einem Pipeline-Stillstand oder dem Abrufen von Daten aus dem Hauptspeicher winzig ist?

Ich weiß, dass die richtige Antwort darin besteht, ein Benchmarking auf der Zielhardware durchzuführen. Was wäre ein guter Weg, um dies zu testen? Ich habe zwei kleine C++ - Programme geschrieben und ihre Laufzeit mit "time" unter Linux verglichen, aber die tatsächliche Laufzeit ist zu variabel (hilft nicht, wenn ich auf einem virtuellen Server arbeite). Ich verbringe nicht den ganzen Tag damit, Hunderte von Benchmarks durchzuführen, Diagramme zu erstellen usw. Kann ich etwas tun, um einen vernünftigen Test der relativen Geschwindigkeit zu erhalten? Irgendwelche Ideen oder Gedanken? Liege ich völlig falsch

Die Programme, die ich wie folgt verwendet habe, sind in keiner Weise identisch:

#include <iostream> #include <cmath> #include <cstdlib> #include <time.h> int main( int argc, char** argv ) { int accum = 0; srand( time( NULL ) ); for( unsigned int i = 0; i < 100000000; ++i ) { accum += Rand( ) % 365; } std::cout << accum << std::endl; return 0; }

Programm 2:

#include <iostream> #include <cmath> #include <cstdlib> #include <time.h> int main( int argc, char** argv ) { float accum = 0; srand( time( NULL ) ); for( unsigned int i = 0; i < 100000000; ++i ) { accum += (float)( Rand( ) % 365 ); } std::cout << accum << std::endl; return 0; }

Danke im Voraus!

Bearbeiten: Die Plattform, die mir am Herzen liegt, ist normales x86 oder x86-64, das auf Linux- und Windows-Desktop-Computern ausgeführt wird.

Edit 2 (eingefügt von einem Kommentar unten): Wir haben derzeit eine umfangreiche Codebasis. Wirklich bin ich auf die Verallgemeinerung gestoßen, dass wir "Float nicht verwenden dürfen, da die Ganzzahlberechnung schneller ist" - und ich suche nach einem Weg (wenn dies überhaupt zutrifft), um diese verallgemeinerte Annahme zu widerlegen. Mir ist klar, dass es unmöglich ist, das genaue Ergebnis für uns vorherzusagen, wenn wir nicht die ganze Arbeit erledigen und danach ein Profil erstellen.

Trotzdem vielen Dank für all Ihre hervorragenden Antworten und Ihre Hilfe. Fühlen Sie sich frei, etwas anderes hinzuzufügen :).

Dan · Accepted Answer

Leider kann ich dir nur eine "es kommt darauf an" Antwort geben ...

Nach meiner Erfahrung gibt es viele, viele Variablen für die Leistung ... insbesondere zwischen Ganzzahl- und Gleitkomma-Mathematik. Es variiert stark von Prozessor zu Prozessor (auch innerhalb derselben Familie wie x86), da verschiedene Prozessoren unterschiedliche "Pipeline" -Längen haben. Außerdem sind einige Operationen im Allgemeinen sehr einfach (wie das Hinzufügen) und haben eine beschleunigte Route durch den Prozessor, während andere (wie das Teilen) viel, viel länger dauern.

Die andere große Variable ist, wo sich die Daten befinden. Wenn Sie nur wenige Werte hinzufügen müssen, können sich alle Daten im Cache befinden, wo sie schnell an die CPU gesendet werden können. Eine sehr, sehr langsame Gleitkommaoperation, bei der sich die Daten bereits im Cache befinden, ist um ein Vielfaches schneller als eine Ganzzahloperation, bei der eine Ganzzahl aus dem Systemspeicher kopiert werden muss.

Ich gehe davon aus, dass Sie diese Frage stellen, weil Sie an einer leistungskritischen Anwendung arbeiten. Wenn Sie für die x86-Architektur entwickeln und zusätzliche Leistung benötigen, sollten Sie die SSE) -Erweiterungen in Betracht ziehen. Dies kann die Gleitkomma-Arithmetik mit einfacher Genauigkeit erheblich beschleunigen Die Operation kann für mehrere Daten gleichzeitig ausgeführt werden. Außerdem gibt es eine separate * Registerbank für die Operationen SSE). (In Ihrem zweiten Beispiel haben Sie "float" anstelle von "double" verwendet.) , was mich glauben lässt, dass Sie Mathematik mit einfacher Genauigkeit verwenden).

* Hinweis: Die Verwendung der alten MMX-Befehle würde Programme verlangsamen, da diese alten Befehle tatsächlich dieselben Register wie die FPU verwendeten, so dass es unmöglich ist, sowohl die FPU als auch MMX gleichzeitig zu verwenden.

vladr · Answer

Zum Beispiel (kleinere Zahlen sind schneller),

64-Bit Intel Xeon X5550 bei 2,67 GHz, gcc 4.1.2 -O3

short add/sub: 1.005460 [0] short mul/div: 3.926543 [0] long add/sub: 0.000000 [0] long mul/div: 7.378581 [0] long long add/sub: 0.000000 [0] long long mul/div: 7.378593 [0] float add/sub: 0.993583 [0] float mul/div: 1.821565 [0] double add/sub: 0.993884 [0] double mul/div: 1.988664 [0]

32-Bit-AMD Opteron ™ -Doppelkernprozessor 265 bei 1,81 GHz, gcc 3.4.6 -O3

short add/sub: 0.553863 [0] short mul/div: 12.509163 [0] long add/sub: 0.556912 [0] long mul/div: 12.748019 [0] long long add/sub: 5.298999 [0] long long mul/div: 20.461186 [0] float add/sub: 2.688253 [0] float mul/div: 4.683886 [0] double add/sub: 2.700834 [0] double mul/div: 4.646755 [0]

Wie Dan wies darauf hin , selbst wenn Sie die Taktfrequenz normalisieren (was bei Pipeline-Designs in sich selbst irreführend sein kann), variieren die Ergebnisse stark je nach CPU-Architektur (individuell ALU / FPU Leistung , sowie tatsächliche Anzahl von ALUs/FPUs Verfügbar pro Kern in superskalar Designs, die beeinflussen, wie viele nabhängige Operationen können parallel ausgeführt werden - Letzterer Faktor wird vom unten stehenden Code nicht ausgeübt, da alle Operationen nacheinander ausgeführt werden abhängig.)

FPU/ALU-Operationsbenchmark des armen Mannes:

#include <stdio.h> #ifdef _WIN32 #include <sys/timeb.h> #else #include <sys/time.h> #endif #include <time.h> #include <cstdlib> double mygettime(void) { # ifdef _WIN32 struct _timeb tb; _ftime(&tb); return (double)tb.time + (0.001 * (double)tb.millitm); # else struct timeval tv; if(gettimeofday(&tv, 0) < 0) { perror("oops"); } return (double)tv.tv_sec + (0.000001 * (double)tv.tv_usec); # endif } template< typename Type > void my_test(const char* name) { Type v = 0; // Do not use constants or repeating values // to avoid loop unroll optimizations. // All values >0 to avoid division by 0 // Perform ten ops/iteration to reduce // impact of ++i below on measurements Type v0 = (Type)(Rand() % 256)/16 + 1; Type v1 = (Type)(Rand() % 256)/16 + 1; Type v2 = (Type)(Rand() % 256)/16 + 1; Type v3 = (Type)(Rand() % 256)/16 + 1; Type v4 = (Type)(Rand() % 256)/16 + 1; Type v5 = (Type)(Rand() % 256)/16 + 1; Type v6 = (Type)(Rand() % 256)/16 + 1; Type v7 = (Type)(Rand() % 256)/16 + 1; Type v8 = (Type)(Rand() % 256)/16 + 1; Type v9 = (Type)(Rand() % 256)/16 + 1; double t1 = mygettime(); for (size_t i = 0; i < 100000000; ++i) { v += v0; v -= v1; v += v2; v -= v3; v += v4; v -= v5; v += v6; v -= v7; v += v8; v -= v9; } // Pretend we make use of v so compiler doesn't optimize out // the loop completely printf("%s add/sub: %f [%d]
", name, mygettime() - t1, (int)v&1); t1 = mygettime(); for (size_t i = 0; i < 100000000; ++i) { v /= v0; v *= v1; v /= v2; v *= v3; v /= v4; v *= v5; v /= v6; v *= v7; v /= v8; v *= v9; } // Pretend we make use of v so compiler doesn't optimize out // the loop completely printf("%s mul/div: %f [%d]
", name, mygettime() - t1, (int)v&1); } int main() { my_test< short >("short"); my_test< long >("long"); my_test< long long >("long long"); my_test< float >("float"); my_test< double >("double"); return 0; }

Ben Voigt · Answer

Es ist wahrscheinlich, dass es einen signifikanten Unterschied in der realen Geschwindigkeit zwischen Festkomma- und Gleitkomma-Mathematik gibt, aber der theoretische Best-Case-Durchsatz von ALU und FPU ist völlig irrelevant. Stattdessen die Anzahl der Ganzzahl- und Gleitkommaregister (echte Register, keine Registernamen) in Ihrer Architektur, die von Ihrer Berechnung nicht anderweitig verwendet werden (z. B. für die Schleifensteuerung), die Anzahl der Elemente jedes Typs, die in eine Cache-Zeile passen , Optimierungen möglich unter Berücksichtigung der unterschiedlichen Semantik für Ganzzahl vs. Gleitkomma-Mathematik - diese Effekte werden dominieren. Die Datenabhängigkeiten Ihres Algorithmus spielen hier eine wichtige Rolle, sodass kein allgemeiner Vergleich die Leistungslücke Ihres Problems vorhersagt.

Beispielsweise ist die Ganzzahladdition kommutativ. Wenn der Compiler eine Schleife sieht, wie Sie sie für einen Benchmark verwendet haben (vorausgesetzt, die Zufallsdaten wurden im Voraus vorbereitet, um die Ergebnisse nicht zu verfälschen), kann er die Schleife abrollen und Teilsummen mit berechnen Keine Abhängigkeiten. Fügen Sie diese dann hinzu, wenn die Schleife beendet wird. Bei Gleitkommazahlen muss der Compiler die Operationen jedoch in der von Ihnen angeforderten Reihenfolge ausführen (Sie haben Sequenzpunkte, damit der Compiler das gleiche Ergebnis erzielen kann, was eine Neuanordnung nicht zulässt), sodass jede Addition von stark abhängig ist das Ergebnis des vorherigen.

Es ist wahrscheinlich, dass Sie gleichzeitig mehr ganzzahlige Operanden in den Cache einfügen. Daher kann die Festkommaversion die Float-Version sogar auf einer Maschine mit theoretisch höherem Durchsatz um eine Größenordnung übertreffen.

Potatoswatter · Answer

Das Hinzufügen ist viel schneller als Rand, daher ist Ihr Programm (besonders) nutzlos.

Sie müssen Leistungs-Hotspots identifizieren und Ihr Programm schrittweise ändern. Es hört sich so an, als hätten Sie Probleme mit Ihrer Entwicklungsumgebung, die zuerst behoben werden müssen. Ist es unmöglich, Ihr Programm für ein kleines Problem auf Ihrem PC auszuführen?

Im Allgemeinen ist der Versuch, FP Jobs mit Integer-Arithmetik auszuführen, ein Rezept für Slow.

MrMesees · Answer

Bis dies variiert (sehr). Hier sind einige Ergebnisse, die mit dem Gnu-Compiler erzielt wurden (übrigens habe ich auch durch Kompilieren auf Maschinen überprüft, Gnu G ++ 5.4 von Xenial ist verdammt viel schneller als 4.6.3 von Linaro).

Intel i7 4700MQ xenial

short add: 0.822491 short sub: 0.832757 short mul: 1.007533 short div: 3.459642 long add: 0.824088 long sub: 0.867495 long mul: 1.017164 long div: 5.662498 long long add: 0.873705 long long sub: 0.873177 long long mul: 1.019648 long long div: 5.657374 float add: 1.137084 float sub: 1.140690 float mul: 1.410767 float div: 2.093982 double add: 1.139156 double sub: 1.146221 double mul: 1.405541 double div: 2.093173

Intel i3 2370M hat ähnliche Ergebnisse

short add: 1.369983 short sub: 1.235122 short mul: 1.345993 short div: 4.198790 long add: 1.224552 long sub: 1.223314 long mul: 1.346309 long div: 7.275912 long long add: 1.235526 long long sub: 1.223865 long long mul: 1.346409 long long div: 7.271491 float add: 1.507352 float sub: 1.506573 float mul: 2.006751 float div: 2.762262 double add: 1.507561 double sub: 1.506817 double mul: 1.843164 double div: 2.877484

Intel (R) Celeron (R) 2955U (Acer C720 Chromebook mit xenial)

short add: 1.999639 short sub: 1.919501 short mul: 2.292759 short div: 7.801453 long add: 1.987842 long sub: 1.933746 long mul: 2.292715 long div: 12.797286 long long add: 1.920429 long long sub: 1.987339 long long mul: 2.292952 long long div: 12.795385 float add: 2.580141 float sub: 2.579344 float mul: 3.152459 float div: 4.716983 double add: 2.579279 double sub: 2.579290 double mul: 3.152649 double div: 4.691226

DigitalOcean 1 GB Droplet Intel (R) Xeon (R) CPU E5-2630L v2 (vertrauenswürdig)

short add: 1.094323 short sub: 1.095886 short mul: 1.356369 short div: 4.256722 long add: 1.111328 long sub: 1.079420 long mul: 1.356105 long div: 7.422517 long long add: 1.057854 long long sub: 1.099414 long long mul: 1.368913 long long div: 7.424180 float add: 1.516550 float sub: 1.544005 float mul: 1.879592 float div: 2.798318 double add: 1.534624 double sub: 1.533405 double mul: 1.866442 double div: 2.777649

AMD Opteron (tm) Prozessor 4122 (präzise)

short add: 3.396932 short sub: 3.530665 short mul: 3.524118 short div: 15.226630 long add: 3.522978 long sub: 3.439746 long mul: 5.051004 long div: 15.125845 long long add: 4.008773 long long sub: 4.138124 long long mul: 5.090263 long long div: 14.769520 float add: 6.357209 float sub: 6.393084 float mul: 6.303037 float div: 17.541792 double add: 6.415921 double sub: 6.342832 double mul: 6.321899 double div: 15.362536

Dies verwendet Code von http://Pastebin.com/Kx8WGUfg als benchmark-pc.c

g++ -fpermissive -O3 -o benchmark-pc benchmark-pc.c

Ich habe mehrere Durchgänge ausgeführt, aber dies scheint der Fall zu sein, dass die allgemeinen Zahlen gleich sind.

Eine bemerkenswerte Ausnahme scheint ALU mul vs FPU mul zu sein. Addition und Subtraktion scheinen trivial verschieden zu sein.

Hier ist das obige in Diagrammform (klicken Sie für volle Größe, niedriger ist schneller und vorzuziehen):

Aktualisieren Sie, um @Peter Cordes unterzubringen

https://Gist.github.com/Lewiscowles1986/90191c59c9aedf3d08bf0b129065cccc

 short add: 0.773049 short sub: 0.789793 short mul: 0.960152 short div: 3.273668 int add: 0.837695 int sub: 0.804066 int mul: 0.960840 int div: 3.281113 long add: 0.829946 long sub: 0.829168 long mul: 0.960717 long div: 5.363420 long long add: 0.828654 long long sub: 0.805897 long long mul: 0.964164 long long div: 5.359342 float add: 1.081649 float sub: 1.080351 float mul: 1.323401 float div: 1.984582 double add: 1.081079 double sub: 1.082572 double mul: 1.323857 double div: 1.968488

 short add: 1.235603 short sub: 1.235017 short mul: 1.280661 short div: 5.535520 int add: 1.233110 int sub: 1.232561 int mul: 1.280593 int div: 5.350998 long add: 1.281022 long sub: 1.251045 long mul: 1.834241 long div: 5.350325 long long add: 1.279738 long long sub: 1.249189 long long mul: 1.841852 long long div: 5.351960 float add: 2.307852 float sub: 2.305122 float mul: 2.298346 float div: 4.833562 double add: 2.305454 double sub: 2.307195 double mul: 2.302797 double div: 5.485736

 short add: 1.040745 short sub: 0.998255 short mul: 1.240751 short div: 3.900671 int add: 1.054430 int sub: 1.000328 int mul: 1.250496 int div: 3.904415 long add: 0.995786 long sub: 1.021743 long mul: 1.335557 long div: 7.693886 long long add: 1.139643 long long sub: 1.103039 long long mul: 1.409939 long long div: 7.652080 float add: 1.572640 float sub: 1.532714 float mul: 1.864489 float div: 2.825330 double add: 1.535827 double sub: 1.535055 double mul: 1.881584 double div: 2.777245

jcoder · Answer

Zwei Punkte zu beachten -

Moderne Hardware kann Befehle überlappen, parallel ausführen und neu anordnen, um die Hardware optimal zu nutzen. Und jedes signifikante Gleitkommaprogramm hat wahrscheinlich auch eine signifikante Ganzzahl-Arbeit, selbst wenn es nur Indizes in Arrays, Schleifenzähler usw. berechnet. Selbst wenn Sie also einen langsamen Gleitkomma-Befehl haben, läuft es möglicherweise auf einem separaten Hardwarebit überlappt mit einem Teil der Integer-Arbeit. Mein Punkt ist, dass, selbst wenn die Gleitkomma-Anweisungen langsamer als die ganzzahligen sind, Ihr Gesamtprogramm möglicherweise schneller ausgeführt wird, da es mehr von der Hardware verwenden kann.

Wie immer ist die einzige Möglichkeit, sicher zu sein, Ihr aktuelles Programm zu profilieren.

Der zweite Punkt ist, dass die meisten CPUs heutzutage SIMD-Anweisungen für Gleitkommazahlen haben, die mit mehreren Gleitkommazahlen gleichzeitig arbeiten können. Zum Beispiel können Sie 4 Floats in ein einzelnes SSE Register laden und 4 Multiplikationen für alle parallel ausführen. Wenn Sie Teile Ihres Codes so umschreiben können, dass SSE -Anweisungen verwendet werden, ist dies wahrscheinlich schneller als eine Ganzzahl-Version. Visual C++ bietet dazu eigene Compilerfunktionen. Weitere Informationen finden Sie unter http://msdn.Microsoft.com/en-us/library/x5c07e2a (v = VS.80) .aspx .

Artem Sokolov · Answer

Wenn Sie keinen Code schreiben, der millionenfach pro Sekunde aufgerufen wird (wie z. B. Zeichnen einer Linie auf dem Bildschirm in einer Grafikanwendung), ist die Arithmetik zwischen Ganzzahl und Gleitkomma selten der Engpass.

Der übliche erste Schritt zu den Effizienzfragen besteht darin, Ihren Code zu profilieren, um festzustellen, wo die Laufzeit wirklich verbracht wird. Der Linux-Befehl dafür ist gprof.

Bearbeiten:

Ich nehme an, Sie können den Strichzeichnungsalgorithmus immer mit Ganzzahlen und Gleitkommazahlen implementieren. Rufen Sie ihn jedoch häufig auf und prüfen Sie, ob er einen Unterschied macht:

http://en.wikipedia.org/wiki/Bresenham's_algorithm

gnasher729 · Answer

Ganzzahloperationen sind heutzutage in der Regel etwas schneller als Gleitkommaoperationen. Wenn Sie also mit den gleichen Operationen in Ganzzahl und Gleitkommazahl rechnen können, verwenden Sie Ganzzahl. JEDOCH SIE SAGEN "Dies verursacht eine Menge ärgerlicher Probleme und fügt eine Menge ärgerlichen Codes hinzu". Das hört sich so an, als ob Sie mehr Operationen benötigen, da Sie anstelle von Gleitkommazahlen eine Ganzzahl-Arithmetik verwenden. In diesem Fall wird Gleitkomma schneller ausgeführt, weil

sobald Sie mehr Ganzzahloperationen benötigen, benötigen Sie wahrscheinlich viel mehr, sodass der leichte Geschwindigkeitsvorteil durch die zusätzlichen Operationen mehr als aufgezehrt wird
der Fließkomma-Code ist einfacher, was bedeutet, dass der Code schneller geschrieben werden kann. Wenn dies geschwindigkeitskritisch ist, können Sie mehr Zeit für die Optimierung des Codes aufwenden.

Goran D · Answer

Die Gleitkomma-Version ist viel langsamer, wenn keine Restoperation ausgeführt wird. Da alle Adds sequentiell sind, kann die CPU die Summation nicht parallelisieren. Die Latenz ist kritisch. Die FPU-Add-Latenz beträgt normalerweise 3 Zyklen, während die Ganzzahl-Addition 1 Zyklus beträgt. Der Teiler für den Restbetreiber wird jedoch wahrscheinlich der kritische Teil sein, da er bei modernen CPUs nicht vollständig in die Pipeline integriert ist. Unter der Annahme, dass der Divisions-/Restbefehl den größten Teil der Zeit in Anspruch nimmt, ist der Unterschied aufgrund der zusätzlichen Latenz gering.

dan04 · Answer

Ich habe einen Test durchgeführt, bei dem anstelle von Rand () 1 zur Zahl hinzugefügt wurde. Ergebnisse (auf einem x86-64) waren:

kurz: 4.260s
int: 4.020s
lang lang: 3.350s
float: 7.330s
double: 7.210s