c - resueltos - resta de numeros enteros
Eficiente función de comparación de enteros (7)
É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
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?
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?
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;
}
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
Podría considerar promocionar los enteros a valores de 64 bits.
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).
Tal vez puedas usar la siguiente idea (en pseudocódigo; no escribí asm-code porque no me siento cómodo con la sintaxis):
- Reste los números (
result = a - b) - Si no hay overflow, done (la instrucción
joy la predicción de bifurcación deberían funcionar muy bien aquí) - 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 .