¿Por qué un movimiento condicional no es vulnerable para la falla de predicción de twig?

Después de leer esta publicación (respuesta en StackOverflow) (en la sección de optimización), me preguntaba por qué los movimientos condicionales no son vulnerables para la falla de predicción de twig. Encontré en un artículo sobre movimientos de cond aquí (PDF de AMD) . También allí, reclaman la ventaja de rendimiento de cond. movimientos. Pero, ¿por qué es esto? Yo no lo veo En el momento en que se evalúa esa instrucción ASM, aún no se conoce el resultado de la instrucción CMP anterior.

Gracias.

Ramas mal predichas son costosas

Un procesador moderno generalmente ejecuta entre una y tres instrucciones en cada ciclo si las cosas van bien (si no se detiene esperando las dependencias de datos para que estas instrucciones lleguen de instrucciones previas o de la memoria).

La afirmación anterior es sorprendentemente buena para bucles ajustados, pero esto no debería cegarle a una dependencia adicional que puede evitar que se ejecute una instrucción cuando llega su ciclo: para que se ejecute una instrucción, el procesador debe haber comenzado a captar y decodificar es 15-20 ciclos antes.

¿Qué debe hacer el procesador cuando se encuentra con una sucursal? La obtención y la deencoding de ambos objectives no se escala (si siguen más twigs, se debería obtener un número exponencial de rutas en paralelo). Entonces, el procesador solo busca y decodifica una de las dos twigs, especulativamente.

Esta es la razón por la cual las twigs mal predichas son costosas: cuestan de 15 a 20 ciclos que generalmente son invisibles debido a una tubería de instrucciones eficiente.

El movimiento condicional nunca es muy caro

El movimiento condicional no requiere predicción, por lo que nunca puede tener esta penalización. Tiene dependencias de datos, al igual que las instrucciones ordinarias. De hecho, un movimiento condicional tiene más dependencias de datos que las instrucciones ordinarias, porque las dependencias de datos incluyen los casos de “condición verdadera” y “condición falsa”. Después de una instrucción que mueve condicionalmente r1 a r2 , el contenido de r2 parece depender tanto del valor anterior de r2 como de r1 . Una bifurcación condicional bien predicha permite que el procesador infiera dependencias más precisas. Pero las dependencias de datos suelen tardar uno o dos ciclos en llegar, si es que necesitan tiempo para llegar.

Tenga en cuenta que un movimiento condicional de la memoria al registro a veces sería una apuesta peligrosa: si la condición es tal que el valor leído de la memoria no está asignado al registro, ha esperado en la memoria por nada. Pero las instrucciones de movimiento condicional que se ofrecen en los conjuntos de instrucciones suelen registrarse para registrarse, lo que evita este error por parte del progtwigdor.

Se trata de la tubería de instrucciones . Recuerde, las CPU modernas ejecutan sus instrucciones en una tubería, lo que produce un aumento significativo en el rendimiento cuando el flujo de ejecución es predecible por la CPU.

cmov

  add eax, ebx cmp eax, 0x10 cmovne ebx, ecx add eax, ecx 

En el momento en que se evalúa esa instrucción ASM, aún no se conoce el resultado de la instrucción CMP anterior.

Quizás, pero la CPU todavía sabe que las instrucciones que siguen al cmov se ejecutarán inmediatamente después, independientemente del resultado de las instrucciones cmp y cmov . Por lo tanto, la siguiente instrucción puede ser captada / decodificada con seguridad antes de tiempo, lo cual no es el caso con las twigs.

La siguiente instrucción podría incluso ejecutarse antes de que lo haga cmov (en mi ejemplo esto sería seguro)

twig

  add eax, ebx cmp eax, 0x10 je .skip mov ebx, ecx .skip: add eax, ecx 

En este caso, cuando el decodificador de la CPU vea je .skip , tendrá que elegir si continuar las instrucciones de je .skip / deencoding: 1) desde la siguiente instrucción o 2) desde el objective de salto. La CPU adivinará que esta twig condicional hacia adelante no sucederá, por lo que la siguiente instrucción mov ebx, ecx irá a la tubería.

Un par de ciclos más tarde, se ejecuta el je .skip y se toma la twig. ¡Oh mierda! Nuestra tubería ahora contiene algo de basura al azar que nunca debería ejecutarse. La CPU debe vaciar todas sus instrucciones en caché y comenzar de nuevo desde .skip:

Esa es la penalización de rendimiento de las twigs cmov , lo que nunca puede ocurrir con cmov ya que no altera el flujo de ejecución.

De hecho, es posible que aún no se conozca el resultado, pero si otras circunstancias lo permiten (en particular, la cadena de dependencia) la CPU puede reordenar y ejecutar instrucciones siguiendo el cmov . Como no hay ramificación involucrada, esas instrucciones deben evaluarse en cualquier caso.

Considera este ejemplo:

 cmoveq edx, eax add ecx, ebx mov eax, [ecx] 

Las dos instrucciones que siguen al cmov no dependen del resultado del cmov , por lo que se pueden ejecutar incluso cuando el cmov sí está pendiente (esto se denomina ejecución fuera de servicio ). Incluso si no se pueden ejecutar, aún se pueden buscar y decodificar.

Una versión de bifurcación podría ser:

  jne skip mov edx, eax skip: add ecx, ebx mov eax, [ecx] 

El problema aquí es que el flujo de control está cambiando y la CPU no es lo suficientemente inteligente como para ver que podría simplemente “insertar” la instrucción mov omitida si la derivación se tomó erróneamente como errónea, sino que descarta todo lo que hizo después de la sucursal y reinicia desde cero. De aquí viene la penalización.

Deberías leer esto. Con Fog + Intel, solo busque CMOV.

La crítica de Linus Torvald de CMOV alrededor de 2007
Comparación de Agner Fog de microarchitectures
Manual de referencia de optimización de architectures Intel® 64 e IA-32

Respuesta corta, las predicciones correctas son ‘gratuitas’, mientras que las predicciones erróneas de las twigs condicionales pueden costar 14-20 ciclos en Haswell. Sin embargo, CMOV nunca es gratis. Aún así, creo que CMOV está mucho mejor ahora que cuando Ravalds despotricó. No hay uno solo correcto para todos los tiempos en todos los procesadores alguna vez responden.

Tengo esta ilustración de [Peter Puschner et al.] Diapositiva que explica cómo se transforma en código de ruta única y acelera la ejecución.

enter image description here