¿Qué técnicas para evitar la ramificación condicional, sabes?

Question

A veces, un bucle donde la CPU pasa la mayor parte del tiempo tiene algunas fallas de predicción de ramificaciones (error de predicción) muy a menudo (probabilidad de cerca de .5). He visto algunas técnicas en hilos muy aislados pero nunca en una lista. Los que conozco ya arreglan situaciones donde la condición se puede convertir en un bool y que 0/1 se usa de alguna manera para cambiar. ¿Hay otras ramas condicionales que se pueden evitar?

p. Ej. (Pseudocódigo)

loop() { 
    if (in[i] < C) 
    out[o++] = in[i++] 
    ... 
} 

pueden reescribirse, podría decirse que perder algo de lectura, con algo como esto:

loop() { 
    out[o] = in[i] // copy anyway, just don't increment 
    inc = in[i] < C // increment counters? (0 or 1) 
    o += inc 
    i += inc 
} 

También he visto técnicas en el cambio de &&-& en condicional en ciertos contextos salvaje escapando de mi mente ahora mismo. Soy un novato en este nivel de optimización, pero seguro que se siente como si tuviera que haber más.

Answer 1

Creo que la forma más común de evitar la bifurcación es aprovechar el paralelismo de bits para reducir el total de saltos presentes en el código. Cuanto más largos sean los bloques básicos, con menor frecuencia se vaciará la tubería.

Como alguien más ha mencionado, si desea hacer algo más que desenrollar bucles, y proporcionar sugerencias de bifurcación, querrá lanzarse al ensamblaje. Por supuesto, esto debe hacerse con la máxima precaución: el compilador típico puede escribir mejor ensamblaje en la mayoría de los casos que un humano. Su mejor esperanza es eliminar asperezas y hacer suposiciones que el compilador no puede deducir.

Aquí hay un ejemplo del siguiente código C:

if (b > a) b = a; 

En el montaje sin ningún tipo de saltos, mediante el uso de de manipulación de bits (y comentando extrema):

sub eax, ebx ; = a - b 
sbb edx, edx ; = (b > a) ? 0xFFFFFFFF : 0 
and edx, eax ; = (b > a) ? a - b : 0 
add ebx, edx ; b = (b > a) ? b + (a - b) : b + 0 

Nota que mientras condicionales movimientos son Los entusiastas de la asamblea se adelantaron inmediatamente, eso es solo porque se entienden fácilmente y brindan un concepto de lenguaje de nivel más alto en una sola instrucción conveniente. No son necesariamente más rápidos, no están disponibles en los procesadores más antiguos, y mapeando su código C en las correspondientes instrucciones de movimiento condicional, usted está haciendo el trabajo del compilador.

Answer 2

La generalización del ejemplo que usted da es "reemplace la evaluación condicional con matemáticas"; la evitación de la rama condicional se reduce a eso.

Lo que está sucediendo con la sustitución de && con & es que, dado que && es un cortocircuito, constituye una evaluación condicional en sí misma. & obtiene los mismos resultados lógicos si ambos lados son 0 o 1, y no es un cortocircuito. Lo mismo se aplica a || y | excepto que no necesita asegurarse de que los lados están limitados a 0 o 1 (nuevamente, solo por motivos lógicos, es decir, está utilizando el resultado solo Booleanly).

Answer 3

GCC ya es lo suficientemente inteligente como para reemplazar los condicionales con instrucciones más simples. Por ejemplo, los procesadores Intel más nuevos proporcionan cmov (movimiento condicional). Si puede usarlo, SSE2 proporciona algunas instrucciones al compare 4 integers (u 8 pantalones cortos, o 16 caracteres) a la vez.

Adicionalmente para calcular mínimo que se puede utilizar (ver estos magic tricks):

min(x, y) = x+(((y-x)>>(WORDBITS-1))&(y-x)) 

Sin embargo, prestar atención a cosas como:

c[i][j] = min(c[i][j], c[i][k] + c[j][k]); // from Floyd-Warshal algorithm 

incluso sin saltos están implicadas es mucho más lento que

int tmp = c[i][k] + c[j][k]; 
if (tmp < c[i][j]) 
    c[i][j] = tmp; 

Mi mejor estimación es que en el primer fragmento se contamina el cach e más a menudo, mientras que en el segundo no lo haces.

Answer 4

En mi opinión, si está llegando a este nivel de optimización, es probable que sea hora de pasar directamente al lenguaje ensamblador.

Esencialmente usted está contando con el compilador que genera un patrón de ensamblaje específico para aprovechar esta optimización en C de todos modos. Es difícil adivinar exactamente qué código generará un compilador, por lo que tendrías que mirarlo cada vez que se realice un pequeño cambio, ¿por qué no hacerlo en el ensamblado y terminar con él?

Answer 5

Este nivel de optimización es poco probable que haga una diferencia que valga la pena en todas las zonas menos calientes, excepto en las más populares.Suponiendo que sí (sin probarlo en un caso específico) es una forma de conjeturando, y la primera regla de optimización es no actúe en conjeturas.

Answer 6

En este nivel, las cosas dependen del hardware y del compilador. ¿El compilador que está utilizando es lo suficientemente inteligente como para compilar < sin flujo de control? gcc en x86 es lo suficientemente inteligente; lcc no es. En conjuntos de instrucciones anteriores o incorporados, es posible que no se pueda calcular < sin flujo de control.

Más allá de esta advertencia tipo Cassandra, es difícil hacer declaraciones generales útiles. Así que aquí están algunas declaraciones generales que pueden ser poco útil:

• de hardware rama de predicción moderna es terriblemente buena. Si pudieras encontrar un programa real en el que la predicción de una sucursal defectuosa costara más de un 1% -2% de desaceleración, estaría muy sorprendido.

• Los contadores de rendimiento u otras herramientas que le indican dónde encontrar errores en las bifurcaciones son indispensables.

• Si realmente se necesita para mejorar dicho código, me vería en la programación de traza y bucle desenrollado:

  • desenrollado Loop replica cuerpos de bucle y le da a su optimizador de un mayor flujo de control para trabajar con ellos.

  • La planificación de trazas identifica qué rutas son más probables de tomar, y entre otros trucos, puede ajustar las direcciones de las ramas para que el hardware de predicción de ramificaciones funcione mejor en las rutas más comunes. Con bucles desenrollados, hay más y más largos caminos, por lo que el planificador de seguimiento tiene más para trabajar con

• me gustaría ser recelosos de intentar codificar esto mismo en el montaje. Cuando salga el próximo chip con nuevo hardware de predicción de bifurcaciones, las posibilidades son excelentes de que todo su trabajo arduo se esfume. En su lugar, buscaría un compilador de optimización dirigido a comentarios.

Answer 7

La mayoría de los procesadores proporcionan una predicción de bifurcación superior al 50%. De hecho, si obtienes una mejora del 1% en la predicción de ramas, entonces probablemente puedas publicar un documento. Hay una montaña de documentos sobre este tema si está interesado.

Es mejor que se preocupe por los éxitos y errores en la caché.

Answer 8

Una extensión de la técnica demostrada en la pregunta original se aplica cuando tiene que hacer varias pruebas anidadas para obtener una respuesta. Puedes construir una pequeña máscara de bits a partir de los resultados de todas las pruebas y "buscar" la respuesta en una tabla.

if (a) { 
    if (b) { 
    result = q; 
    } else { 
    result = r; 
    } 
} else { 
    if (b) { 
    result = s; 
    } else { 
    result = t; 
    } 
} 

Si a y b son casi al azar (por ejemplo, a partir de datos arbitrario), y esto es en un bucle estrecho, entonces fallos de predicción de ramificación realmente pueden retrasar este hacia abajo. Puede escribirse como:

// assuming a and b are bools and thus exactly 0 or 1 ... 
static const table[] = { t, s, r, q }; 
unsigned index = (a << 1) | b; 
result = table[index]; 

Puede generalizar esto a varios condicionales. Lo he visto hecho para 4. Sin embargo, si el anidamiento es tan profundo, debes asegurarte de que probarlos a todos es realmente más rápido que hacer solo las pruebas mínimas sugeridas por la evaluación de cortocircuito.

Answer 9

Usando el ejemplo de Matt Joiner:

if (b > a) b = a; 

También puede hacer lo siguiente, sin tener que excavar en código ensamblador:

bool if_else = b > a; 
b = a * if_else + b * !if_else;