Was ist die schnellste ganzzahlige Division, die die Division durch Null unterstützt, unabhängig vom Ergebnis?
Lesezeit: 10 Minuten
Philipp
Zusammenfassung:
Ich suche den schnellsten Weg zur Berechnung
(int) x / (int) y
ohne eine Ausnahme für y==0. Stattdessen möchte ich nur ein willkürliches Ergebnis.
Hintergrund:
Beim Codieren von Bildverarbeitungsalgorithmen muss ich oft durch einen (kumulierten) Alpha-Wert dividieren. Die einfachste Variante ist reiner C-Code mit Integer-Arithmetik. Mein Problem ist, dass ich normalerweise einen Division-durch-Null-Fehler für Ergebnispixel bekomme alpha==0. Allerdings sind das genau die Pixel, bei denen das Ergebnis überhaupt keine Rolle spielt: Farbwerte von Pixeln mit sind mir egal alpha==0.
Einzelheiten:
Ich suche sowas wie:
result = (y==0)? 0 : x/y;
oder
result = x / MAX( y, 1 );
x und y sind positive ganze Zahlen. Der Code wird sehr oft in einer verschachtelten Schleife ausgeführt, daher suche ich nach einer Möglichkeit, die bedingte Verzweigung loszuwerden.
Wenn y den Bytebereich nicht überschreitet, bin ich mit der Lösung zufrieden
Aber das funktioniert offensichtlich nicht gut für größere Reichweiten.
Ich denke, die letzte Frage ist: Was ist der schnellste Bit-Twiddling-Hack, der 0 in einen anderen ganzzahligen Wert ändert, während alle anderen Werte unverändert bleiben?
Erläuterungen
Ich bin mir nicht 100% sicher, ob die Verzweigung zu teuer ist. Allerdings kommen unterschiedliche Compiler zum Einsatz, daher bevorzuge ich Benchmarking mit kleinen Optimierungen (was ja fragwürdig ist).
Sicherlich sind Compiler großartig, wenn es um Bit-Twiddling geht, aber ich kann das “egal”-Ergebnis nicht in C ausdrücken, sodass der Compiler niemals in der Lage sein wird, die volle Bandbreite an Optimierungen zu nutzen.
Code sollte vollständig C-kompatibel sein, Hauptplattformen sind Linux 64 Bit mit gcc & clang und MacOS.
Wie haben Sie festgestellt, dass der if-Zweig zu teuer ist?
– Djechlin
27. Mai 2013 um 16:56 Uhr
Wie hast du das da festgestellt ist ein Zweig?
– leemes
27. Mai 2013 um 16:57 Uhr
+1 für die Profilerstellung, mit der modernen Verzweigungsvorhersage benötigen Sie dies möglicherweise nicht. Ebenfalls, warum Programmieren Sie Ihre eigenen Bildverarbeitungsalgorithmen?
– TC1
27. Mai 2013 um 16:57 Uhr
“Was ist der schnellste Bittwiddling-Hack …” Vielleicht y += !y? Es ist kein Zweig erforderlich, um das zu berechnen. Du könntest vergleichen x / (y + !y) gegen x / max(y, 1) und vielleicht auch y ? (x/y) : 0. Ich denke, es wird in keinem von ihnen einen Zweig geben, zumindest wenn die Optimierungen aktiviert sind.
– leemes
27. Mai 2013 um 17:07 Uhr
Jeder, der denkt, dass die moderne Verzweigungsvorhersage bedeutet, dass Sie dies nicht tun müssen, hat nicht genügend Verzweigungseliminierungscode profiliert, der auf einer Per-Pixel-Ebene ausgeführt wird. Moderne Verzweigungsvorhersage ist akzeptabel, wenn das Alpha 0 Abschnitte sind riesig und zusammenhängend. Es gibt einen Platz zum Herumspielen mit Mikrooptimierungen und Operationen pro Pixel exakt diese Stelle.
– Yakk – Adam Nevraumont
27. Mai 2013 um 18:00 Uhr
Bryan Olivier
Inspiriert durch einige der Kommentare habe ich den Zweig auf meinem Pentium und losgeworden gcc Compiler verwenden
int f (int x, int y)
{
y += y == 0;
return x/y;
}
Der Compiler erkennt grundsätzlich, dass er im Zusatz ein Bedingungs-Flag des Tests verwenden kann.
Da sich herausstellte, dass dies eine so beliebte Frage und Antwort war, werde ich etwas näher darauf eingehen. Das obige Beispiel basiert auf einer Programmiersprache, die ein Compiler erkennt. Im obigen Fall wird ein boolescher Ausdruck in der Integralarithmetik verwendet, und die Verwendung von Bedingungsflags wird zu diesem Zweck in der Hardware erfunden. Im Allgemeinen sind Zustandsflags in C nur über die Verwendung von Idiom zugänglich. Aus diesem Grund ist es so schwierig, eine portable Integer-Bibliothek mit mehrfacher Genauigkeit in C zu erstellen, ohne auf (Inline-) Assemblierung zurückzugreifen. Ich vermute, dass die meisten anständigen Compiler die obige Redewendung verstehen werden.
Eine andere Möglichkeit, Verzweigungen zu vermeiden, ist, wie auch in einigen der obigen Kommentare erwähnt, die prädizierte Ausführung. Ich habe daher den ersten Code von Philipp und meinen Code genommen und ihn durch den Compiler von ARM und den GCC-Compiler für die ARM-Architektur laufen lassen, der über eine prädizierte Ausführung verfügt. Beide Compiler vermeiden die Verzweigung in beiden Codebeispielen:
Philipps Version mit dem ARM-Compiler:
f PROC
CMP r1,#0
BNE __aeabi_idivmod
MOVEQ r0,#0
BX lr
Alle Versionen benötigen noch einen Abzweig zur Divisionsroutine, da diese Version des ARM keine Hardware für eine Division hat, sondern den Test für y == 0 wird vollständig durch vorhergesagte Ausführung implementiert.
Können Sie uns den resultierenden Assembler-Code zeigen? Oder wie hast du festgestellt, dass es keine Verzweigung gibt?
– Haatschii
27. Mai 2013 um 17:15 Uhr
Genial. Kann gemacht werden constexpr und vermeiden Sie unnötige Typumwandlungen wie diese: template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); } Und wenn Sie möchten 255, (lhs)/(rhs+!rhs) & -!rhs
– Yakk – Adam Nevraumont
27. Mai 2013 um 18:08 Uhr
@leemes aber ich meinte | nicht &. Hoppla — ( (lhs)/(rhs+!rhs) ) | -!rhs sollte Ihren Wert auf setzen 0xFFFFFFF wenn rhs ist 0und lhs/rhs wenn rhs!=0.
– Yakk – Adam Nevraumont
27. Mai 2013 um 18:20 Uhr
Gute Antwort! Normalerweise greife ich für solche Dinge auf die Montage zurück, aber das ist immer schrecklich zu warten (ganz zu schweigen von weniger tragbar 😉 ).
– Löwe
28. Mai 2013 um 7:35 Uhr
Stellen Sie sicher, dass Sie einen Benchmark durchführen, bevor Sie dies tatsächlich verwenden – Verzweigungen, die gut vorhergesagt werden können, sind in modernen CPUs praktisch kostenlos, sodass Tricks zur Vermeidung von Verzweigungen die Leistung beeinträchtigen können. Vor allem, wenn es um schwere Operationen wie Division geht. +1 für die tolle Antwort.
– Cory Nelson
29. Mai 2013 um 15:59 Uhr
Hier sind einige konkrete Zahlen unter Windows mit GCC 4.7.2:
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned int result = 0;
for (int n = -500000000; n != 500000000; n++)
{
int d = -1;
for (int i = 0; i != ITERATIONS; i++)
d &= rand();
#if CHECK == 0
if (d == 0) result++;
#elif CHECK == 1
result += n / d;
#elif CHECK == 2
result += n / (d + !d);
#elif CHECK == 3
result += d == 0 ? 0 : n / d;
#elif CHECK == 4
result += d == 0 ? 1 : n / d;
#elif CHECK == 5
if (d != 0) result += n / d;
#endif
}
printf("%u\n", result);
}
Beachten Sie, dass ich absichtlich nicht anrufe srand()so dass rand() liefert immer genau die gleichen Ergebnisse. Beachten Sie auch das -DCHECK=0 zählt lediglich die Nullen, damit ersichtlich ist, wie oft sie vorkamen.
Nun, Kompilieren und Timing auf verschiedene Arten:
$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done
zeigt die Ausgabe, die in einer Tabelle zusammengefasst werden kann:
Wenn Nullen selten sind, werden die -DCHECK=2 Version schneidet schlecht ab. Wenn Nullen häufiger erscheinen, wird die -DCHECK=2 Gehäuse startet deutlich besser. Von den anderen Optionen gibt es wirklich keinen großen Unterschied.
Dort hat Check 2 keinen Nachteil im Vergleich zu den anderen Checks und behält die Vorteile, da Nullen häufiger vorkommen.
Sie sollten jedoch wirklich messen, was mit Ihrem Compiler und Ihren repräsentativen Beispieldaten passiert.
Machen Sie 50% der Einträge aus d=0 zufällig, anstatt es fast immer zu machen d!=0, und es werden mehr Fehler bei der Verzweigungsvorhersage angezeigt. Die Verzweigungsvorhersage ist großartig, wenn einer Verzweigung fast immer gefolgt wird oder wenn die Verfolgung der einen oder anderen Verzweigung sehr klumpig ist …
– Yakk – Adam Nevraumont
27. Mai 2013 um 18:18 Uhr
@ Yakk Das d Iteration ist die innere Schleife, also die d == 0 Fälle werden gleichmäßig verteilt. Und macht 50% der Fälle d == 0 realistisch?
– Benutzer743382
27. Mai 2013 um 18:19 Uhr
macht 0.002% der Fälle d==0 realistisch? Sie werden überall verteilt, alle 65000 Iterationen, die Sie treffen d==0 Fall. Während 50% kommt vielleicht nicht oft vor, 10% oder 1% könnte leicht passieren, oder sogar 90% oder 99%. Der angezeigte Test testet wirklich nur “Wenn Sie im Grunde nie einen Zweig hinuntergehen, macht die Verzweigungsvorhersage das Entfernen des Zweigs sinnlos?”, worauf die Antwort “Ja, aber das ist nicht interessant” lautet.
– Yakk – Adam Nevraumont
27. Mai 2013 um 18:32 Uhr
Nein, da die Unterschiede aufgrund des Rauschens praktisch unsichtbar sind.
– Jo
27. Mai 2013 um 20:14 Uhr
Die Verteilung der Nullen bezieht sich nicht auf die Verteilung, die in der Situation des Fragestellers gefunden wird. Bilder, die eine Mischung aus 0 Alpha und anderen enthalten, haben Löcher oder unregelmäßige Formen, aber (normalerweise) ist dies kein Rauschen. Anzunehmen, dass Sie nichts über die Daten wissen (und es als Rauschen betrachten), ist ein Fehler. Dies ist eine reale Anwendung mit tatsächlichen Bildern, die 0 Alpha haben können. Und da eine Reihe von Pixeln wahrscheinlich entweder alle a=0 oder alle a>0 hat, kann die Nutzung der Verzweigungsvorhersage sehr wohl am schnellsten sein, insbesondere wenn a=0 häufig auftritt und (langsame) Divisionen (15+ Zyklen). !) werden vermieden.
– DDS
28. Mai 2013 um 19:28 Uhr
Tyler Durden
Ohne die Plattform zu kennen, gibt es keine Möglichkeit, die effizienteste Methode zu kennen, aber auf einem generischen System kann dies dem Optimum nahe kommen (unter Verwendung der Intel-Assembler-Syntax):
(Angenommen, der Divisor ist in ecx und die Dividende ist drin eax)
Vier unverzweigte Anweisungen mit einem Zyklus plus die Division. Der Quotient wird drin sein eax und der Rest wird drin sein edx Am Ende. (Dies zeigt, warum Sie keinen Compiler schicken wollen, um die Arbeit eines Mannes zu erledigen).
Dies führt keine Division aus, sondern verunreinigt nur den Divisor, sodass eine Division durch Null unmöglich ist
– Tyler Durden
27. Mai 2013 um 21:36 Uhr
@Jens Timmerman Tut mir leid, das habe ich geschrieben, bevor ich die div-Anweisung hinzugefügt habe. Ich habe den Text aktualisiert.
– Tyler Durden
29. Mai 2013 um 15:40 Uhr
Demzufolge Verknüpfungkönnen Sie das SIGFPE-Signal einfach mit blockieren sigaction() (Ich habe es selbst nicht ausprobiert, aber ich glaube, es sollte funktionieren).
Dies ist die schnellstmögliche Vorgehensweise, wenn Division-durch-Null-Fehler äußerst selten sind: Sie zahlen nur für die Divisionen durch Null, nicht für die gültigen Divisionen, der normale Ausführungspfad wird überhaupt nicht geändert.
Das Betriebssystem wird jedoch an jeder ignorierten Ausnahme beteiligt sein, was teuer ist. Ich denke, Sie sollten mindestens tausend gute Divisionen pro Division durch Null haben, die Sie ignorieren. Wenn Ausnahmen häufiger auftreten, zahlen Sie wahrscheinlich mehr, wenn Sie die Ausnahmen ignorieren, als wenn Sie jeden Wert vor der Division überprüfen.
14218800cookie-checkWas ist die schnellste ganzzahlige Division, die die Division durch Null unterstützt, unabhängig vom Ergebnis?yes
Wie haben Sie festgestellt, dass der if-Zweig zu teuer ist?
– Djechlin
27. Mai 2013 um 16:56 Uhr
Wie hast du das da festgestellt ist ein Zweig?
– leemes
27. Mai 2013 um 16:57 Uhr
+1 für die Profilerstellung, mit der modernen Verzweigungsvorhersage benötigen Sie dies möglicherweise nicht. Ebenfalls, warum Programmieren Sie Ihre eigenen Bildverarbeitungsalgorithmen?
– TC1
27. Mai 2013 um 16:57 Uhr
“Was ist der schnellste Bittwiddling-Hack …” Vielleicht
y += !y
? Es ist kein Zweig erforderlich, um das zu berechnen. Du könntest vergleichenx / (y + !y)
gegenx / max(y, 1)
und vielleicht auchy ? (x/y) : 0
. Ich denke, es wird in keinem von ihnen einen Zweig geben, zumindest wenn die Optimierungen aktiviert sind.– leemes
27. Mai 2013 um 17:07 Uhr
Jeder, der denkt, dass die moderne Verzweigungsvorhersage bedeutet, dass Sie dies nicht tun müssen, hat nicht genügend Verzweigungseliminierungscode profiliert, der auf einer Per-Pixel-Ebene ausgeführt wird. Moderne Verzweigungsvorhersage ist akzeptabel, wenn das Alpha
0
Abschnitte sind riesig und zusammenhängend. Es gibt einen Platz zum Herumspielen mit Mikrooptimierungen und Operationen pro Pixel exakt diese Stelle.– Yakk – Adam Nevraumont
27. Mai 2013 um 18:00 Uhr