Ce que la division d’entiers plus rapide soutient division par zéro, quel que soit le résultat ?

Question

Résumé:

Je suis à la recherche de la façon la plus rapide pour calculer

(int) x / (int) y

sans se faire une exception pour y==0. Au lieu de cela, je veux juste que l'arbitraire d'un résultat.

---

Arrière-plan:

Lors du codage d'algorithmes de traitement d'image, j'ai souvent besoin de diviser par un (cumul) la valeur alpha. La variante la plus simple est de la plaine du code C avec l'arithmétique des nombres entiers. Mon problème est que j'ai généralement obtenir une division par zéro pour résultat pixels avec alpha==0. Cependant, ce sont exactement les pixels où le résultat n'est pas grave du tout: je ne me préoccupe pas de la couleur des valeurs de pixels avec alpha==0.

---

Détails:

Je suis à la recherche de quelque chose comme:

result = (y==0)? 0 : x/y;

ou

result = x / MAX( y, 1 );

x et y sont des entiers positifs. Le code est exécuté un grand nombre de fois dans une boucle imbriquée, donc je suis à la recherche d'un moyen de se débarrasser de la condition de branchement.

Lorsque y ne pas dépasser la plage d'octets, je suis heureux avec la solution

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

Mais de toute évidence, cela ne fonctionne pas bien pour les grandes plages.

Je suppose que la dernière question est: quel est le plus rapide peu tourner hack changement de 0 pour toute autre valeur entière, tout en laissant toutes les autres valeurs inchangées?

---

Précisions

Je ne suis pas sûr à 100% que la ramification est trop cher. Cependant, des compilateurs différents sont utilisés, donc je préfère la comparaison avec peu d'optimisations (ce qui est discutable).

Pour sûr, les compilateurs sont grands quand il s'agit à peu se tourner, mais je ne peux pas exprimer le "don't care" résultat dans C, de sorte que le compilateur ne sera jamais en mesure d'utiliser la gamme complète des optimisations.

Le Code doit être entièrement C compatible, le principal sont les plates-formes Linux 64 Bits avec gcc et clang et MacOS.

Answer 1

Inspiré par certains des commentaires que je me suis débarrassé de la branche sur mon Pentium et gcc compilateur à l'aide de

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

Le compilateur reconnaît fondamentalement qu'il peut utiliser une condition drapeau de l'épreuve dans le plus.

Conformément à la demande de l'assemblée:

.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

Comme cela s'est avéré être une telle populaire de la question et la réponse, je vais essayer d'approfondir un peu plus. L'exemple ci-dessus est basé sur la programmation de l'idiome qu'un compilateur reconnaît. Dans le cas ci-dessus une expression booléenne est utilisé dans l'intégralité de l'arithmétique et de l'utilisation de la condition des drapeaux sont inventés dans le matériel à cet effet. Dans la condition générale des drapeaux ne sont accessibles qu'en C à l'aide de l'idiome. C'est pourquoi il est si difficile de faire un portable multiples précision entier de la bibliothèque en C sans avoir recours à l' (inline) de l'assemblée. Ma conjecture est que la plupart des bons compilateurs de comprendre ce qui précède idiome.

Une autre manière d'éviter les branches, comme l'a également fait remarquer dans certains des commentaires ci-dessus, est fondée l'exécution. J'ai donc pris philipp premier code et mon code et il a couru à travers le compilateur de BRAS et le compilateur GCC pour l'architecture ARM, qui dispose d'fondée exécution. Les deux compilateurs éviter la branche dans les deux échantillons de code:

Philipp est la version avec le BRAS du compilateur:

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

Philipp version avec GCC:

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

Mon code avec le BRAS du compilateur:

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

Mon code avec GCC:

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

Toutes les versions ont encore besoin d'une branche de la division de la routine, parce que cette version du BRAS n'a pas le matériel pour une division, mais le test pour y == 0 est pleinement mis en œuvre à travers fondée exécution.

Answer 2

Voici quelques chiffres concrets, sur Windows à l'aide de 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);
}

Notez que je ne suis pas intentionnellement appelant srand(), de sorte qu' rand() retourne toujours exactement les mêmes résultats. Notez également qu' -DCHECK=0 seulement compte des zéros, de sorte qu'il est évident de savoir comment est apparu souvent.

Maintenant, la compilation et le calendrier de différentes façons:

$ 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

montre de sortie qui peuvent être résumés dans un tableau:

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

Si les zéros sont rares, l' -DCHECK=2 version effectue mal. Comme des zéros commencent à apparaître de plus, l' -DCHECK=2 de cas commence à se produire de manière significative une meilleure. De l'autre des options, il n'y a vraiment pas beaucoup de différence.

Pour -O3, mais c'est une autre histoire:

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

Là, case 2 n'a aucun désavantage par rapport aux autres contrôles, et il ne garder que les avantages que les zéros deviennent plus courantes.

Vous devriez vraiment en mesure de voir ce qui se passe avec votre compilateur et votre échantillon représentatif de données.

Answer 3

Sans la connaissance de la plate-forme il n'y a aucun moyen de connaître l'exacte méthode plus efficace, cependant, dans un système générique de cette mai près de l'optimum (à l'aide d'Intel assembleur syntaxe):

(à supposer diviseur est en ecx et le dividende est en eax)

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

Quatre non ramifié, en un seul cycle des instructions plus le fossé. Le quotient sera en eax et le reste sera en edx à la fin. (Ce genre de montre pourquoi vous ne voulez pas envoyer un compilateur pour faire le travail d'un homme).