webentwicklung-frage-antwort-db.com.de

Was ist der schnellste Weg, um den absoluten Wert einer Zahl zu erhalten

Was ist der schnellste Weg, eine Operation zu implementieren, die den absoluten Wert einer Zahl zurückgibt?

x=root(x²)

oder

if !isPositive(x):
    x=x*(-1)

Eigentlich kann diese Frage als übersetzt werden, wie schnell ein if ist (und warum bitte).

Meine College-Programmierprofessoren haben mir immer empfohlen, ifs zu vermeiden, da sie extrem langsam sind, aber ich habe immer vergessen zu fragen, wie langsam und warum. Weiß jemand hier?

37
Diones

Conditionals sind langsamer als einfache arithmetische Operationen, aber viel, viel schneller als etwas so Dummes wie die Quadratwurzel berechnen.

Faustregeln aus meinen Assembly-Tagen:

  • Ganzzahl oder bitweise Op: 1 Zyklus
  • Fließkommazahl/Sub/Mul: 4 Zyklen
  • Gleitpunkt div: ~ 30 Zyklen
  • Gleitpunktexponentiation: ~ 200 Zyklen
  • Fließkommazahl: ~ 60 Zyklen je nach Implementierung
  • Bedingter Zweig: Durchschn. 10 Zyklen, besser wenn gut vorhergesagt, viel schlechter, wenn falsch vorhergesagt
57
kquinn

Es gibt einen großartigen Trick, um den absoluten Wert einer 2s-Komplement-Ganzzahl zu berechnen, ohne eine if-Anweisung zu verwenden. Die Theorie besagt, wenn der Wert negativ ist, möchten Sie die Bits umschalten und eins hinzufügen, ansonsten möchten Sie die Bits unverändert weitergeben. Ein XOR 1 schaltet A um, und A XOR 0 bewirkt, dass A intakt bleibt. Du willst also so etwas machen:

  uint32_t temp = value >> 31;     // make a mask of the sign bit
  value ^= temp;                   // toggle the bits if value is negative
  value += temp & 1;               // add one if value was negative

Im Prinzip können Sie dies in nur drei Montageanweisungen (ohne Verzweigung) tun. Und Sie möchten gerne denken, dass die Funktion abs (), die Sie mit math.h erhalten, dies optimal tut.

Keine Branchen == bessere Leistung. Im Gegensatz zu der obigen Antwort von @ paxdiablo ist dies in tiefen Pipelines wirklich wichtig. Je mehr Verzweigungen Sie in Ihrem Code haben, desto wahrscheinlicher ist es, dass der Verzweigungsvorhersager falsch ist und zurückrollt. Wenn Sie also nicht verzweigen, wo Möglicherweise bewegen sich die Dinge in Ihrem Kern auf Hochtouren :).

73
vicatcu

Ugh, haben dir deine Lehrer das tatsächlich gesagt? Die Regel, die den meisten Leuten folgt, besteht darin, Ihren Code zuerst lesbar zu machen und dann etwaige Leistungsprobleme zu optimieren nachdem sie sich als tatsächlich probleme erwiesen haben. In 99,999% der Fälle werden Sie nie ein Leistungsproblem sehen, da Sie zu viele if-Anweisungen verwendet haben. Knuth sagte es am besten , "vorzeitige Optimierung ist die Wurzel allen Übels".

26
Ed S.

Die Berechnung der Quadratwurzel ist wahrscheinlich eine der schlimmsten Dinge, die Sie tun können, weil sie sehr langsam ist. Normalerweise gibt es dafür eine Bibliotheksfunktion. so etwas wie Math.Abs ​​(). Eine Multiplikation mit -1 ist ebenfalls nicht erforderlich. Gib einfach -x zurück. Eine gute Lösung wäre also die folgende.

(x >= 0) ? x : -x

Der Compiler wird dies wahrscheinlich auf eine einzige Anweisung optimieren. Bei modernen Prozessoren können die Bedingungen wegen der langen Ausführungspipelines recht teuer sein. Die Berechnungen müssen verworfen werden, wenn eine Verzweigung nicht vorhergesagt wurde und der Prozessor mit der Ausführung der Anweisungen aus dem falschen Codepfad begann. Aber wegen der erwähnten Compiler-Optimierung brauchen Sie sich in diesem Fall nicht zu kümmern. 

11

Der Vollständigkeit halber können Sie dies für IEEE-Floats auf x86-Systemen in C++ tun:

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;
5
awdz9nld

Die Variable if ist fast sicher blind fast im Vergleich zur Quadratwurzel, da sie normalerweise auf der Ebene des Maschinencodes in eine bedingte Sprunganweisung übersetzt wird (nach der Auswertung des Ausdrucks, der komplex sein kann, aber nicht.) in diesem Fall ist es eine einfache Überprüfung für weniger als 0).

Es ist wahrscheinlich viel langsamer, die Quadratwurzel einer Zahl zu nehmen (zum Beispiel würde die Newton-Methode viele - viele if-Anweisungen auf Maschinencodeebene verwenden).

Die wahrscheinliche Quelle der Verwirrung ist die Tatsache, dass if immer zu einer nicht sequentiellen Änderung des Befehlszeigers führt. Dies kann Prozessoren verlangsamen, die Befehle vorab in eine Pipeline abrufen, da sie die Pipeline erneut auffüllen müssen, wenn sich die Adresse unerwartet ändert.

Die Kosten dafür wären jedoch im Vergleich zu einer Quadratwurzeloperation im Vergleich zu einem einfachen Prüfen und Negieren winzig.

4
paxdiablo

Was ist der schnellste Weg, um den absoluten Wert einer Zahl zu erhalten

Ich denke, die "richtige" Antwort ist eigentlich nicht hier. Der schnellste Weg, um die absolute Zahl zu erhalten, ist wahrscheinlich die Verwendung von Intel Intrinsic. Siehe https://software.intel.com/sites/landingpage/IntrinsicsGuide/ und suche nach 'vpabs' (oder einem anderen Intrinsic, der die Aufgabe für Ihre CPU erfüllt). Ich bin mir ziemlich sicher, dass es alle anderen Lösungen hier schlagen wird.

Wenn Sie Intrinsics nicht mögen (oder sie nicht verwenden können oder ...), möchten Sie vielleicht prüfen, ob der Compiler klug genug ist, um herauszufinden, ob ein Aufruf zum 'nativen absoluten Wert' (std::abs in C++ oder Math.Abs(x) in C #) erfolgt. wird sich automatisch in das Intrinsic umwandeln - im Grunde geht es darum, den disassemblierten (kompilierten) Code zu betrachten. Wenn Sie sich in einer JIT befinden, stellen Sie sicher, dass JIT-Optimierungen nicht deaktiviert sind.

Wenn Sie auch keine optimierten Anweisungen erhalten, können Sie die hier beschriebene Methode verwenden: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs .

3
atlaste

Die Modulo-Operation wird verwendet, um einen Rest zu finden. Sie meinen den absoluten Wert. Ich habe die Frage geändert, weil es sein sollte, wenn! Pos (x) dann x = x * -1 ist. (fehlte nicht) 

Ich würde mir keine Gedanken über die Effizienz einer if-Aussage machen. Konzentrieren Sie sich stattdessen auf die Lesbarkeit Ihres Codes. Wenn Sie feststellen, dass ein Effizienzproblem vorliegt, konzentrieren Sie sich auf die Profilerstellung Ihres Codes, um echte Engpässe zu finden.

Wenn Sie beim Codieren auf Effizienz achten möchten, müssen Sie sich nur um die Komplexität Ihrer Algorithmen kümmern. 

Wenn Anweisungen sehr effizient sind, wertet sie den Ausdruck aus und ändert dann einfach den Programmzähler basierend auf dieser Bedingung. Der Programmzähler speichert die Adresse des nächsten auszuführenden Befehls.

Multiplikation mit -1 und Überprüfen, ob ein Wert größer als 0 ist, kann auf eine einzige Assembly-Anweisung reduziert werden.

Das Finden der Wurzel einer Zahl und das Quadrieren dieser Zahl zuerst, ist definitiv mehr Operationen als das Wenn mit einer Negation. 

2
Brian R. Bondy

Die Zeit, die benötigt wird, um eine Quadratwurzel zu machen, ist viel länger als die Zeit, um eine Bedingung auszuführen. Wenn Sie gelernt haben, Bedingungen zu vermeiden, weil sie langsam sind, wurden Sie falsch informiert. Sie sind um einiges langsamer als triviale Operationen wie das Hinzufügen oder Subtrahieren von Ganzzahlen oder das Verschieben von Bits. Daher ist das Abrollen von Schleifen nur von Vorteil, wenn Sie solche trivialen Operationen ausführen. Aber im Großen sind die Bedingungen gut und schnell, nicht schlecht und langsam. Etwas so kompliziertes zu tun, wie eine Funktion aufzurufen oder eine Quadratwurzel zu berechnen, um eine bedingte Anweisung zu vermeiden, ist verrückt.

Warum sollten Sie statt (x = x * -1) (x = 0 - x) nicht tun? Vielleicht optimiert der Compiler sie gleich, aber ist der zweite überhaupt nicht einfacher?

1
thomasrutter

Verwenden Sie die 8086-Baugruppe? ;-)

                ; abs value of AX
   cwd          ; replicate the high bit into DX
   xor  ax, dx  ; take 1's complement if negative; no change if positive
   sub  ax, dx  ; AX is 2's complement if it was negative The standard
                : absolute value method works on any register but is much
                ; slower:

   or   bx, bx  ; see if number is negative
   jge  notneg  ; if it is negative...
   neg  bx      ; ...make it positive
notneg:         ; jump to here if positive

(eklatant gestohlen )

1
Mark Maxham

Wenn Sie lediglich die absoluten Werte von zwei Zahlen vergleichen (z. B. benötigen Sie nach dem Vergleich keinen absoluten Wert), müssen Sie nur die beiden Werte quadrieren, um beide Werte positiv zu machen (entfernen Sie das Vorzeichen jedes Werts), und das größere Quadrat wird angezeigt größer als das kleinere Quadrat.

0
Neoheurist

Was schneller ist, hängt stark davon ab, auf welchen Compiler und auf welche CPU Sie abzielen. Bei den meisten CPUs und allen Compilern ist x = (x> = 0)? x: -x; ist der schnellste Weg, um einen absoluten Wert zu erhalten, aber in der Tat bieten Standardfunktionen diese Lösung bereits an (z. B. fabs ()). Es wird in Compare, gefolgt von einer bedingten Zuweisungsanweisung (CMOV), nicht in einem bedingten Sprung kompiliert. Bei einigen Plattformen fehlt diese Anweisung. Allerdings würde der Compiler von Intel (aber nicht von Microsoft oder GCC) if () automatisch in eine bedingte Zuweisung konvertieren und sogar versuchen, die Zyklen (falls möglich) zu optimieren.

Verzweigungscode ist im Allgemeinen langsamer als die bedingte Zuweisung, wenn die CPU eine statistische Vorhersage verwendet. if () kann im Durchschnitt langsamer sein, wenn der Vorgang mehrmals wiederholt wird und sich das Ergebnis ständig ändert. CPUs wie Intel würden beginnen, both zu berechnen, und würden die ungültige ungültig machen. Bei großen if () - Körpern oder einer großen Anzahl von Zyklen, die möglicherweise kritisch sind.

sqr () und sqrt () auf modernen Intel-CPUs sind einzelne eingebaute Anweisungen und sind nicht langsam, aber sie sind ungenau und das Laden von Registern würde ebenfalls Zeit erfordern.

Verwandte Frage: Warum ist ein CPU-Verzweigungsbefehl langsam?

Am wahrscheinlichsten wollte der Professor, dass der Student in dieser Angelegenheit recherchiert, es ist eine semi-provokative Frage, die nur gut wäre, wenn der Student lernen würde, selbstständig zu denken und nach zusätzlichen Quellen zu suchen.

0

Ich mache einige Retro-Grafikprogrammierungen in C für 8088/8086, und der Aufruf von abs() ist zeitaufwendig, daher habe ich ihn ersetzt durch:

/* assuming 'i' is int; this WILL NOT WORK on floating point */
if (i < 0) {
    i = ~i + 1;
}

Der Grund dafür ist, dass dies schneller ist, weil es im Wesentlichen eine CALL in Assembly für eine JNE handelt. Durch Aufrufen einer Methode werden einige Register geändert, einige weitere verschoben, Argumente auf den Stapel gelegt und die Prefetch-Warteschlange geleert. Außerdem müssen diese Aktionen am Ende der Funktion rückgängig gemacht werden, was für die CPU sehr teuer ist.

0