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

Lesezeit: 10 Minuten

Benutzeravatar von Philipp
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

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

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


Benutzeravatar von Bryan Olivier
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.

Auf Wunsch die Montage:

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

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

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, 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.

Zum -O3aber es 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 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

Benutzeravatar von Tyler Durden
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)

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

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.

1421880cookie-checkWas ist die schnellste ganzzahlige Division, die die Division durch Null unterstützt, unabhängig vom Ergebnis?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy