Fonction de comparaison de nombre entier efficace

Ce qui suit s’est toujours avéré assez efficace pour moi:

 return (a < b) ? -1 : (a > b); 

Avec gcc -O2 -S , ceci se comstack dans les cinq instructions suivantes:

 xorl %edx, %edx cmpl %esi, %edi movl $-1, %eax setg %dl cmovge %edx, %eax 

Pour faire suite à l’excellente réponse d’ Ambroz Bizjak , je n’étais pas convaincu que son programme testait le même code d’assemblage que ce qui a été posté ci-dessus. Et, en étudiant de plus près la sortie du compilateur, j’ai remarqué que le compilateur ne générait pas les mêmes instructions que celles affichées dans nos réponses. J’ai donc pris son programme de test, modifié manuellement la sortie de l’assemblage pour correspondre à ce que nous avions publié et comparé les temps obtenus. Il semble que les deux versions se comparent approximativement.

 ./opt_cmp_branchless: 0m1.070s ./opt_cmp_branch: 0m1.037s 

Je publie le assembly de chaque programme dans son intégralité pour que d’autres puissent tenter la même expérience et confirmer ou contredire mon observation.

Voici la version avec l’instruction cmovge ( (a < b) ? -1 : (a > b) ):

  .file "cmp.c" .text .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .ssortingng "%d=0\n" .text .p2align 4,,15 .globl main .type main, @function main: .LFB20: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 movl $arr.2789, %ebx subq $8, %rsp .cfi_def_cfa_offset 32 .L9: leaq 4(%rbx), %rbp .L10: call rand movb %al, (%rbx) addq $1, %rbx cmpq %rbx, %rbp jne .L10 cmpq $arr.2789+4096, %rbp jne .L9 xorl %r8d, %r8d xorl %esi, %esi orl $-1, %edi .L12: xorl %ebp, %ebp .p2align 4,,10 .p2align 3 .L18: movl arr.2789(%rbp), %ecx xorl %eax, %eax .p2align 4,,10 .p2align 3 .L15: movl arr.2789(%rax), %edx xorl %ebx, %ebx cmpl %ecx, %edx movl $-1, %edx setg %bl cmovge %ebx, %edx addq $4, %rax addl %edx, %esi cmpq $4096, %rax jne .L15 addq $4, %rbp cmpq $4096, %rbp jne .L18 addl $1, %r8d cmpl $500, %r8d jne .L12 movl $.LC0, %edi xorl %eax, %eax call printf addq $8, %rsp .cfi_def_cfa_offset 24 xorl %eax, %eax popq %rbx .cfi_def_cfa_offset 16 popq %rbp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE20: .size main, .-main .local arr.2789 .comm arr.2789,4096,32 .section .note.GNU-stack,"",@progbits 

La version ci-dessous utilise la méthode sans twig ( (a > b) - (a < b) ):

  .file "cmp.c" .text .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .ssortingng "%d=0\n" .text .p2align 4,,15 .globl main .type main, @function main: .LFB20: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 movl $arr.2789, %ebx subq $8, %rsp .cfi_def_cfa_offset 32 .L9: leaq 4(%rbx), %rbp .L10: call rand movb %al, (%rbx) addq $1, %rbx cmpq %rbx, %rbp jne .L10 cmpq $arr.2789+4096, %rbp jne .L9 xorl %r8d, %r8d xorl %esi, %esi .L19: movl %ebp, %ebx xorl %edi, %edi .p2align 4,,10 .p2align 3 .L24: movl %ebp, %ecx xorl %eax, %eax jmp .L22 .p2align 4,,10 .p2align 3 .L20: movl arr.2789(%rax), %ecx .L22: xorl %edx, %edx cmpl %ebx, %ecx setg %cl setl %dl movzbl %cl, %ecx subl %ecx, %edx addl %edx, %esi addq $4, %rax cmpq $4096, %rax jne .L20 addq $4, %rdi cmpq $4096, %rdi je .L21 movl arr.2789(%rdi), %ebx jmp .L24 .L21: addl $1, %r8d cmpl $500, %r8d jne .L19 movl $.LC0, %edi xorl %eax, %eax call printf addq $8, %rsp .cfi_def_cfa_offset 24 xorl %eax, %eax popq %rbx .cfi_def_cfa_offset 16 popq %rbp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE20: .size main, .-main .local arr.2789 .comm arr.2789,4096,32 .section .note.GNU-stack,"",@progbits 

Celui-ci n’a pas de twigs et ne souffre pas de débordement ou de débordement:

 return (a > b) - (a < b); 

Avec gcc -O2 -S , ceci est compilé dans les six instructions suivantes:

 xorl %eax, %eax cmpl %esi, %edi setl %dl setg %al movzbl %dl, %edx subl %edx, %eax 

Voici un code pour comparer différentes implémentations de comparaison:

 #include  #include  #define COUNT 1024 #define LOOPS 500 #define COMPARE compare2 #define USE_RAND 1 int arr[COUNT]; int compare1 (int a, int b) { if (a < b) return -1; if (a > b) return 1; return 0; } int compare2 (int a, int b) { return (a > b) - (a < b); } int compare3 (int a, int b) { return (a < b) ? -1 : (a > b); } int compare4 (int a, int b) { __asm__ __volatile__ ( "sub %1, %0 \n\t" "jno 1f \n\t" "cmc \n\t" "rcr %0 \n\t" "1: " : "+r"(a) : "r"(b) : "cc"); return a; } int main () { for (int i = 0; i < COUNT; i++) { #if USE_RAND arr[i] = rand(); #else for (int b = 0; b < sizeof(arr[i]); b++) { *((unsigned char *)&arr[i] + b) = rand(); } #endif } int sum = 0; for (int l = 0; l < LOOPS; l++) { for (int i = 0; i < COUNT; i++) { for (int j = 0; j < COUNT; j++) { sum += COMPARE(arr[i], arr[j]); } } } printf("%d=0\n", sum); return 0; } 

Les résultats sur mon système 64 bits, compilés avec gcc -std=c99 -O2 , pour les nombres entiers positifs ( USE_RAND=1 ):

 compare1: 0m1.118s compare2: 0m0.756s compare3: 0m1.101s compare4: 0m0.561s 

En dehors des solutions C uniquement, celle que j'ai proposée était la plus rapide. La solution de user315052 était plus lente malgré la compilation de seulement 5 instructions. Le ralentissement est probable car, malgré une instruction de moins, il existe une instruction conditionnelle ( cmovge ).

Dans l'ensemble, l'implémentation de l'assemblage à 4 instructions de FredOverflow était la plus rapide lorsqu'elle était utilisée avec des entiers positifs. Cependant, ce code n'étudie que la plage de nombres entiers RAND_MAX, de sorte que le test à 4 instulsions est biaisé, car il gère les débordements séparément et ceux-ci ne se produisent pas dans le test; la vitesse peut être due à une prédiction de twig réussie.

Avec une gamme complète d'entiers ( USE_RAND=0 ), la solution à 4 instructions est en fait très lente (d'autres sont les mêmes):

 compare4: 0m1.897s 

Ok, j’ai réussi à le ramener à quatre instructions 🙂 L’idée de base est la suivante:

La moitié du temps, la différence est assez petite pour tenir dans un entier. Dans ce cas, retournez simplement la différence. Sinon, déplacez le numéro un à droite. La question cruciale est la suivante: dans quelle mesure doit-on évoluer vers la MSB?

Regardons deux exemples extrêmes, en utilisant 8 bits au lieu de 32 bits par souci de simplicité:

  10000000 INT_MIN 01111111 INT_MAX --------- 000000001 difference 00000000 shifted 01111111 INT_MAX 10000000 INT_MIN --------- 111111111 difference 11111111 shifted 

Le décalage du bit de retenue donnerait 0 pour le premier cas (bien que INT_MIN ne soit pas égal à INT_MAX ) et un nombre négatif pour le second cas (bien que INT_MAX ne soit pas plus petit que INT_MIN ).

Mais si nous retournons le report avant de faire le changement, nous obtenons des chiffres sensibles:

  10000000 INT_MIN 01111111 INT_MAX --------- 000000001 difference 100000001 carry flipped 10000000 shifted 01111111 INT_MAX 10000000 INT_MIN --------- 111111111 difference 011111111 carry flipped 01111111 shifted 

Je suis sûr qu’il y a une raison mathématique profonde pour laquelle il est logique de retourner le document, mais je ne le vois pas encore.

 int compare_int(int a, int b) { __asm__ __volatile__ ( "sub %1, %0 \n\t" "jno 1f \n\t" "cmc \n\t" "rcr %0 \n\t" "1: " : "+r"(a) : "r"(b) : "cc"); return a; } 

J’ai testé le code avec un million d’entrées aléatoires plus toutes les combinaisons de INT_MIN, -INT_MAX, INT_MIN / 2, -1, 0, 1, INT_MAX / 2, INT_MAX / 2 + 1, INT_MAX. Tous les tests ont réussi. Pouvez-vous me prouver le contraire?

Pour ce que ça vaut, je mets en place une implémentation SSE2. vec_compare1 utilise la même approche que compare2 mais ne nécessite que trois instructions arithmétiques SSE2:

 #include  #include  #include  #define COUNT 1024 #define LOOPS 500 #define COMPARE vec_compare1 #define USE_RAND 1 int arr[COUNT] __atsortingbute__ ((aligned(16))); typedef __m128i vSInt32; vSInt32 vec_compare1 (vSInt32 va, vSInt32 vb) { vSInt32 vcmp1 = _mm_cmpgt_epi32(va, vb); vSInt32 vcmp2 = _mm_cmpgt_epi32(vb, va); return _mm_sub_epi32(vcmp2, vcmp1); } int main () { for (int i = 0; i < COUNT; i++) { #if USE_RAND arr[i] = rand(); #else for (int b = 0; b < sizeof(arr[i]); b++) { *((unsigned char *)&arr[i] + b) = rand(); } #endif } vSInt32 vsum = _mm_set1_epi32(0); for (int l = 0; l < LOOPS; l++) { for (int i = 0; i < COUNT; i++) { for (int j = 0; j < COUNT; j+=4) { vSInt32 v1 = _mm_loadu_si128(&arr[i]); vSInt32 v2 = _mm_load_si128(&arr[j]); vSInt32 v = COMPARE(v1, v2); vsum = _mm_add_epi32(vsum, v); } } } printf("vsum = %vd\n", vsum); return 0; } 

Le temps pour ceci est 0.137s.

Le temps pour compare2 avec le même processeur et le même compilateur est 0.674s.

Ainsi, l'implémentation de SSE2 est environ 4x plus rapide, comme on pouvait s'y attendre (car elle est à quatre dimensions).

Ce code n’a pas de twigs et utilise 5 instructions. Il peut surpasser les autres alternatives sans twigs sur les processeurs Intel récents, où les instructions cmov * sont assez coûteuses. Le désavantage est la valeur de retour non symésortingque (INT_MIN + 1, 0, 1).

 int compare_int (int a, int b) { int res; __asm__ __volatile__ ( "xor %0, %0 \n\t" "cmpl %2, %1 \n\t" "setl %b0 \n\t" "rorl $1, %0 \n\t" "setnz %b0 \n\t" : "=q"(res) : "r"(a) , "r"(b) : "cc" ); return res; } 

Cette variante n’a pas besoin d’initialisation, elle n’utilise donc que 4 instructions:

 int compare_int (int a, int b) { __asm__ __volatile__ ( "subl %1, %0 \n\t" "setl %b0 \n\t" "rorl $1, %0 \n\t" "setnz %b0 \n\t" : "+q"(a) : "r"(b) : "cc" ); return a; } 

Vous pouvez peut-être utiliser l’idée suivante (en pseudo-code; n’a pas écrit asm-code parce que je ne suis pas à l’aise avec la syntaxe):

1. Soustraire les nombres ( result = a - b )
2. Si aucun débordement, fait (l’instruction de jo et la prédiction de twig devraient très bien fonctionner ici)
3. S’il y avait un débordement, utilisez une méthode robuste ( return (a < b) ? -1 : (a > b) )

Edit: pour plus de simplicité: s’il y avait un débordement, retournez le signe du résultat, au lieu de l’étape 3 .

Vous pouvez envisager de promouvoir les entiers à des valeurs 64 bits.