Fonction de comparaison d'entiers efficace

Question

L' compare fonction est une fonction qui prend deux arguments a et b et renvoie un entier décrivant leur ordre. Si a est plus petit que b, le résultat est négatif entier. Si a est plus grand que b, le résultat est certain entier positif. Sinon, a et b sont égaux, et le résultat est zéro.

Cette fonction est souvent utilisée pour paramétrer le tri et la recherche d'algorithmes de bibliothèques standard.

La mise en œuvre de l' compare fonction pour les personnages est assez facile: il vous suffit de soustraire les arguments:

int compare_char(char a, char b)
{
    return a - b;
}

Cela fonctionne parce que la différence entre les deux personnages est généralement supposé correspondre à un nombre entier. (À noter que cette hypothèse n'est pas valable pour les systèmes où l' sizeof(char) == sizeof(int).)

Cette astuce ne peut pas travailler pour comparer des nombres entiers, parce que la différence entre deux nombres entiers en général ne correspond pas à un nombre entier. Par exemple, INT_MAX - (-1) = INT_MIN suggère que INT_MAX est plus petit que -1 (techniquement, le dépassement conduit à un comportement indéfini, mais supposons que l'arithmétique modulo).

Alors, comment pouvons-nous mettre en œuvre la fonction de comparaison de l'efficacité pour les entiers? Voici mon premier essai:

int compare_int(int a, int b)
{
    int temp;
    int result;
    __asm__ __volatile__ (
        "cmp %3, %2 \n\t"
        "mov $0, %1 \n\t"

        "mov $1, %0 \n\t"
        "cmovg %0, %1 \n\t"

        "mov $-1, %0 \n\t"
        "cmovl %0, %1 \n\t"
    : "=r"(temp), "=r"(result)
    : "r"(a), "r"(b)
    : "cc");
    return result;
}

Peut-il être fait en moins de 6 instructions? Est-il moins simple façon qui soit plus efficace?

Answer 1

Celui-ci a pas de branches, et ne souffre pas de dépassement supérieur ou inférieur:

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

Avec gcc -O2 -S, cette compile le suivant six instructions:

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

Voici un code de référence de comparer les différentes implémentations:

#include <stdio.h>
#include <stdlib.h>

#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é avec gcc -std=c99 -O2, pour des entiers positifs (USE_RAND=1):

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

De C-seules les solutions, celle que j'ai proposé a été le plus rapide. user315052 la solution a été plus lente en dépit de la compilation à seulement 5 instructions. Le ralentissement est probablement parce que, malgré le fait d'avoir moins d'instruction, il y a une instruction conditionnelle (cmovge).

Dans l'ensemble, FredOverflow 4-instructions d'assemblage de la mise en œuvre a été la plus rapide lorsqu'il est utilisé avec des entiers positifs. Toutefois, ce code ne comparées de l'intervalle entier RAND_MAX, de sorte que le 4-instuction test est biaisé, car il gère les débordements séparément, et on ne peut pas se produire dans le test; la vitesse peut être dû à la réussite de la direction de la prévision.

Avec une gamme complète d'entiers (USE_RAND=0), le 4-l'instruction de la solution est en fait très lentement (les autres sont les mêmes):

compare4: 0m1.897s

Answer 2

La suite a toujours prouvé pour être assez efficace pour moi:

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

Avec gcc -O2 -S, cette compile le suivant cinq instructions:

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

---

En tant que suivi de l'Ambroz Bizjak excellent compagnon de réponse, je n'étais pas convaincu que son programme a testé de la même assemblée ce code a été affiché ci-dessus. Et, lorsque j'étais étudiant la sortie du compilateur de plus près, j'ai remarqué que le compilateur n'a pas été de générer les instructions a été publié dans une de nos réponses. Donc, j'ai pris son programme de test, la main modifié l'assemblée de sortie pour correspondre à ce que nous avons publié, et par rapport à l'résultant fois. Il semble que les deux versions comparer à peu près de la même manière.

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

Je suis annonce l'assemblage de chaque programme en plein, de sorte que d'autres peuvent tenter la même expérience, et de confirmer ou d'infirmer mon observation.

Ce qui suit est la version avec l' cmovge à l'enseignement ((a < b) ? -1 : (a > b)):

        .file   "cmp.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%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 le sans branches méthode ((a > b) - (a < b)):

        .file   "cmp.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%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

Answer 3

Bon, j'ai réussi à le faire descendre à quatre instructions :) L'idée de base est comme suit:

La moitié du temps, la différence est assez petit pour tenir dans un entier. Dans ce cas, il suffit de retourner la différence. Sinon, maj le numéro un de la droite. La question cruciale est ce que peu de changement dans le bit de poids fort puis.

Regardons deux exemples extrêmes, à l'aide de 8 bits au lieu de 32 bits pour des raisons de simplicité:

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

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

Déplacement du bit en donnerait 0 pour le premier cas (bien qu' INT_MIN n'est pas égal à INT_MAX) et certains nombre négatif pour le deuxième cas (bien qu' INT_MAX n'est pas plus petit que INT_MIN).

Mais si nous retourner le bit de retenue avant de faire la maj, nous obtenons sensible numéros:

 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 profonde mathématique raison pourquoi il est judicieux d'inverser le bit de retenue, mais je ne 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 des 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 passés. Pouvez-vous prouver que j'ai tort?

Answer 4

Pour ce que ça vaut la peine, j'ai mis en place une implémentation SSE2. vec_compare1 utilise la même approche que compare2 mais nécessite seulement trois instructions arithmétiques SSE2:

 #include <stdio.h>
#include <stdlib.h>
#include <emmintrin.h>

#define COUNT 1024
#define LOOPS 500
#define COMPARE vec_compare1
#define USE_RAND 1

int arr[COUNT] __attribute__ ((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 cela est de 0,137s.

Le temps pour compare2 avec le même processeur et le même compilateur est de 0,674s.

Ainsi, la mise en œuvre de SSE2 est environ 4 fois plus rapide, comme on pouvait s'y attendre (puisqu'il s'agit d'un SIMD à 4 bandes).

Answer 5

Ce code n'a pas de branches et utilise 5 instructions. Il peut surperformer les autres solutions sans branche sur les processeurs Intel récents, où les instructions cmov * sont assez coûteuses. L’inconvénient est une valeur de retour non symétrique (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 utilise donc seulement 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;
}