¿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?

109

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.

philipp
fuente
22
¿Cómo ha determinado que la rama if es demasiado cara?
djechlin
7
¿Cómo se ha determinado que no es una rama?
leemes
13
+1 para la creación de perfiles, con la predicción de rama moderna, es posible que no necesite esto. Además, ¿por qué está codificando sus propios algoritmos de procesamiento de imágenes?
TC1
8
"¿Cuál es el truco de juguete más rápido ..." y += !y¿ Quizás ? No se necesita ninguna rama para calcular eso. Se podría comparar x / (y + !y)con x / max(y, 1)y quizás también y ? (x/y) : 0. Supongo que no habrá ninguna rama en ninguno de ellos, al menos con las optimizaciones activadas.
leemes
6
Cualquiera que piense que la predicción de ramas de hoy en día significa que no tiene que hacer esto, no ha perfilado suficiente código de eliminación de ramas que se ejecute a un nivel por píxel. La predicción de rama moderna es aceptable si las 0secciones alfa son enormes y contiguas. Hay un lugar para jugar con las micro optimizaciones, y las operaciones por píxel es exactamente ese lugar.
Yakk - Adam Nevraumont

Respuestas:

107

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.

Bryan Olivier
fuente
¿Podría mostrarnos el código ensamblador resultante? ¿O cómo determinó que no hay sucursal?
Haatschii
1
Increíble. Se puede hacer constexpry evitar tipos innecesarios como este: template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); } Y si quieres 255,(lhs)/(rhs+!rhs) & -!rhs
Yakk - Adam Nevraumont
1
@leemes pero quise decir que |no &. Ooops: ( (lhs)/(rhs+!rhs) ) | -!rhsdebe establecer su valor en 0xFFFFFFFif rhsis 0y lhs/rhsif rhs!=0.
Yakk - Adam Nevraumont
1
Esto fue muy inteligente.
Theodoros Chatzigiannakis
1
¡Gran respuesta! Suelo recurrir al montaje para este tipo de cosas, pero eso siempre es horrible de mantener (por no hablar menos portátil;)).
Leo
20

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.


fuente
4
Haga que el 50% de las entradas sea d=0aleatorio, en lugar de hacerlo casi siempre d!=0, y verá más fallas de predicción de rama. La predicción de ramas es excelente si una rama se sigue casi siempre, o si el seguimiento de una rama u otra es realmente grumoso ...
Yakk - Adam Nevraumont
@Yakk La diteración es el ciclo interno, por lo que los d == 0casos se distribuyen uniformemente. ¿Es d == 0realista el 50% de los casos ?
2
¿Es realista hacer 0.002%los casos d==0? Se distribuyen por todas partes, cada 65000 iteraciones en su d==0caso. Si bien 50%puede que no suceda con frecuencia, 10%o 1%podría suceder fácilmente, o incluso 90%o 99%. La prueba como se muestra solo prueba realmente "si básicamente nunca, nunca bajas por una rama, ¿la predicción de rama hace que eliminar la rama sea inútil?", A lo que la respuesta es "sí, pero eso no es interesante".
Yakk - Adam Nevraumont
1
No, porque las diferencias serán efectivamente invisibles debido al ruido.
Joe
3
La distribución de ceros no se relaciona con la distribución encontrada en la situación del autor de la pregunta. Las imágenes que contienen una mezcla de 0 alfa y otras tienen agujeros o formas irregulares, pero (normalmente) esto no es ruido. Asumir que no sabe nada sobre los datos (y considerarlo ruido) es un error. Esta es una aplicación del mundo real con imágenes reales que pueden tener 0 alfa. Y dado que es probable que una fila de píxeles tenga todo a = 0 o todo a> 0, aprovechar la predicación de rama puede ser lo más rápido, especialmente cuando a = 0 ocurre mucho y divisiones (lentas) (más de 15 ciclos !) se evitan.
DDS
13

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).

Tyler Durden
fuente
donde esta la division?
Yakk - Adam Nevraumont
1
esto no hace la división, solo contamina el divisor, por lo que la división por cero es imposible
Tyler Durden
@Jens Timmerman Lo siento, escribí eso antes de agregar la declaración div. He actualizado el texto.
Tyler Durden
1

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.

cmaster - reinstalar a monica
fuente