c - resueltos - resta de numeros enteros

Eficiente función de comparación de enteros

Question

La función de compare es una función que toma dos argumentos a y b y devuelve un número entero que describe su orden. Si a es más pequeño que b , el resultado es un entero negativo. Si a es mayor que b , el resultado es un entero positivo. De lo contrario, a y b son iguales, y el resultado es cero.

Esta función se usa a menudo para parametrizar algoritmos de clasificación y búsqueda de bibliotecas estándar.

Implementar la función de compare para los personajes es bastante fácil; simplemente resta los argumentos:

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

Esto funciona porque generalmente se supone que la diferencia entre dos caracteres encaja en un número entero. (Tenga en cuenta que esta suposición no es válida para los sistemas donde sizeof(char) == sizeof(int) .)

Este truco no puede funcionar para comparar enteros, porque la diferencia entre dos enteros generalmente no cabe en un entero. Por ejemplo, INT_MAX - (-1) = INT_MIN sugiere que INT_MAX es menor que -1 (técnicamente, el desbordamiento conduce a un comportamiento indefinido, pero supongamos que la aritmética del módulo).

Entonces, ¿cómo podemos implementar la función de comparación de manera eficiente para enteros? Aqui esta mi primer intento:

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;
}

¿Se puede hacer en menos de 6 instrucciones? ¿Hay una manera menos directa que sea más eficiente?

Answer 1

Éste no tiene ramificaciones, y no sufre de desbordamiento o desbordamiento:

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

Con gcc -O2 -S , compila las siguientes seis instrucciones:

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

Aquí hay un código para comparar varias implementaciones de comparación:

#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;
}

Los resultados en mi sistema de 64 bits, compilado con gcc -std=c99 -O2 , para enteros positivos ( USE_RAND=1 ):

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

De las soluciones exclusivas para C, la que sugerí fue la más rápida. La solución de user315052 fue más lenta a pesar de compilar solo 5 instrucciones. La ralentización es probable porque, a pesar de tener una instrucción menos, hay una instrucción condicional ( cmovge ).

En general, la implementación del ensamble de 4 instrucciones de FredOverflow fue la más rápida cuando se utilizó con enteros positivos. Sin embargo, este código solo comparó el rango entero RAND_MAX, por lo que la prueba de 4 instucciones está sesgada, porque maneja los desbordamientos por separado, y estos no ocurren en la prueba; la velocidad puede deberse a una predicción de bifurcación exitosa.

Con un rango completo de enteros ( USE_RAND=0 ), la solución de 4 instrucciones es de hecho muy lenta (otras son las mismas):

compare4: 0m1.897s

Answer 2

De acuerdo, logré bajarlo a cuatro instrucciones :) La idea básica es la siguiente:

La mitad del tiempo, la diferencia es lo suficientemente pequeña como para caber en un número entero. En ese caso, solo devuelve la diferencia. De lo contrario, cambie el número uno a la derecha. La pregunta crucial es qué poco cambiar a la MSB entonces.

Veamos dos ejemplos extremos, usando 8 bits en lugar de 32 bits por simplicidad:

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

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

Al desplazar el bit de acarreo hacia adentro obtendría 0 para el primer caso (aunque INT_MIN no es igual a INT_MAX ) y algún número negativo para el segundo caso (aunque INT_MAX no es más pequeño que INT_MIN ).

Pero si volteamos el bit de acarreo antes de hacer el cambio, obtenemos números 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

Estoy seguro de que hay una razón matemática profunda por la que tiene sentido voltear el bit de acarreo, pero aún no lo veo.

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;
}

He probado el código con un millón de entradas aleatorias más cada combinación de INT_MIN, -INT_MAX, INT_MIN / 2, -1, 0, 1, INT_MAX / 2, INT_MAX / 2 + 1, INT_MAX. Todas las pruebas pasaron ¿Puedes demostrarme que estoy equivocado?

Answer 3

Este código no tiene ramas y usa 5 instrucciones. Puede superar a otras alternativas sin sucursales en procesadores Intel recientes, donde las instrucciones cmov * son bastante costosas. La desventaja es un valor de retorno no simétrico (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;
}

Esta variante no necesita inicialización, por lo que solo usa 4 instrucciones:

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;
}

Answer 4

Lo siguiente siempre ha demostrado ser bastante eficiente para mí:

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

Con gcc -O2 -S , compila las siguientes cinco instrucciones:

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

Como seguimiento de la excelente respuesta complementaria de Ambroz Bizjak , no estaba convencido de que su programa probara el mismo código de ensamblaje que se publicó anteriormente. Y, cuando estaba estudiando la salida del compilador más de cerca, noté que el compilador no estaba generando las mismas instrucciones que se publicaron en cualquiera de nuestras respuestas. Entonces, tomé su programa de prueba, modifiqué a mano el resultado del ensamblaje para que coincida con lo que publicamos y comparé los tiempos resultantes. Parece que las dos versiones se comparan aproximadamente de manera idéntica.

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

Estoy publicando el conjunto de cada programa en su totalidad para que otros puedan intentar el mismo experimento y confirmar o contradecir mi observación.

La siguiente es la versión con la instrucción cmovge ( (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 siguiente versión usa el método sin sucursales ( (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 5

Podría considerar promocionar los enteros a valores de 64 bits.

Answer 6

Por lo que vale, armé una implementación de SSE2. vec_compare1 utiliza el mismo enfoque que compare2 pero solo requiere tres instrucciones aritméticas 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;
}

El tiempo para esto es 0.137s.

El tiempo para compare2 con la misma CPU y compilador es 0.674s.

Por lo tanto, la implementación de SSE2 es aproximadamente 4 veces más rápida, como podría esperarse (dado que es SIMD de 4 de ancho).

Answer 7

Tal vez puedas usar la siguiente idea (en pseudocódigo; no escribí asm-code porque no me siento cómodo con la sintaxis):

1. Reste los números ( result = a - b )
2. Si no hay overflow, done (la instrucción jo y la predicción de bifurcación deberían funcionar muy bien aquí)
3. Si hubo desbordamiento, use cualquier método robusto ( return (a < b) ? -1 : (a > b) )

Editar: para una mayor simplicidad: si hubo desbordamiento, voltee el signo del resultado, en lugar del paso 3 .