Effiziente Implementierung von Floored / Euclidian Integer Division

Floored Division ist, wenn das Ergebnis immer nach unten (in Richtung −∞) geteilt wird, nicht in Richtung 0:

Ist es möglich, Floored oder Euclidian Integer Division in C/C++ effizient zu implementieren?

(Die offensichtliche Lösung besteht darin, das Vorzeichen des Dividenden zu überprüfen)

Antworten:

Ich greife diese Frage fünf Jahre später erneut auf, da sie auch für mich relevant ist. Ich habe einige Leistungsmessungen an zwei reinen C-Versionen und zwei Inline-Assembly-Versionen für x86-64 durchgeführt, und die Ergebnisse könnten interessant sein.

Die getesteten Varianten der Bodenaufteilung sind:

1. Die Implementierung, die ich seit einiger Zeit verwende;


2. Die leichte Variante der oben vorgestellten, die nur eine Unterteilung verwendet;


3. Das vorherige, aber in Inline-Montage von Hand implementiert; und


4. A CMOV Version in Assembler implementiert.

Das Folgende ist mein Benchmark-Programm:

#include <stdio.h>
 #include <stdlib.h>
 #include <sys/time.h>
 #ifndef VARIANT
 #define VARIANT 3
 #endif
 #if VARIANT == 0
 #define floordiv(a, b) (((a) < 0)?((((a) + 1) / (b)) - 1):((a) / (b)))
 #elif VARIANT == 1
 #define floordiv(a, b) ((((a) < 0)?((a) - ((b) - 1)):(a)) / (b))
 #elif VARIANT == 2
 #define floordiv(a, b) ({                                   \
     int result;                                             \
     asm("test %%eax, %%eax; jns 1f; sub %1, %%eax;"         \
         "add $1, %%eax; 1: cltd; idivl %1;"                 \
         : "=a" (result)                                     \
         : "r" (b),                                          \
           "0" (a)                                           \
         : "rdx");                                           \
     result;})
 #elif VARIANT == 3
 #define floordiv(a, b) ({                                           \
     int result;                                                     \
     asm("mov %%eax, %%edx; sub %1, %%edx; add $1, %%edx;"           \
         "test %%eax, %%eax; cmovs %%edx, %%eax; cltd;"              \
         "idivl %1;"                                                 \
         : "=a" (result)                                             \
         : "r" (b),                                                  \
           "0" (a)                                                   \
         : "rdx");                                                   \
     result;})
 #endif
 double ntime(void)
 {
     struct timeval tv;
     gettimeofday(&tv, NULL);
     return(tv.tv_sec + (((double)tv.tv_usec) / 1000000.0));
 }
 void timediv(int n, int *p, int *q, int *r)
 {
     int i;
     for(i = 0; i < n; i++)
         r[i] = floordiv(p[i], q[i]);
 }
 int main(int argc, char **argv)
 {
     int n, i, *q, *p, *r;
     double st;
     n = 10000000;
     p = malloc(sizeof(*p) * n);
     q = malloc(sizeof(*q) * n);
     r = malloc(sizeof(*r) * n);
     for(i = 0; i < n; i++) {
         p[i] = (rand() % 1000000) - 500000;
         q[i] = (rand() % 1000000) + 1;
     }
     st = ntime();
     for(i = 0; i < 100; i++)
         timediv(n, p, q, r);
     printf("%g\n", ntime() - st);
     return(0);
 }
 

Ich habe das mit gcc -march=native -Ofast kompiliert mit GCC 4.9.2, und die Ergebnisse auf meinem Core i5-2400 waren wie folgt. Die Ergebnisse sind von Lauf zu Lauf ziemlich reproduzierbar – sie landen zumindest immer in der gleichen Reihenfolge.

• Variante 0:7,21 Sekunden


• Variante 1:7,26 Sekunden


• Variante 2:6,73 Sekunden


• Variante 3:4,32 Sekunden

Also die CMOV Umsetzung bläst die anderen zumindest aus dem Wasser. Was mich überrascht, ist, dass Variante 2 ihre reine C-Version (Variante 1) ziemlich weit übertrifft. Ich hätte gedacht, dass der Compiler in der Lage sein sollte, Code mindestens so effizient auszugeben wie meiner.

Hier sind einige andere Plattformen zum Vergleich:

AMD Athlon 64 X2 4200+, GCC 4.7.2:

• Variante 0:26,33 Sekunden


• Variante 1:25,38 Sekunden


• Variante 2:25,19 Sekunden


• Variante 3:22,39 Sekunden

Xeon E3-1271 v3, GCC 4.9.2:

• Variante 0:5,95 Sekunden


• Variante 1:5,62 Sekunden


• Variante 2:5,40 Sekunden


• Variante 3:3,44 Sekunden

Als letzte Anmerkung sollte ich vielleicht davor warnen, den offensichtlichen Leistungsvorteil der CMOV zu nutzen Version zu ernst, denn in der realen Welt wird die Verzweigung in den anderen Versionen wahrscheinlich nicht so vollständig zufällig sein wie in diesem Benchmark, und wenn der Verzweigungsprädiktor vernünftige Arbeit leisten kann, werden die Verzweigungsversionen möglicherweise besser ausfallen. Die Realität davon hängt jedoch ziemlich stark von den Daten ab, die in der Praxis verwendet werden, und daher ist es wahrscheinlich sinnlos, zu versuchen, einen allgemeinen Benchmark durchzuführen.