Quelle est la division entière la plus rapide prenant en charge la division par zéro, quel que soit le résultat?

109

Résumé:

Je recherche le moyen le plus rapide de calculer

(int) x / (int) y

sans obtenir une exception pour y==0. Au lieu de cela, je veux juste un résultat arbitraire.


Contexte:

Lors du codage d'algorithmes de traitement d'image, j'ai souvent besoin de diviser par une valeur alpha (accumulée). La variante la plus simple est le code C simple avec arithmétique entière. Mon problème est que j'obtiens généralement une erreur de division par zéro pour les pixels de résultat avec alpha==0. Cependant, ce sont exactement les pixels où le résultat n'a aucune importance: je me fiche des valeurs de couleur des pixels avec alpha==0.


Détails:

Je recherche 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, je cherche donc un moyen de me débarrasser du branchement conditionnel.

Lorsque y ne dépasse pas la plage d'octets, je suis satisfait de la solution

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

Mais cela ne fonctionne évidemment pas bien pour les plus grandes gammes.

Je suppose que la dernière question est la suivante: quel est le piratage le plus rapide qui change de 0 à une autre valeur entière, tout en laissant toutes les autres valeurs inchangées?


Clarifications

Je ne suis pas sûr à 100% que le branchement soit trop cher. Cependant, différents compilateurs sont utilisés, donc je préfère le benchmarking avec peu d'optimisations (ce qui est en effet discutable).

Bien sûr, les compilateurs sont excellents en ce qui concerne le twiddling, mais je ne peux pas exprimer le résultat "don't care" en C, donc le compilateur ne pourra jamais utiliser la gamme complète des optimisations.

Le code doit être entièrement compatible C, les principales plates-formes sont Linux 64 bits avec gcc & clang et MacOS.

philipp
la source
22
Comment avez-vous déterminé que la branche if est trop chère?
djechlin
7
Comment avez - vous déterminé qu'il y est une branche?
leemes
13
+1 pour le profilage, avec la prédiction de branche moderne, vous n'en aurez peut-être pas besoin. Aussi, pourquoi codez -vous vos propres algorithmes de traitement d'image?
TC1
8
"Quel est le piratage le plus rapide ..." Peut y += !y- être ? Aucune branche nécessaire pour calculer cela. Vous pouvez comparer les x / (y + !y)contre x / max(y, 1)et peut - être aussi y ? (x/y) : 0. Je suppose qu'il n'y aura aucune branche dans l'un ou l'autre, du moins avec les optimisations activées.
leemes
6
Quiconque pense que la prédiction de branche moderne signifie que vous n'êtes pas obligé de le faire n'a pas profilé suffisamment de code d'élimination de branche qui s'exécute au niveau par pixel. La prédiction de branche moderne est acceptable si les 0sections alpha sont énormes et contiguës. Il y a un endroit pour bidouiller avec les micro-optimisations, et les opérations par pixel sont exactement cet endroit.
Yakk - Adam Nevraumont

Réponses:

107

Inspiré par certains des commentaires, je me suis débarrassé de la branche sur mon Pentium et de mon gcccompilateur en utilisant

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

Le compilateur reconnaît essentiellement qu'il peut utiliser un indicateur de condition du test dans l'addition.

Selon la demande, l'assemblage:

.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 question et une réponse très populaire, je vais élaborer un peu plus. L'exemple ci-dessus est basé sur un langage de programmation reconnu par un compilateur. Dans le cas ci-dessus, une expression booléenne est utilisée en arithmétique intégrale et l'utilisation d'indicateurs de condition est inventée dans le matériel à cette fin. En condition générale, les drapeaux ne sont accessibles en C qu'en utilisant idiom. C'est pourquoi il est si difficile de créer une bibliothèque d'entiers de précision multiple portable en C sans recourir à l'assemblage (en ligne). Je suppose que la plupart des compilateurs décents comprendront l'idiome ci-dessus.

Une autre façon d'éviter les branches, comme cela a également été remarqué dans certains des commentaires ci-dessus, est l'exécution prédéfinie. J'ai donc pris le premier code de philipp et mon code et je l'ai fait passer par le compilateur d'ARM et le compilateur GCC pour l'architecture ARM, qui propose une exécution prédéfinie. Les deux compilateurs évitent la branche dans les deux exemples de code:

Version de Philipp avec le compilateur ARM:

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

Version de Philipp 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 compilateur ARM:

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 toujours besoin d'une branche vers la routine de division, car cette version de l'ARM ne dispose pas de matériel pour une division, mais le test y == 0est entièrement implémenté via une exécution prédéfinie.

Bryan Olivier
la source
Pouvez-vous nous montrer le code assembleur résultant? Ou comment avez-vous déterminé qu'il n'y avait pas de succursale?
Haatschii
1
Impressionnant. Peut être fait constexpret éviter les moulages inutiles comme celui-ci: template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); } Et si vous voulez 255,(lhs)/(rhs+!rhs) & -!rhs
Yakk - Adam Nevraumont
1
@leemes mais je ne voulais |pas dire &. Oups - ( (lhs)/(rhs+!rhs) ) | -!rhsdevrait définir votre valeur sur 0xFFFFFFFif rhsis 0, et lhs/rhsif rhs!=0.
Yakk - Adam Nevraumont
1
C'était très intelligent.
Theodoros Chatzigiannakis
1
Très bonne réponse! J'ai l'habitude de recourir à l'assemblage pour ce genre de choses, mais c'est toujours horrible à entretenir (pour ne pas dire moins portable;)).
Leo
20

Voici quelques chiffres concrets, sur Windows utilisant 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 n'appelle pas intentionnellement srand(), donc cela rand()renvoie toujours exactement les mêmes résultats. Notez également que -DCHECK=0ne compte que les zéros, de sorte que la fréquence d'apparition est évidente.

Maintenant, compilez et chronométrez de différentes manières:

$ 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

affiche la sortie qui peut être résumée 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, la -DCHECK=2version fonctionne mal. Au fur et à mesure que les zéros apparaissent de plus en plus, le -DCHECK=2boîtier commence à fonctionner nettement mieux. Parmi les autres options, il n'y a vraiment pas beaucoup de différence.

Car -O3, cependant, 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à, le chèque 2 n'a aucun inconvénient par rapport aux autres chèques, et il conserve les avantages à mesure que les zéros deviennent plus courants.

Vous devriez vraiment mesurer pour voir ce qui se passe avec votre compilateur et vos exemples de données représentatifs, cependant.


la source
4
Faites en sorte que 50% des entrées soient d=0aléatoires, au lieu de le faire presque toujours d!=0, et vous verrez plus d'échecs de prédiction de branche. La prédiction de branche est excellente si une branche est presque toujours suivie, ou si la suite d'une branche ou de l'autre est vraiment grumeleuse ...
Yakk - Adam Nevraumont
@Yakk L' ditération est la boucle interne, donc les d == 0cas sont répartis uniformément. Et est-ce que 50% des cas sont d == 0réalistes?
2
est-ce que faire 0.002%des cas est d==0réaliste? Ils sont distribués partout, toutes les 65000 itérations vous frappez votre d==0cas. Bien que 50%cela ne se produise pas souvent, 10%ou 1%facilement, ou même 90%ou 99%. Le test tel qu'il est affiché ne teste vraiment que "si vous ne descendez jamais, jamais dans une branche, est-ce que la prédiction de branche rend inutile la suppression de la branche?", Auquel la réponse est "oui, mais ce n'est pas intéressant".
Yakk - Adam Nevraumont
1
Non, car les différences seront effectivement invisibles à cause du bruit.
Joe
3
La distribution des zéros ne se rapporte pas à la distribution trouvée dans la situation du demandeur. Les images contenant un mélange de 0 alpha et d'autres ont des trous ou une forme irrégulière, mais (généralement) ce n'est pas du bruit. Supposer que vous ne savez rien sur les données (et que vous considérez cela comme du bruit) est une erreur. Ceci est une application du monde réel avec des images réelles qui peuvent avoir 0 alpha. Et comme une ligne de pixels est susceptible d'avoir soit tout a = 0, soit tout a> 0, tirer parti de la prédication de branche peut très bien être le plus rapide, surtout quand a = 0 se produit beaucoup et que des divisions (lentes) (15+ cycles !) sont évités.
DDS
13

Sans connaître la plate-forme, il n'y a aucun moyen de connaître la méthode la plus efficace, cependant, sur un système générique, cela peut être proche de l'optimum (en utilisant la syntaxe de l'assembleur Intel):

(Supposons que le diviseur est dans ecxet que le dividende est dans eax)

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

Quatre instructions non ramifiées à cycle unique plus la division. Le quotient sera dans eaxet le reste sera edxà la fin. (Ce genre de montre pourquoi vous ne voulez pas envoyer un compilateur pour faire le travail d'un homme).

Tyler Durden
la source
où est la division?
Yakk - Adam Nevraumont
1
cela ne fait pas la division, il pollue simplement le diviseur de sorte que la division par zéro est impossible
Tyler Durden
@Jens Timmerman Désolé, j'ai écrit ça avant d'ajouter la déclaration div. J'ai mis à jour le texte.
Tyler Durden
1

Selon ce lien , vous pouvez simplement bloquer le signal SIGFPE avec sigaction()(je ne l'ai pas essayé moi-même, mais je pense que cela devrait fonctionner).

C'est l'approche la plus rapide possible si les erreurs de division par zéro sont extrêmement rares: vous ne payez que pour les divisions par zéro, pas pour les divisions valides, le chemin d'exécution normal n'est pas du tout modifié.

Cependant, le système d'exploitation sera impliqué dans chaque exception ignorée, ce qui est coûteux. Je pense que vous devriez avoir au moins mille bonnes divisions par division par zéro que vous ignorez. Si les exceptions sont plus fréquentes que cela, vous paierez probablement plus en ignorant les exceptions qu'en vérifiant chaque valeur avant la division.

cmaster - réintégrer monica
la source