Code sans embranchement qui associe zéro, négatif et positif à 0, 1, 2

Question

Ecrivez une fonction sans branche qui renvoie 0, 1 ou 2 si la différence entre deux entiers signés est égale à zéro, négative ou positive.

Voici une version avec branchement:

int Compare(int x, int y)
{
    int diff = x - y;
    if (diff == 0)
        return 0;
    else if (diff < 0)
        return 1;
    else
        return 2;
}

Voici une version qui peut être plus rapide en fonction du compilateur et du processeur:

int Compare(int x, int y)
{
    int diff = x - y;
    return diff == 0 ? 0 : (diff < 0 ? 1 : 2);
}

Pouvez-vous en créer un plus rapide sans branches?

RÉSUMÉ

Les 10 solutions que j'ai testées ont des performances similaires. Les nombres réels et le gagnant varient en fonction du compilateur (icc / gcc), des options du compilateur (par exemple, -O3, -march = nocona, -fast, -xHost) et de la machine. La solution de Canon a bien fonctionné dans de nombreux tests de performances , mais là encore, l’avantage en termes de performances était faible. J'ai été surpris de constater que, dans certains cas, certaines solutions étaient plus lentes que la solution naïve avec des branches.

Answer 1

int Compare(int x, int y) {
     return (x < y) + (y < x) << 1;
}

Éditer: bit par bit seulement? Devinez & Lt; et > ne compte pas, alors?

int Compare(int x, int y) {
    int diff = x - y;
    return (!!diff) | (!!(diff & 0x80000000) << 1);
}

Mais il y a que c'est embêtant -.

Éditer: inversez la tendance.

Meh, juste pour réessayer:

int Compare(int x, int y) {
    int diff = y - x;
    return (!!diff) << ((diff >> 31) & 1);
}

Mais je suppose qu'il n'y a pas d'instruction ASM standard pour !!. De même, le << peut être remplacé par +, selon ce qui est le plus rapide ...

C'est un peu marrant de tourner!

Hmm, je viens d'apprendre que setnz.

Je n'ai pas vérifié la sortie de l'assembleur (mais je l'ai un peu testée cette fois), et avec un peu de chance, cela pourrait sauver une instruction complète !:

en théorie. MON ASSEMBLEUR EST RUSTY

subl  %edi, %esi
setnz %eax
sarl  $31, %esi
andl  $1, %esi
sarl  %eax, %esi
mov   %esi, %eax
ret

Se promener est amusant.

J'ai besoin de dormir.

Answer 2

Le code sans branche (au niveau de la langue) qui mappe négatif à -1, zéro à 0 et positif à +1 ressemble à ceci

int c = (n > 0) - (n < 0);

si vous avez besoin d'un mappage différent, vous pouvez simplement utiliser un mappage explicite pour le remapper

const int MAP[] = { 1, 0, 2 };
int c = MAP[(n > 0) - (n < 0) + 1];

ou, pour le mappage demandé, utilisez une astuce numérique telle que

int c = 2 * (n > 0) + (n < 0);

(Il est évidemment très facile de générer un mappage à partir de ceci tant que 0 est mappé sur 0. Et le code est assez lisible. Si 0 est mappé sur autre chose, il devient plus compliqué et moins lisible.)

Remarque supplémentaire: comparer deux entiers en les soustrayant au niveau de langage C est une technique imparfaite, car elle est généralement sujette au débordement. La beauté des méthodes ci-dessus réside dans le fait qu’elles peuvent être immédiatement utilisées pour & "; Sans soustraction &"; des comparaisons, comme

int c = 2 * (x > y) + (x < y);

Answer 3

En supposant un complément à 2, un décalage arithmétique à droite et aucun dépassement de capacité dans la soustraction:

#define SHIFT (CHARBIT*sizeof(int) - 1)

int Compare(int x, int y)
{
    int diff = x - y;
    return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}

Answer 4

Complément à deux:

#include <limits.h>
#define INT_BITS (CHAR_BITS * sizeof (int))

int Compare(int x, int y) {
    int d = y - x;
    int p = (d + INT_MAX) >> (INT_BITS - 1);
    d = d >> (INT_BITS - 2);
    return (d & 2) + (p & 1);
}

En supposant un compilateur sain, cela n’appellera ni le matériel de comparaison de votre système, ni une comparaison dans le langage. Pour vérifier: si x == y, alors d et p seront clairement égaux à 0 et le résultat final sera zéro. Si (x - y) & Gt; 0 alors ((x - y) + INT_MAX) définira le bit haut de l’entier, sinon il sera inactif. Donc, p aura son bit le plus bas défini si et seulement si (x - y) & Gt; 0. Si (x - y) & Lt; 0, son bit haut sera défini et d définira son deuxième bit sur le bit le plus bas.

Answer 5

La comparaison non signée qui renvoie -1,0,1 (cmpu) est l’un des cas testés par GNU , SuperOptimizer .

cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
    return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}

Un superoptimiseur recherche minutieusement dans l'espace d'instructions la meilleure combinaison possible d'instructions qui implémenteront une fonction donnée. Il est suggéré aux compilateurs de remplacer automatiquement les fonctions ci-dessus par leurs versions superoptimisées (bien que tous les compilateurs fais ça). Par exemple, dans le Guide de l’écriture du compilateur PowerPC ( powerpc-cwg.pdf ). ), la fonction cmpu est illustrée dans l’annexe D, page 204:

cmpu: compare (unsigned)
PowerPC SuperOptimized Version
subf  R5,R4,R3
subfc R6,R3,R4
subfe R7,R4,R3
subfe R8,R7,R5

C’est plutôt bien, n’est-ce pas ... seulement quatre soustractions (et avec les versions de portage et / ou étendue). Sans parler du fait qu'il est réellement sans branche au niveau du code d'opération de la machine . Il existe probablement une séquence équivalente PC / Intel X86 qui est également courte puisque le superoptimiseur GNU fonctionne pour X86 ainsi que pour PowerPC.

Notez que la comparaison non signée (cmpu) peut être transformée en comparaison signée (cmps) sur une comparaison 32 bits en ajoutant 0x80000000 aux deux entrées signées avant de la transmettre à cmpu.

cmps: compare (signed)
int cmps(signed_word v0, signed_word v1)
{
    signed_word offset=0x80000000;
    return ( (unsigned_word) (v0 + signed_word),
        (unsigned_word) (v1 + signed_word) );
}

Il ne s’agit que d’une option ... Le SuperOptimizer peut trouver un cmps plus court et ne pas avoir à ajouter de compensation ni à appeler cmpu.

Pour obtenir la version que vous avez demandée et qui renvoie vos valeurs de {1,0,2} au lieu de {-1,0,1}, utilisez le code suivant, qui tire parti de la fonction cmp SuperOptimized.

int Compare(int x, int y)
{
    static const int retvals[]={1,0,2};
    return (retvals[cmps(x,y)+1]);
}

Answer 6

Je me range à côté de la réponse originale de Tordek:

int compare(int x, int y) {
    return (x < y) + 2*(y < x);
}

La compilation avec gcc -O3 -march=pentium4 donne un code sans branche qui utilise des instructions conditionnelles setg et setl (voir ceci explication des instructions x86 ).

push   %ebp
mov    %esp,%ebp
mov    %eax,%ecx
xor    %eax,%eax
cmp    %edx,%ecx
setg   %al
add    %eax,%eax
cmp    %edx,%ecx
setl   %dl
movzbl %dl,%edx
add    %edx,%eax
pop    %ebp
ret 

Answer 7

Bon Dieu, cela m’a hanté.

Quoi que je fasse, je pense avoir tiré une dernière goutte de performance:

int compare(int a, int b) {
    return (a != b) << (a > b);
}

Bien que, compiler avec -O3 dans GCC donnera (gardez avec moi je le fais de mémoire)

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
cmpl  %esi, %edi
setgt %dl
sall  %dl, %eax
ret

Mais la deuxième comparaison semble (selon un petit test; je suis nul à ASM) redondante, laissant le petit et beau

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
setgt %dl
sall  %dl, %eax
ret

(Sall n'est peut-être pas une instruction ASM, mais je ne me souviens pas exactement.)

Alors ... si cela ne vous dérange pas de réutiliser votre point de repère, j'aimerais connaître les résultats (le mien a donné une amélioration de 3%, mais il se peut que ce soit faux).

Answer 8

Combinant les réponses de Stephen Canon et de Tordek:

int Compare(int x, int y)
{
    int diff = x - y; 
    return -(diff >> 31) + (2 & (-diff >> 30));
} 

Rendements: (g ++ -O3)

subl     %esi,%edi 
movl     %edi,%eax
sarl     $31,%edi
negl     %eax
sarl     $30,%eax
andl     $2,%eax
subl     %edi,%eax 
ret 

Tight! Cependant, la version de Paul Hsieh contient encore moins d'instructions:

subl     %esi,%edi
leal     0x7fffffff(%rdi),%eax
sarl     $30,%edi
andl     $2,%edi
shrl     $31,%eax
leal     (%rdi,%rax,1),%eax
ret

Answer 9

int Compare(int x, int y)
{
    int diff = x - y;

    int absdiff = 0x7fffffff & diff; // diff with sign bit 0
    int absdiff_not_zero = (int) (0 != udiff);

    return
        (absdiff_not_zero << 1)      // 2 iff abs(diff) > 0
        -
        ((0x80000000 & diff) >> 31); // 1 iff diff < 0
}

Answer 10

Pour 32 entiers signés (comme en Java), essayez:

return 2 - ((((x >> 30) & 2) + (((x-1) >> 30) & 2))) >> 1;

où (x >> 30) & 2 renvoie 2 pour les nombres négatifs et 0 sinon.

x serait la différence des deux entiers en entrée