wake-up-neo.com

Gleitkomma-gegen-Ganzzahl-Berechnungen auf moderner Hardware

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 :).

94
maxpenguin

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.

31
Dan

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]\n", 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]\n", 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;
}
48
vladr

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.

21
Ben Voigt

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.

18
Potatoswatter

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):

Chart of above data

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
14
MrMesees

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 .

7
jcoder

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

4
Artem Sokolov

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.

4
gnasher729

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.

4
Goran D

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
3
dan04