is_page - condicionales en wordpress

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

Question

A veces, un bucle en el que la CPU pasa la mayor parte del tiempo suele fallar alguna predicción de bifurcación (predicción errónea) (cerca de la probabilidad de 0.5). He visto algunas técnicas en subprocesos muy aislados pero nunca en una lista. Las que sé que ya solucionan situaciones en las que 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?

por ejemplo (pseudocódigo)

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

Puede reescribirse, posiblemente perdiendo algo de legibilidad, 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 salvaje cambio y & a & en el condicional en ciertos contextos escapando de mi mente ahora mismo. Soy un novato en este nivel de optimización, pero seguro que parece que tiene que haber más.

Answer 1

Creo que la forma más común de evitar la ramificación es aprovechar el paralelismo de bits para reducir los saltos totales presentes en su código. Cuanto más largos son los bloques básicos, menos frecuentemente se descarga la tubería.

Como lo mencionó otra persona, si desea hacer más que desenrollar los bucles y proporcionar sugerencias de ramas, querrá colocarlas en el ensamblaje. Por supuesto, esto debe hacerse con la mayor precaución: en la mayoría de los casos, su compilador típico puede escribir mejor ensamblado que un humano. Tu mejor esperanza es afeitar los bordes ásperos y hacer suposiciones que el compilador no puede deducir.

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

if (b > a) b = a;

En ensamblaje sin ningún salto, mediante la manipulación de bits (y comentarios extremos):

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

Tenga en cuenta que si bien los entusiastas de los ensamblajes saltan inmediatamente a los movimientos condicionales, eso es solo porque son fáciles de entender y brindan un concepto de lenguaje de nivel superior en una sola instrucción conveniente. No son necesariamente más rápidos, no están disponibles en procesadores antiguos y, al asignar su código C a las correspondientes instrucciones de movimiento condicional, solo está haciendo el trabajo del compilador.

Answer 2

En este nivel, las cosas dependen mucho del hardware y del compilador. ¿Es el compilador que está usando lo suficientemente inteligente como para compilar <sin flujo de control? gcc en x86 es lo suficientemente inteligente; lcc no lo es. En conjuntos de instrucciones más antiguos o integrados, puede que no sea posible calcular <sin flujo de control.

Más allá de esta advertencia similar a la de Cassandra, es difícil hacer declaraciones generales útiles. Así que aquí hay algunas declaraciones generales que pueden ser inútiles:

• El hardware moderno de predicción de ramificaciones es terriblemente bueno. Si pudiera encontrar un programa real en el que la mala predicción de las sucursales cuesta más de un 1% a un 2% de desaceleración, me sorprendería mucho.

• Los contadores de rendimiento u otras herramientas que le indiquen dónde encontrar predicciones erróneas de sucursales son indispensables.

• Si realmente necesita mejorar dicho código, buscaría en la programación de seguimiento y desenrollaría en bucle:

  • El desenrollado de bucle replica los cuerpos de bucle y le da a su optimizador más flujo de control para trabajar.

  • La programación de seguimiento identifica qué rutas son más probables y, entre otros, puede modificar las direcciones de las ramas para que el hardware de predicción de ramas funcione mejor en las rutas más comunes. Con los bucles desenrollados, hay más y más rutas, por lo que el programador de seguimiento tiene más para trabajar

• Estaría receloso de intentar codificar esto yo mismo en ensamblaje. Cuando salga el próximo chip con un nuevo hardware de predicción de bifurcaciones, es muy probable que todo su arduo trabajo se vaya por el desagüe. En su lugar, buscaría un compilador optimizador dirigido por comentarios .

Answer 3

En mi opinión, si está alcanzando este nivel de optimización, es probable que sea el momento de pasar al lenguaje ensamblador.

Esencialmente, usted cuenta con que el compilador genere un patrón específico de ensamblaje 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 verlo cada vez que se haga un pequeño cambio. ¿Por qué no hacerlo en ensamblador y terminar con él?

Answer 4

Es poco probable que este nivel de optimización haga una diferencia que valga la pena en todos los hotspots menos en los más calientes. Asumir que lo hace (sin demostrarlo en un caso específico) es una forma de adivinar , y la primera regla de optimización es no actuar sobre las adivinanzas .

Answer 5

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 para comparar 4 enteros (u 8 cortos, o 16 caracteres) a la vez.

Además, para calcular el mínimo que puede usar (vea estos trucos de magia ):

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

Sin embargo, presta atención a cosas como:

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

Incluso no hay saltos implícitos 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 conjetura es que en el primer fragmento de código usted contamina el caché más a menudo, mientras que en el segundo fragmento no lo hace.

Answer 6

La generalización del ejemplo que da es "reemplazar la evaluación condicional con matemáticas"; La evitación de la rama condicional se reduce en gran medida 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 están en cortocircuito. Lo mismo se aplica a || y | excepto que no necesita asegurarse de que los lados estén limitados a 0 o 1 (de nuevo, solo con fines lógicos, es decir, está utilizando el resultado solo Booleanamente).

Answer 7

La mayoría de los procesadores proporcionan una predicción de rama que es mejor que el 50%. De hecho, si obtiene una mejora del 1% en la predicción de sucursales, probablemente pueda publicar un artículo. Hay una montaña de documentos sobre este tema si está interesado.

Es mejor que te preocupes por los golpes y fallos de caché.

Answer 8

Se aplica una extensión de la técnica demostrada en la pregunta original cuando tiene que hacer varias pruebas anidadas para obtener una respuesta. Puede crear 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 aleatorios (por ejemplo, de datos arbitrarios), y esto está en un circuito cerrado, entonces los fallos de predicción de bifurcaciones pueden ralentizar esto. Se puede escribir 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];

Puedes generalizar esto a varios condicionales. Sin embargo, lo he visto hecho para 4. Si el anidamiento es tan profundo, sin embargo, usted quiere asegurarse de que la prueba de todos ellos sea realmente más rápida que la de 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 escarbar en el código de ensamblaje:

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