tipos - ¿Qué tan eficiente es una instrucción if en comparación con una prueba que no usa un if?(C++)

switch c++

Question

Necesito un programa para obtener el menor de dos números, y me pregunto si usar un estándar "si x es menor que y"

int a, b, low;
if (a < b) low = a;
else low = b;

es más o menos eficiente que esto:

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

(o la variación de poner int delta = a - b en la parte superior y volver a colocar instancias de a - b con eso).

Me pregunto cuál de estos sería más eficiente (o si la diferencia es demasiado minúscula para ser relevante), y la eficacia de las declaraciones if-else versus las alternativas en general.

Answer 1

Me pregunto cuál de estos sería más eficiente (o si la diferencia es minúscula para ser relevante), y la eficacia de las declaraciones if-else frente a las alternativas en general.

Las CPU de escritorio / servidor están optimizadas para la canalización. El segundo es teóricamente más rápido porque la CPU no tiene que ramificarse y puede utilizar múltiples ALU para evaluar partes de la expresión en paralelo. Más código no ramificado con operaciones independientes entremezcladas es mejor para tales CPU. (Pero incluso eso ahora es negado por las modernas instrucciones "condicionales" de la CPU que también permiten que el primer código sea menos ramificado).

En las CPUs integradas, la bifurcación es a menudo menos costosa (en relación con todo lo demás), ni tienen muchas ALU de repuesto para evaluar las operaciones fuera de servicio (eso es si admiten la ejecución fuera de orden en absoluto). Menos código / datos es mejor: los cachés también son pequeños. (Incluso he visto usos de buble-sort en aplicaciones integradas: el algoritmo usa menos memoria / código y lo suficientemente rápido para pequeñas cantidades de información).

Importante: no te olvides de las optimizaciones del compilador. Usando muchos trucos, los compiladores a veces pueden eliminar la ramificación ellos mismos: alineación, propagación constante, refactorización, etc.

Pero al final yo diría que sí, que la diferencia es minúscula para ser relevante. A largo plazo, el código legible gana.

Tal como están las cosas en la parte frontal de la CPU, es más gratificante invertir tiempo ahora para hacer que el código tenga múltiples subprocesos y sea compatible con OpenCL.

Answer 2

(Descargo de responsabilidad: lo siguiente trata de optimizaciones de muy bajo nivel que a menudo no son necesarias. Si continúa leyendo, renuncia a su derecho a quejarse de que las computadoras son rápidas y de que nunca hay motivos para preocuparse por este tipo de cosas).

Una ventaja de eliminar un enunciado if es evitar las penalizaciones por predicción de sucursal.

Las penalizaciones por predicción de ramas generalmente son solo un problema cuando la derivación no se predice fácilmente. Una rama se predice fácilmente cuando casi siempre se toma / no se toma, o sigue un patrón simple. Por ejemplo, la rama en una declaración de ciclo se toma todas las veces, excepto la última, por lo que se predice fácilmente. Sin embargo, si tiene código como

a = random() % 10
if (a < 5)
print "Less"
else
print "Greater"

entonces esta rama no se predice fácilmente, y con frecuencia incurrirá en la penalización de predicción asociada con borrar las instrucciones de caché e inversión que se ejecutaron en la parte incorrecta de la rama.

Una forma de evitar este tipo de penalizaciones es utilizar el operador ternario ( ?: :). En casos simples, el compilador generará instrucciones de movimiento condicionales en lugar de ramas.

Asi que

int a, b, low;
if (a < b) low = a;
else low = b;

se convierte

int a, b, low;
low = (a < b) ? a : b

y en el segundo caso una instrucción de ramificación no es necesaria. Además, es mucho más claro y más legible que su implementación de intercambio de bits.

Por supuesto, esta es una micro-optimización que es poco probable que tenga un impacto significativo en su código.

Answer 3

A menos que realmente estés tratando de controlar la eficiencia, no creo que sea algo de lo que tengas que preocuparte.

Mi simple pensamiento es que el if sería más rápido porque está comparando una cosa, mientras que el otro código está haciendo varias operaciones. Pero de nuevo, me imagino que la diferencia es minúscula.

Answer 4

Al igual que con cualquier optimización de bajo nivel, pruébela en la configuración de CPU / placa de destino.

En mi compilador (gcc 4.5.1 en x86_64), el primer ejemplo se convierte

cmpl %ebx, %eax
cmovle %eax, %esi

El segundo ejemplo se convierte

subl %eax, %ebx
movl %ebx, %edx
sarl $31, %edx
andl %ebx, %edx
leal (%rdx,%rax), %esi

No estoy seguro si el primero es más rápido en todos los casos, pero apuesto a que sí.

Answer 5

Compilando esto en gcc 4.3.4, amd64 (core 2 duo), Linux:

int foo1(int a, int b)
{
int low;
if (a < b) low = a;
else low = b;
return low;
}
int foo2(int a, int b)
{
int low;
low = b + ((a - b) & ((a - b) >> 31));
return low;
}

Yo obtengo:

foo1:
cmpl %edi, %esi
cmovle %esi, %edi
movl %edi, %eax
ret
foo2:
subl %esi, %edi
movl %edi, %eax
sarl $31, %eax
andl %edi, %eax
addl %esi, %eax
ret

... que estoy seguro de que no contará para las predicciones de bifurcación, ya que el código no salta. Además, la versión non-statement es 2 instrucciones más largas. Creo que continuaré la codificación y dejaré que el compilador haga su trabajo.

Answer 6

De cualquier manera, el ensamblaje solo tendrá unas pocas instrucciones y de cualquier forma tomará unos picosegundos para que se ejecuten esas instrucciones.

Perfilaría la aplicación y concentraría sus esfuerzos de optimización en algo más valioso.

Además, el tiempo ahorrado por este tipo de optimización no valdrá la pena el tiempo perdido por cualquiera que intente mantenerlo.

Para declaraciones simples como esta, el operador ternario me parece muy intuitivo:

low = (a < b) ? a : b;

Claro y conciso.

Answer 7

El mayor problema es que su segundo ejemplo no funcionará en máquinas de 64 bits .

Sin embargo, incluso descuidando eso, los compiladores modernos son lo suficientemente inteligentes como para considerar la predicción sin sucursales en todos los casos posibles, y comparar las velocidades estimadas. Entonces, tu segundo ejemplo probablemente sea más lento

No habrá diferencia entre la instrucción if y el uso de un operador ternario, ya que incluso los compiladores más tontos son lo suficientemente inteligentes como para reconocer este caso especial.

[Editar] Debido a que creo que este es un tema tan interesante, he escrito una publicación en el blog sobre él.

Answer 8

Había escrito el simulador de lógica ternaria no hace mucho, y esta pregunta me resultó viable, ya que afecta directamente a la velocidad de ejecución de mi intérprete; Debía simular toneladas y toneladas de compuertas lógicas ternarias lo más rápido posible.

En un sistema ternario codificado en binario, un trit se empaqueta en dos bits. El bit más significativo significa negativo y menos significativo significa positivo. El caso "11" no debería ocurrir, pero debe manejarse adecuadamente y amenazarse con 0.

Considere la función en inline int bct_decoder( unsigned bctData ) , que debería devolver nuestro trit formateado como entero regular -1, 0 o 1; Como observé, hay 4 enfoques: los llamé "cond", "mod", "math" y "lut"; Vamos a investigarlos

Primero se basa en jz | jnz y jl | jb saltos condicionales, por lo tanto cond. Su rendimiento no es bueno en absoluto, porque depende de un pronosticador de bifurcación. Y lo que es peor, varía, porque se desconoce si habrá una rama o dos a priori. Y aquí hay un ejemplo:

inline int bct_decoder_cond( unsigned bctData ) {
unsigned lsB = bctData & 1;
unsigned msB = bctData >> 1;
return
( lsB == msB ) ? 0 : // most possible -> make zero fastest branch
( lsB > msB ) ? 1 : -1;
}

Esta es la versión más lenta, podría implicar 2 ramas en el peor de los casos y esto es algo donde falla la lógica binaria. En mi 3770k, produce alrededor de 200MIPS en promedio en datos aleatorios. (aquí y después - cada prueba es un promedio de 1000 intentos en un conjunto de datos de 2mb aleatoriamente llenos)

El siguiente se basa en el operador de módulo y su velocidad está en algún punto entre el primero y el tercero, pero es definitivamente más rápido: 600 MIPS:

inline int bct_decoder_mod( unsigned bctData ) {
return ( int )( ( bctData + 1 ) % 3 ) - 1;
}

El siguiente es un enfoque sin sucursales, que involucra solo las matemáticas, por lo tanto, las matemáticas; no asume instrunciones de salto en absoluto:

inline int bct_decoder_math( unsigned bctData ) {
return ( int )( bctData & 1 ) - ( int )( bctData >> 1 );
}

Esto hace lo que debería, y se comporta realmente bien. Para comparar, el rendimiento estimado es 1000 MIPS, y es 5 veces más rápido que la versión ramificada. Probablemente, la versión ramificada se ralentiza debido a la falta de soporte nativo firmado de 2 bits. Pero en mi aplicación es una versión bastante buena en sí misma.

Si esto no es suficiente, podemos ir más allá, teniendo algo especial. Luego se llama enfoque de tabla de búsqueda:

inline int bct_decoder_lut( unsigned bctData ) {
static const int decoderLUT[] = { 0, 1, -1, 0 };
return decoderLUT[ bctData & 0x3 ];
}

En mi caso, un trit ocupaba solo 2 bits, por lo que la tabla lut era solo 2b * 4 = 8 bytes, y valía la pena intentarlo. Se adapta a la caché y funciona a una velocidad increíble de 1400-1600 MIPS, aquí es donde la precisión de mi medición está bajando. Y eso es una aceleración de 1.5 veces desde el enfoque matemático rápido. Eso es porque solo tiene un resultado precalculado y una sola instrucción AND . Lamentablemente, los cachés son pequeños y (si la longitud de su índice es mayor que varios bits) simplemente no puede usarlos.

Así que creo que respondí tu pregunta, sobre cómo podría ser el código ramificado / sin sucursales. La respuesta es mucho mejor y con muestras detalladas, la aplicación en el mundo real y los resultados de las mediciones de rendimiento real.

Answer 9

Para algo tan simple como esto, ¿por qué no simplemente experimentar y probarlo?

En general, harías un perfil primero, identifica esto como un punto de acceso público, experimentas con un cambio y ves el resultado.

Escribí un programa simple que compara ambas técnicas pasando en números aleatorios (para que no veamos la predicción de rama perfecta) con Visual C ++ 2010. ¿La diferencia entre los enfoques en mi máquina para la iteración de 100,000,000? Menos de 50ms en total, y la versión si tendía a ser más rápida. Al observar el codegen, el compilador convirtió con éxito la instrucción simple if a cmovl, evitando por completo una rama.

Answer 10

Por qué low = a; en el if y low = a; en el else ? Y, ¿por qué 31 ? Si 31 tiene algo que ver con el tamaño de la palabra de la CPU, ¿qué pasa si el código se va a ejecutar en una CPU de diferente tamaño?

La otra ... forma parece más legible. Me gusta que los programas sean tan legibles para los humanos como lo son para los compiladores.

Answer 11

Respuesta actualizada tomando el estado actual (2018) de la vectorización del compilador. Ver la respuesta de Danben para el caso general donde la vectorización no es una preocupación.

Resumen de TLDR : evitar if s puede ayudar con la vectorización.

Como SIMD sería demasiado complejo para permitir la bifurcación en algunos elementos, pero no en otros, ningún código que contenga una instrucción if no podrá vectorizarse a menos que el compilador conozca una técnica de superoptimización que pueda reescribirla en un conjunto de operaciones sin sucursales. No conozco ningún compilador que esté haciendo esto como una parte integrada del pase de vectorización (Clang hace algo de esto independientemente, pero no específicamente para ayudar a la vectorización de AFAIK)

Usando el ejemplo provisto por OP:

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

Muchos compiladores pueden vectorizar esto para que sea aproximadamente equivalente a:

__m128i low128i(__m128i a, __m128i b){
__m128i diff, tmp;
diff = _mm_sub_epi32(a,b);
tmp = _mm_srai_epi32(diff, 31);
tmp = _mm_and_si128(tmp,diff);
return _mm_add_epi32(tmp,b);
}

Esta optimización requeriría que los datos se desplegaran de una manera que lo permitiera, pero podría ampliarse a __m256i con avx2 o __m512i con avx512 (e incluso desenrollar bucles para aprovechar registros adicionales) u otras instrucciones simd en otras arquitecturas. Otra ventaja es que estas instrucciones son todas de baja latencia, altas instrucciones de rendimiento (latencias de ~ 1 y rendimientos recíprocos en el rango de 0.33 a 0.5, muy rápido en relación con el código no vectorizado)

No veo ninguna razón por la cual los compiladores no pudieron optimizar una instrucción if en un movimiento condicional vectorizado (excepto que las operaciones x86 correspondientes solo funcionan en ubicaciones de memoria y tienen bajo rendimiento y otras arquitecturas como arm pueden carecer por completo) pero podría hacerse por haciendo algo como:

void lowhi128i(__m128i *a, __m128i *b){ // does both low and high
__m128i _a=*a, _b=*b;
__m128i lomask = _mm_cmpgt_epi32(_a,_b),
__m128i himask = _mm_cmpgt_epi32(_b,_a);
_mm_maskmoveu_si128(_b,lomask,a);
_mm_maskmoveu_si128(_a,himask,b);
}

Sin embargo, esto tendría una latencia mucho más alta debido a las lecturas y escrituras de la memoria y un menor rendimiento (mayor / peor rendimiento recíproco) que el ejemplo anterior.

Answer 12

Si es por Gnu C ++, intente esto

int min = i <? j;

No lo he perfilado, pero creo que definitivamente es el que debe vencer.

Answer 13

Una cosa de la que debes desconfiarte cuando entres en tipos de hacks realmente pequeños es cómo pueden interactuar con las optimizaciones del compilador que tienen lugar después de la creación. Por ejemplo, el procedimiento legible

int foo (int a, int b) {
return ((a < b) ? a : b);
}

Es probable que se compile en algo muy eficiente en cualquier caso, pero en algunos casos puede ser incluso mejor. Supongamos, por ejemplo, que alguien escribe

int bar = foo (x, x+3);

Después de la alineación, el compilador reconocerá que 3 es positivo, y luego podrá usar el hecho de que el desbordamiento firmado no está definido para eliminar la prueba por completo, para obtener

int bar = x;

Está mucho menos claro cómo el compilador debería optimizar su segunda implementación en este contexto. Este es un ejemplo bastante artificial, por supuesto, pero las optimizaciones similares son realmente importantes en la práctica. Por supuesto, no debe aceptar una salida de compilador incorrecta cuando el rendimiento es crítico, pero es probable que vea si puede encontrar un código claro que produzca un buen resultado antes de recurrir al código para que la próxima versión del compilador, sorprendentemente mejorada, no lo haga. ser capaz de optimizar a la muerte.

Answer 14

Una cosa que señalaré es que no me he dado cuenta de que una optimización como esta puede verse fácilmente abrumada por otros problemas. Por ejemplo, si está ejecutando esta rutina en dos grandes matrices de números (o peor aún, pares de números dispersos en la memoria), el costo de recuperar los valores en las CPU de hoy en día puede detener fácilmente las tuberías de ejecución de la CPU.

Answer 15

resultados de perfil con gcc -o foo -g -p -O0, Solaris 9 v240

 %Time Seconds Cumsecs #Calls msec/call Name
36.8 0.21 0.21 8424829 0.0000 foo2
28.1 0.16 0.37 1 160. main
17.5 0.10 0.4716850667 0.0000 _mcount
17.5 0.10 0.57 8424829 0.0000 foo1
0.0 0.00 0.57 4 0. atexit
0.0 0.00 0.57 1 0. _fpsetsticky
0.0 0.00 0.57 1 0. _exithandle
0.0 0.00 0.57 1 0. _profil
0.0 0.00 0.57 1000 0.000 rand
0.0 0.00 0.57 1 0. exit

código:

int
foo1 (int a, int b, int low)
{
if (a < b)
low = a;
else
low = b;
return low;
}
int
foo2 (int a, int b, int low)
{
low = (a < b) ? a : b;
return low;
}
int main()
{
int low=0;
int a=0;
int b=0;
int i=500;
while (i--)
{
for(a=rand(), b=rand(); a; a--)
{
low=foo1(a,b,low);
low=foo2(a,b,low);
}
}
return 0;
}

En base a los datos, en el entorno anterior, no se encontró que fuera verdadero el opuesto exacto de varias creencias aquí expresadas. Tenga en cuenta el "en este entorno" Si la construcción fue más rápido que el ternario? : construir

Answer 16

Respuesta simple: Un salto condicional va a ser más eficiente que dos restas, una suma, un bit a bit y una operación de cambio combinada. He sido suficientemente instruido en este punto (ver los comentarios) que ya no soy lo suficientemente seguro como para decir que generalmente es más eficiente.

Respuesta pragmática: de cualquier manera, no está pagando casi tanto por los ciclos de CPU adicionales como lo está por el tiempo que le lleva a un programador averiguar qué está haciendo ese segundo ejemplo. Programa de legibilidad primero, eficiencia en segundo lugar.