c++ - entera - la division para niños
¿Cuál es la división de enteros más rápida que admite división por cero sin importar el resultado? (4)
Aquí hay algunos números concretos, en Windows usando GCC 4.7.2:
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned int result = 0;
for (int n = -500000000; n != 500000000; n++)
{
int d = -1;
for (int i = 0; i != ITERATIONS; i++)
d &= rand();
#if CHECK == 0
if (d == 0) result++;
#elif CHECK == 1
result += n / d;
#elif CHECK == 2
result += n / (d + !d);
#elif CHECK == 3
result += d == 0 ? 0 : n / d;
#elif CHECK == 4
result += d == 0 ? 1 : n / d;
#elif CHECK == 5
if (d != 0) result += n / d;
#endif
}
printf("%u/n", result);
}
Tenga en cuenta que intencionalmente no llamo a srand() , por lo que rand() siempre devuelve exactamente los mismos resultados. Tenga en cuenta también que -DCHECK=0 simplemente cuenta los ceros, por lo que es obvio cuán seguido apareció.
Ahora, compilarlo y cronometrarlo de varias maneras:
$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done
muestra resultados que se pueden resumir en una tabla:
Iterations → | 0 | 1 | 2 | 3 | 4 | 5
-------------+-------------------------------------------------------------------
Zeroes | 0 | 1 | 133173 | 1593376 | 135245875 | 373728555
Check 1 | 0m0.612s | - | - | - | - | -
Check 2 | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3 | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4 | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5 | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s
Si los ceros son raros, la versión -DCHECK=2 funciona mal. A medida que los ceros comienzan a aparecer más, el caso -DCHECK=2 comienza a funcionar significativamente mejor. Fuera de las otras opciones, realmente no hay mucha diferencia.
Para -O3 , sin embargo, es una historia diferente:
Iterations → | 0 | 1 | 2 | 3 | 4 | 5
-------------+-------------------------------------------------------------------
Zeroes | 0 | 1 | 133173 | 1593376 | 135245875 | 373728555
Check 1 | 0m0.646s | - | - | - | - | -
Check 2 | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3 | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4 | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5 | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s
Allí, la verificación 2 no tiene ningún inconveniente en comparación con los otros controles, y mantiene los beneficios ya que los ceros se vuelven más comunes.
Sin embargo, debería medir realmente para ver qué pasa con su compilador y sus datos de muestra representativos.
Resumen:
Estoy buscando la forma más rápida de calcular
(int) x / (int) y
sin obtener una excepción para y==0 . En cambio, solo quiero un resultado arbitrario.
Fondo:
Al codificar algoritmos de procesamiento de imágenes, a menudo necesito dividir por un valor alfa (acumulado). La variante más simple es el código simple C con la aritmética de enteros. Mi problema es que normalmente obtengo una división por error cero para los píxeles de resultados con alpha==0 . Sin embargo, estos son exactamente los píxeles donde el resultado no importa para nada: no me importan los valores de color de los píxeles con alpha==0 .
Detalles:
Estoy buscando algo como:
result = (y==0)? 0 : x/y;
o
result = x / MAX( y, 1 );
xey son números enteros positivos. El código se ejecuta una gran cantidad de veces en un bucle anidado, por lo que estoy buscando una manera de deshacerse de la bifurcación condicional.
Cuando y no supera el rango de bytes, estoy contento con la solución
unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];
Pero esto obviamente no funciona bien para rangos más grandes.
Supongo que la última pregunta es: ¿cuál es el truco más rápido cambiando el valor de 0 a cualquier otro valor entero, dejando intactos los demás valores?
Aclaraciones
No estoy 100% seguro de que la ramificación sea demasiado costosa. Sin embargo, se utilizan diferentes compiladores, por lo que prefiero la evaluación comparativa con pocas optimizaciones (lo que de hecho es cuestionable).
Por supuesto, los compiladores son geniales cuando se trata de dar vueltas, pero no puedo expresar el resultado de "no me importa" en C, por lo que el compilador nunca podrá usar toda la gama de optimizaciones.
El código debe ser completamente compatible con C, las plataformas principales son Linux 64 Bit con gcc y clang y MacOS.
Inspirado por algunos de los comentarios me deshice de la rama en mi compilador Pentium y gcc usando
int f (int x, int y)
{
y += y == 0;
return x/y;
}
El compilador básicamente reconoce que puede usar un indicador de condición de la prueba en la adición.
Según solicitud, el conjunto:
.globl f
.type f, @function
f:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
movl 12(%ebp), %edx
testl %edx, %edx
sete %al
addl %edx, %eax
movl 8(%ebp), %edx
movl %eax, %ecx
popl %ebp
movl %edx, %eax
sarl $31, %edx
idivl %ecx
ret
Como esta resultó ser una pregunta y respuesta tan popular, voy a elaborar un poco más. El ejemplo anterior se basa en la expresión de programación que reconoce un compilador. En el caso anterior, se usa una expresión booleana en aritmética integral y el uso de indicadores de condición se inventa en hardware para este propósito. En condiciones generales, solo se puede acceder a las marcas en C mediante el uso de expresiones idiomáticas. Es por eso que es tan difícil hacer una biblioteca de enteros de precisión múltiple portátil en C sin recurrir al ensamblado (en línea). Mi suposición es que la mayoría de los compiladores decentes entenderán el modismo anterior.
Otra forma de evitar las ramas, como también se señala en algunos de los comentarios anteriores, es la ejecución predicada. Por lo tanto, tomé el primer código de philipp y mi código y lo ejecuté a través del compilador de ARM y el compilador de GCC para la arquitectura ARM, que presenta la ejecución predicada. Ambos compiladores evitan la rama en ambas muestras de código:
La versión de Philipp con el compilador ARM:
f PROC
CMP r1,#0
BNE __aeabi_idivmod
MOVEQ r0,#0
BX lr
La versión de Philipp con GCC:
f:
subs r3, r1, #0
str lr, [sp, #-4]!
moveq r0, r3
ldreq pc, [sp], #4
bl __divsi3
ldr pc, [sp], #4
Mi código con el compilador ARM:
f PROC
RSBS r2,r1,#1
MOVCC r2,#0
ADD r1,r1,r2
B __aeabi_idivmod
Mi código con GCC:
f:
str lr, [sp, #-4]!
cmp r1, #0
addeq r1, r1, #1
bl __divsi3
ldr pc, [sp], #4
Todas las versiones aún necesitan una bifurcación para la rutina de división, porque esta versión del ARM no tiene hardware para una división, pero la prueba para y == 0 se implementa completamente a través de la ejecución predicada.
Según este link , puedes bloquear la señal SIGFPE con sigaction() (no lo he probado yo mismo, pero creo que debería funcionar).
Este es el enfoque más rápido posible si los errores de división por cero son extremadamente raros: solo paga las divisiones por cero, no por las divisiones válidas, la ruta de ejecución normal no se cambia en absoluto.
Sin embargo, el sistema operativo estará involucrado en todas las excepciones que se ignoran, lo que es costoso. Creo que deberías tener al menos mil buenas divisiones por división por cero que ignoras. Si las excepciones son más frecuentes, es probable que pague más ignorando las excepciones que verificando cada valor antes de la división.
Sin conocer la plataforma, no hay forma de conocer el método más eficiente, sin embargo, en un sistema genérico, esto puede acercarse al óptimo (usando la sintaxis del ensamblador Intel):
(supongamos que el divisor está en ecx y el dividendo está en eax )
mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx
Cuatro instrucciones no ramificadas de ciclo único más la división. El cociente estará en eax y el resto estará en edx al final. (Este tipo de muestra por qué no desea enviar un compilador para hacer un trabajo de hombre).