¿Cuál es la división de enteros más rápida que admite la división por cero sin importar cuál sea el resultado?

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.

Antecedentes:

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 C simple con aritmética de enteros. Mi problema es que normalmente obtengo una división por error cero para los píxeles de resultado con alpha==0. Sin embargo, estos son exactamente los píxeles en los que el resultado no importa en absoluto: 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 forma de deshacerme de la ramificación condicional.

Cuando y no excede el rango de bytes, estoy satisfecho 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 pregunta final es: ¿Cuál es el truco más rápido que cambia de 0 a cualquier otro valor entero, dejando todos los demás valores sin cambios?

Aclaraciones

No estoy 100% seguro de que la ramificación sea demasiado cara. Sin embargo, se utilizan diferentes compiladores, por lo que prefiero la evaluación comparativa con pequeñas optimizaciones (lo que de hecho es cuestionable).

Por supuesto, los compiladores son geniales cuando se trata de juegos de bits, pero no puedo expresar el resultado "no me importa" en C, por lo que el compilador nunca podrá usar la gama completa de optimizaciones.

El código debe ser totalmente compatible con C, las principales plataformas son Linux de 64 bits con gcc & clang y MacOS.

Inspirado por algunos de los comentarios, me deshice de la rama en mi Pentium y el gcccompilador 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 de la asamblea:

.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, elaboraré un poco más. El ejemplo anterior se basa en el lenguaje 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 general, las banderas solo son accesibles en C mediante el uso de idiom. 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 ensamblaje (en línea). Supongo que la mayoría de los compiladores decentes entenderán el idioma anterior.

Otra forma de evitar las ramas, como también se señaló 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 una ejecución predicada. Ambos compiladores evitan la rama en ambas muestras de código:

Versión de Philipp con el compilador ARM:

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

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 rama a la rutina de división, porque esta versión de ARM no tiene hardware para una división, pero la prueba y == 0se implementa completamente a través de la ejecución predicada.

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 no estoy llamando intencionalmente srand(), por lo que rand()siempre devuelve exactamente los mismos resultados. Tenga en cuenta también que -DCHECK=0simplemente cuenta los ceros, por lo que es obvio con qué frecuencia apareció.

Ahora, compilándolo y cronometrando de varias formas:

$ 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 la salida que se puede 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 -DCHECK=2versión funciona mal. A medida que comienzan a aparecer más ceros, el -DCHECK=2caso comienza a funcionar significativamente mejor. De las otras opciones, realmente no hay mucha diferencia.

Porque -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í, el cheque 2 no tiene inconvenientes en comparación con los otros cheques, y mantiene los beneficios a medida que los ceros se vuelven más comunes.

Sin embargo, realmente debería medir para ver qué sucede con su compilador y sus datos de muestra representativos.

Sin conocer la plataforma, no hay forma de conocer el método más eficiente exacto, sin embargo, en un sistema genérico esto puede acercarse al óptimo (usando la sintaxis de ensamblador Intel):

(suponga que el divisor está adentro ecxy el dividendo está adentro eax)

mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx

Cuatro instrucciones de ciclo único no ramificadas más la división. El cociente estará adentro eaxy el resto edxal final. (Este tipo de muestra por qué no desea enviar un compilador para hacer el trabajo de un hombre).

De acuerdo con este enlace , puede 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 por las divisiones por cero, no por las divisiones válidas, la ruta de ejecución normal no cambia en absoluto.

Sin embargo, el sistema operativo estará involucrado en todas las excepciones que se ignoren, lo cual es costoso. Creo que deberías tener al menos mil buenas divisiones por división entre cero que ignoras. Si las excepciones son más frecuentes que eso, probablemente pagará más ignorando las excepciones que verificando cada valor antes de la división.