¿Cómo optimizar esta línea de código C (rango de comprobación)?

Question

¿Hay alguna forma de optimizar la siguiente línea de código C (para evitar la bifurcación)?

if ((i < -threshold) || (i > threshold)) 
{ 
    counter++; 
} 

Todas las variables son enteros con signo de 16 bits. Una versión optimizada debería ser altamente portátil.

Answer 1

¿Qué tal:

counter += (i < -threshold) | (i > threshold); 

Suponiendo que el código original era válido, entonces esto debería funcionar también, de una manera portátil. El estándar dice que los operadores relacionales (<, > y así sucesivamente) devuelven un int igual a 1 en caso de éxito, o 0 en caso de falla.

ACTUALIZACIÓN

Para contestar el comentario de Sheen a continuación, el siguiente código:

int main() 
{ 
    short threshold = 10; 
    short i = 20; 
    short counter = 0; 

    counter += (i < -threshold) | (i > threshold); 

    return 0; 
} 

resultados en la siguiente desensamblador en x86 utilizando GCC, sin optimizaciones:

push %rbp 
    mov %rsp,%rbp 
    movw $0xa,-6(%rbp) 
    movw $0x14,-4(%rbp) 
    movw $0x0,-2(%rbp) 
    movswl -4(%rbp),%edx 
    movswl -6(%rbp),%eax 
    neg %eax 
    cmp %eax,%edx 
    setl %dl 
    movzwl -4(%rbp),%eax 
    cmp -6(%rbp),%ax 
    setg %al 
    or  %edx,%eax 
    movzbw %al,%dx 
    movzwl -2(%rbp),%eax 
    lea (%rdx,%rax,1),%eax 
    mov %ax,-2(%rbp) 
    mov $0x0,%eax 
    leaveq 
    retq 

Answer 2

Comparar el absoluto de ambos

short imask = i >> sizeof(short) * 8 - 1; //compute the sign bit 1 or 0 
short tmask = threshold >> sizeof(short) * 8 - 1; //compute the sign bit 1 or 0 

short iabsolute = (i + imask)^imask; // compute i absolute 
short tabsolute = (threshold + tmask)^tmask; // compute threshold absolute 

counter += iabsolute > tabsolute; 

Answer 3

Dependiendo de la distribución de los valores de 'i', su CPU puede almacenar en caché la predicción de bifurcación por usted mejor que cualquier cambio de código que pueda hacer. Ver http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/ para una reseña interesante. Reddit discusión aquí: http://www.reddit.com/r/programming/comments/c7ues/fast_and_slow_ifstatements_branch_prediction_in/

Answer 4

Usted puede utilizar el siguiente truco que reduce las ramas de una misma rama:

if (((unsigned) (i + threshold)) > (threshold << 1)) 
{ 
    counter++; 
} 

o, por el pedante:

if (((unsigned) i + (unsigned) threshold) > ((unsigned) threshold << 1)) 
{ 
    counter++; 
} 

Answer 5

Esto se basa en bit twiddling hacks, (muy recomendable)

#define CHAR_BIT 8 

int main() 
{ 
    int i=-3; // example input 
    int treshold=2; // example treshold 
    int count=0; 
    // step 1: find the absolute value of i 
    unsigned int r; // the result goes here 
    int const mask = i >> (sizeof(int) * CHAR_BIT - 1); 
    r = (i + mask)^mask; 
    // step 2: compute the sign of the difference 
    // sign becomes 0 (if r<=treshold) 
    // sign becomes 1 otherwise 
    int sign = 1^((unsigned int)(r-treshold-1) >> (sizeof(int) * CHAR_BIT - 1)); 
    count+=sign; 
    return count; 
} 

Esto funciona para 32 bits enteros, la adaptación a 16 bits debe ser fácil. Compila con g ++.

La velocidad depende de la procesador utilizado. La ramificación podría ser más rápida después de todo.

Answer 6

Oli Charlesworth, creo, tiene la idea correcta. Sin embargo, sospecho que se puede optimizar aún más (a expensas de la legibilidad).

El umbral se puede normalizar a cero para eliminar una comparación.

Es decir, ...

counter += ((unsigned) (i + threshhold) < (unsigned) (threshhold + threshhold)); 

Answer 7

Hay un lenguaje estándar para la gama de comprobación con una sola instrucción de comparación.Dice así:

(unsigned)x - a <= (unsigned)b - a /* a <= x <= b */ 
(unsigned)x - a < (unsigned)b - a /* a <= x < b */ 

Como un ejemplo común (esta versión si isdigit se garantiza que sea correcta por la norma):

(unsigned)ch - '0' < 10 

Si el tipo de original es mayor que int (por ejemplo long long) luego deberá usar tipos sin firmar más grandes (por ejemplo, unsigned long long). Si a y b son constantes o ya tiene tipo sin signo, o si conoce b-a no se desbordará, se puede omitir el elenco de b.

Para que este método funcione, naturalmente debe tener a<=b y los tipos/valores debe ser tal que la expresión original (es decir a <= x && x <= b o similar) se comporta matemáticamente correctamente. Por ejemplo, si x fueron firmados y sin firmar b, x<=b podría evaluar en falso cuando x=-1 y b=UINT_MAX-1. Siempre que sus tipos originales estén todos firmados o sean más pequeños que el tipo sin firmar al que se lanza, esto no es un problema.

En cuanto a cómo este "truco" funciona, es puramente determinar, después de la reducción de módulo UINT_MAX+1, si x-a se encuentra en el rango de 0 a b-a.

En su caso, creo que el siguiente debería funcionar bien:

(unsigned)i + threshold > 2U * threshold; 

Si threshold no cambia entre las iteraciones del bucle, el compilador probablemente puede mantener tanto threshold y 2U*threshold en los registros.

Hablando de optimizaciones, un buen compilador debe optimizar su prueba original gama de usar la aritmética sin signo donde se sabe que se cumplan las restricciones. Sospecho que muchos lo hacen con a y b constante, pero tal vez no con expresiones más complejas. Incluso si el compilador puede optimizar, sin embargo, el lenguaje (unsigned)x-a<b-a sigue siendo de gran utilidad en las macros en las que desea asegurarse de que x se evalúa exactamente una vez.

Answer 8

Oh, qué mal la pregunta ya ha sido contestada. Parafraseando la respuesta de Oli, el código

#include <stdint.h> 
int main() 
{ 
    int32_t threshold_square = 100; 
    int16_t i = 20; 
    int16_t counter = 0; 

    counter += ((int32_t) i * i > threshold_square); 

    return 0; 
} 

se obtiene la siguiente ensamblador x86 usando GCC sin optimizaciones

pushq %rbp 
movq %rsp, %rbp 
movl $100, -8(%rbp) 
movw $20, -2(%rbp) 
movw $0, -4(%rbp) 
movswl -2(%rbp),%edx 
movswl -2(%rbp),%eax 
imull %edx, %eax 
cmpl -8(%rbp), %eax 
setg %al 
movzbl %al, %edx 
movzwl -4(%rbp), %eax 
leal (%rdx,%rax), %eax 
movw %ax, -4(%rbp) 
movl $0, %eax 
leave 
ret 

que es cuatro instrucciones a menos que el uso de (i < -threshold) | (i > threshold).

Si esto es mejor o no, por supuesto, depende de la arquitectura.

(El uso de stdint.h a efectos ilustrativos, por estricta C89 reemplazar con lo que es relevante para el sistema de destino.)

Answer 9

¿Qué hay de malo en el código original? ¿Realmente necesita optimizar la mano?

Cualquier compilador decente debería ser capaz de optimizarlo muy bien. Cualquier optimización de la mano probablemente solo conduzca a la ofuscación.

Answer 10

Este código no tiene una rama altamente portátil (sin embargo, la implementación de abs puede tener uno).

#include <stdlib.h> 
counter += abs(i) > threshold; 

Esa es la expresión estándar más simple.

Si su compilador no utiliza macro optimizado para abs() puede usar su propia función macro/en línea.

que son ejemplos, que la naturaleza uso del formato de complemento a dos usada en la mayoría de las máquinas:

#define ABS(x) ((x)*(((x)>>15)|1)) 

#define ABS(x) ((x)-((x)>>15)^((x)>>15)) 

También es posible reemplazar operador de comparación con la expresión de la siguiente manera:

#define LESS(x, y) (-((x)-(y))>>15)) 

código resultante:

counter -= ((threshold - abs(i)) >> 15); 

Todas esas macros se basan en hechos, que cambian a la derecha al número de bits menos uno de valor positivo o cero se evalúa a cero, y de negativo se evalúa a menos uno. Pero esa implementación está definida.