Was ist die schnellste Ganzzahldivision, die die Division durch Null unterstützt, unabhängig vom Ergebnis?

109

Zusammenfassung:

Ich suche den schnellsten Weg, um zu berechnen

(int) x / (int) y

ohne eine Ausnahme zu bekommen für y==0. Stattdessen möchte ich nur ein beliebiges Ergebnis.


Hintergrund:

Beim Codieren von Bildverarbeitungsalgorithmen muss ich oft durch einen (akkumulierten) Alpha-Wert dividieren. Die einfachste Variante ist einfacher C-Code mit ganzzahliger Arithmetik. Mein Problem ist, dass ich für Ergebnispixel mit normalerweise einen Fehler durch Division durch Null erhalte alpha==0. Dies sind jedoch genau die Pixel, bei denen das Ergebnis überhaupt keine Rolle spielt: Ich interessiere mich nicht für Farbwerte von Pixeln mit alpha==0.


Einzelheiten:

Ich suche so etwas 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 zu beseitigen.

Wenn y den Bytebereich nicht überschreitet, bin ich mit der Lösung zufrieden

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

Dies funktioniert jedoch 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?


Klarstellungen

Ich bin mir nicht 100% sicher, dass die Verzweigung zu teuer ist. Es werden jedoch unterschiedliche Compiler verwendet, daher bevorzuge ich Benchmarking mit geringen Optimierungen (was in der Tat fraglich ist).

Natürlich sind Compiler großartig, wenn es um Bit-Twiddling geht, aber ich kann das Ergebnis "egal" in C nicht ausdrücken, sodass der Compiler niemals alle Optimierungen nutzen kann.

Der Code sollte vollständig C-kompatibel sein. Die Hauptplattformen sind Linux 64 Bit mit gcc & clang und MacOS.

philipp
quelle
22
Wie haben Sie festgestellt, dass der if-Zweig zu teuer ist?
Djechlin
7
Wie haben festgestellt, dass es ist ein Zweig?
Leemes
13
+1 für die Profilerstellung, mit der modernen Branchenvorhersage benötigen Sie diese möglicherweise nicht. Auch warum codieren Sie Ihre eigenen Bildverarbeitungsalgorithmen?
TC1
8
"Was ist der schnellste Twiddling-Hack ..." Vielleicht y += !y? Kein Zweig benötigt, um das zu berechnen. Sie könnten vergleichen x / (y + !y)gegen x / max(y, 1)und vielleicht auch y ? (x/y) : 0. Ich denke, es wird in keinem von beiden einen Zweig geben, zumindest wenn die Optimierungen aktiviert sind.
Leemes
6
Jeder, der der Meinung ist, dass die moderne Verzweigungsvorhersage bedeutet, dass Sie dies nicht tun müssen, hat nicht genügend Code zur Eliminierung von Verzweigungen erstellt, der auf Pixelebene ausgeführt wird. Die moderne Vorhersage von Zweigen ist akzeptabel, wenn die Alpha- 0Abschnitte groß und zusammenhängend sind. Es gibt einen Ort, an dem man mit Mikrooptimierungen herumspielen kann, und Operationen pro Pixel sind genau dieser Ort.
Yakk - Adam Nevraumont

Antworten:

107

Inspiriert von einigen Kommentaren habe ich den Zweig auf meinem Pentium und gccCompiler mit entfernt

int f (int x, int y)
{
        y += y == 0;
        return x/y;
}

Der Compiler erkennt grundsätzlich, dass er im Zusatz ein Bedingungsflag des Tests verwenden kann.

Auf Anfrage der Baugruppe:

.globl f
    .type   f, @function
f:
    pushl   %ebp
    xorl    %eax, %eax
    movl    %esp, %ebp
    movl    12(%ebp), %edx
    testl   %edx, %edx
    sete    %al
    addl    %edx, %eax
    movl    8(%ebp), %edx
    movl    %eax, %ecx
    popl    %ebp
    movl    %edx, %eax
    sarl    $31, %edx
    idivl   %ecx
    ret

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 Hardware erfunden. Im Allgemeinen sind Flags in C nur mit idiom zugänglich. Aus diesem Grund ist es in C so schwierig, eine tragbare Ganzzahlbibliothek mit mehrfacher Genauigkeit zu erstellen, ohne auf (Inline-) Assembly zurückgreifen zu müssen. Ich vermute, dass die meisten anständigen Compiler die obige Redewendung verstehen werden.

Eine andere Möglichkeit, Verzweigungen zu vermeiden, wie auch in einigen der obigen Kommentare erwähnt, ist 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 ausgeführt, die eine prädizierte Ausführung bietet. 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

Philipps Version mit GCC:

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

Mein Code mit dem ARM-Compiler:

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

Mein Code mit GCC:

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

Alle Versionen benötigen noch eine Verzweigung zur Divisionsroutine, da diese Version des ARM keine Hardware für eine Division enthält, der Test für y == 0jedoch vollständig durch prädizierte Ausführung implementiert wird.

Bryan Olivier
quelle
Können Sie uns den resultierenden Assembler-Code zeigen? Oder wie haben Sie festgestellt, dass es keinen Zweig gibt?
Haatschii
1
Genial. Kann gemacht werden constexprund unnötige template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); }255(lhs)/(rhs+!rhs) & -!rhs
Typabgüsse
1
@leemes aber ich meinte |nicht &. Hoppla - ( (lhs)/(rhs+!rhs) ) | -!rhssollte Ihren Wert auf 0xFFFFFFFif rhsis 0und lhs/rhsif setzen rhs!=0.
Yakk - Adam Nevraumont
1
Das war sehr klug.
Theodoros Chatzigiannakis
1
Gute Antwort! Normalerweise greife ich für solche Dinge auf die Montage zurück, aber das ist immer schrecklich zu pflegen (ganz zu schweigen von weniger tragbar;)).
Leo
20

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(), sodass rand()immer genau die gleichen Ergebnisse zurückgegeben werden. Beachten Sie auch, dass -DCHECK=0nur die Nullen gezählt werden, so dass es offensichtlich ist, wie oft erschienen.

Nun können Sie es auf verschiedene Arten kompilieren und zeitlich festlegen:

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

Iterations  | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.612s | -        | -        | -         | -         | -
Check 2      | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3      | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4      | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5      | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s

Wenn Nullen selten sind, funktioniert die -DCHECK=2Version schlecht. Wenn mehr Nullen erscheinen, wird die-DCHECK=2 Fall deutlich besser. Von den anderen Optionen gibt es wirklich keinen großen Unterschied.

Denn -O3es ist eine andere Geschichte:

Iterations  | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.646s | -        | -        | -         | -         | -
Check 2      | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3      | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4      | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5      | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s

Dort hat Scheck 2 im Vergleich zu den anderen Schecks keinen Nachteil und behält die Vorteile bei, wenn Nullen häufiger werden.

Sie sollten jedoch wirklich messen, um zu sehen, was mit Ihrem Compiler und Ihren repräsentativen Beispieldaten passiert.


quelle
4
Stellen Sie sicher d=0, dass 50% der Einträge zufällig sind, anstatt fast immer d!=0, und Sie werden mehr Fehler bei der Verzweigungsvorhersage sehen. Die Vorhersage von Zweigen ist großartig, wenn einem Zweig fast immer gefolgt wird oder wenn das Folgen des einen oder anderen Zweigs wirklich klumpig ist ...
Yakk - Adam Nevraumont
@Yakk Die dIteration ist die innere Schleife, daher sind die d == 0Fälle gleichmäßig verteilt. Und sind 50% der Fälle d == 0realistisch?
2
macht 0.002%die Fälle d==0realistisch? Sie werden über alle 65000 Iterationen verteilt, die Sie in Ihrem d==0Fall getroffen haben. Während 50%möglicherweise nicht oft 10%oder 1%leicht passieren könnte, oder sogar 90%oder 99%. Der angezeigte Test testet nur wirklich "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
1
Nein, da die Unterschiede aufgrund des Rauschens praktisch unsichtbar sind.
Joe
3
Die Verteilung der Nullen bezieht sich nicht auf die Verteilung in der Situation des Fragestellers. Bilder, die eine Mischung aus 0 Alpha und anderen enthalten, haben Löcher oder eine unregelmäßige Form, aber (normalerweise) ist dies kein Rauschen. Es ist ein Fehler anzunehmen, dass Sie nichts über die Daten wissen (und es als Rauschen betrachten). Dies ist eine reale Anwendung mit tatsächlichen Bildern, die 0 Alpha haben können. Und da eine Pixelreihe wahrscheinlich entweder alle a = 0 oder alle a> 0 hat, kann die Ausnutzung der Verzweigungsprädikation sehr wohl die schnellste sein, insbesondere wenn a = 0 häufig auftritt und (langsame) Teilungen (15+ Zyklen) !) werden vermieden.
DDS
13

Ohne Kenntnis der Plattform gibt es keine Möglichkeit, die genau effizienteste Methode zu ermitteln. Auf einem generischen System kann dies jedoch nahe am Optimum liegen (unter Verwendung der Intel-Assembler-Syntax):

(Angenommen, der Divisor ist in ecxund die Dividende ist in eax)

mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx

Vier unverzweigte Einzelzyklusanweisungen plus die Teilung. Der Quotient ist in eaxund der Rest ist edxam Ende. (Diese Art zeigt, warum Sie keinen Compiler senden möchten, um die Arbeit eines Mannes zu erledigen).

Tyler Durden
quelle
Wo ist die Aufteilung?
Yakk - Adam Nevraumont
1
Dies macht nicht die Division, es verschmutzt nur den Divisor, so dass eine Division durch Null unmöglich ist
Tyler Durden
@Jens Timmerman Sorry, das habe ich geschrieben, bevor ich die div-Anweisung hinzugefügt habe. Ich habe den Text aktualisiert.
Tyler Durden
1

Laut diesem Link können Sie das SIGFPE-Signal einfach mit blockieren sigaction()(ich habe es nicht selbst ausprobiert, aber ich glaube, es sollte funktionieren).

Dies ist der schnellstmögliche Ansatz, wenn Fehler durch Division durch Null äußerst selten sind: Sie zahlen nur für die Division durch Null, nicht für die gültigen Divisionen, der normale Ausführungspfad wird überhaupt nicht geändert.

Das Betriebssystem ist jedoch an jeder Ausnahme beteiligt, die ignoriert wird, 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 indem Sie jeden Wert vor der Division überprüfen.

cmaster - Monica wieder einsetzen
quelle