performance - Instrucción jmp lenta

assembly x86

Question

Como seguimiento a mi pregunta Las ventajas de usar registros / instrucciones de 32 bits en x86-64 , comencé a medir los costos de las instrucciones. Soy consciente de que esto se ha hecho varias veces (por ejemplo, Agner Fog ), pero lo hago por diversión y autoeducación.

Mi código de prueba es bastante simple (por simplicidad aquí como pseudocódigo, en realidad en ensamblador):

for(outer_loop=0; outer_loop<NO;outer_loop++){
    operation  #first
    operation  #second
    ...
    operation #NI-th
} 

Pero, sin embargo, se deben considerar algunas cosas.

1. Si la parte interna del bucle es grande ( NI>10^7 grande NI>10^7 ), todo el contenido del bucle no cabe en la caché de instrucciones y, por lo tanto, debe cargarse una y otra vez, lo que hace que la velocidad de la RAM defina el tiempo necesario para ejecución Por ejemplo, para piezas internas grandes, xorl %eax, %eax (2 bytes) es 33% más rápido que xorq %rax, %rax (3 bytes).
2. Si NI es pequeño y todo el bucle se ajusta fácilmente en la memoria caché de instrucciones, entonces xorl %eax, %eax y xorq %rax, %rax son igualmente rápidos y pueden ejecutarse 4 veces por ciclo de reloj.

Sin embargo, este modelo simple no retiene el agua para la jmp jmp. Para la jmp jmp, mi código de prueba tiene el siguiente aspecto:

for(outer_loop=0; outer_loop<NO;outer_loop++){
    jmp .L0
    .L0: jmp .L1
    L1: jmp L2
    ....
}

Y los resultados son:

1. Para tamaños de bucle "grandes" (ya para NI>10^4 ) jmp 4.2 ns / jmp -instruction (equivaldría a 42 bytes cargados desde RAM o aproximadamente 12 ciclos de reloj en mi máquina).
2. Para tamaños de bucle pequeños ( NI<10^3 ) jmp- 1 ns / jmp- instrucción (que es alrededor de 3 ciclos de reloj, lo que suena plausible - las tablas de Agner Fog muestran los costos de 2 ciclos de reloj).

La instrucción jmp LX utiliza la codificación de 2 bytes eb 00 .

Por lo tanto, mi pregunta: ¿Cuál podría ser la explicación del alto costo de la jmp jmp en los bucles "grandes"?

PD: Si desea probarlo en su máquina, puede descargar los scripts desde here , simplemente ejecute sh jmp_test.sh en src -folder.

Editar: Resultados experimentales que confirman la teoría del tamaño BTB de Peter.

La siguiente tabla muestra los ciclos por instrucción para diferentes valores de ǸI (en relación con NI = 1000):

|oprations/ NI        | 1000 |  2000|  3000|  4000|  5000| 10000|
|---------------------|------|------|------|------|------|------|
|jmp                  |  1.0 |  1.0 |  1.0 |  1.2 |  1.9 |   3.8|
|jmp+xor              |  1.0 |  1.2 |  1.3 |  1.6 |  2.8 |   5.3|
|jmp+cmp+je (jump)    |  1.0 |  1.5 |  4.0 |  4.4 |  5.5 |   5.5|
|jmp+cmp+je (no jump) |  1.0 |  1.2 |  1.3 |  1.5 |  3.8 |   7.6|

Se puede ver:

1. Para la instrucción jmp , un recurso (aún desconocido) se vuelve escaso y esto conduce a una degradación del rendimiento para ǸI mayor que 4000.
2. Este recurso no se comparte con instrucciones tales como xor : la degradación del rendimiento sigue siendo jmp para NI aproximadamente 4000, si jmp y xor se ejecutan uno tras otro.
3. Pero este recurso se comparte con je si se realiza el salto: para jmp + je uno tras otro, el recurso se vuelve escaso para NI aproximadamente 2000.
4. Sin embargo, si je no salta en absoluto, el recurso volverá a escasear para que NI sea ​​aproximadamente 4000 (cuarta línea).

Los artículos de ingeniería inversa de predicción de rama de Matt Godbolt establecen que la capacidad del búfer objetivo de rama es 4096 entradas. Esa es una evidencia muy sólida de que las fallas de BTB son la razón de la diferencia de rendimiento observada entre los bucles jmp pequeños y grandes.

Answer 1

TL: DR: mi conjetura actual se está quedando sin entradas BTB (búfer de destino de rama). Vea abajo.

Aunque sus jmp s no funcionan, la CPU no tiene transistores adicionales para detectar este caso especial. Se manejan como cualquier otro jmp , lo que significa tener que reiniciar la búsqueda de instrucciones desde una nueva ubicación, creando una burbuja en la tubería.

Para obtener más información sobre los saltos y su efecto en las CPU canalizadas, los riesgos de control en una tubería RISC clásica deberían ser una buena introducción de por qué las ramas son difíciles para las CPU canalizadas. Las guías de Agner Fog explican las implicaciones prácticas, pero creo que asumen parte de ese tipo de conocimiento de fondo.

Su CPU Intel Broadwell tiene un uop-cache , que almacena en caché las instrucciones decodificadas (separadas del 32kiB L1 I-cache).

El tamaño de la caché de uop es de 32 conjuntos de 8 formas, con 6 uops por línea, para un total de 1536 uops (si cada línea está llena de 6 uops; eficiencia perfecta). 1536 uops está entre tus 1000 y 10000 tamaños de prueba. Antes de su edición, predije que el límite de lento a rápido sería alrededor de 1536 instrucciones totales en su bucle. No se ralentiza en absoluto hasta más allá de las instrucciones de 1536, por lo que creo que podemos descartar los efectos uop-cache. Esta no es una pregunta tan simple como pensé. :)

Ejecutar desde el caché uop (tamaño de código pequeño) en lugar de los decodificadores de instrucciones x86 (bucles grandes) significa que hay menos etapas de canalización antes de la etapa que reconoce jmp instrucciones jmp . Por lo tanto, podríamos esperar que las burbujas de un flujo constante de saltos sean más pequeñas, aunque se pronostiquen correctamente.

Se supone que correr desde los decodificadores da una penalización de predicción errónea de rama más grande (como tal vez 20 ciclos en lugar de 15), pero estas no son ramas predichas erróneamente.

Aunque la CPU no necesita predecir si la rama se toma o no, aún puede usar recursos de predicción de rama para predecir que un bloque de código contiene una rama tomada antes de que se decodifique.

El almacenamiento en caché del hecho de que hay una rama en un determinado bloque de código, y su dirección de destino, permite que la interfaz comience a buscar código desde el destino de la rama antes de que la codificación jmp rel32 se decodifique realmente. Recuerde que decodificar instrucciones x86 de longitud variable es difícil: no sabe dónde comienza una instrucción hasta que se decodifica la anterior. Por lo tanto, no puede simplemente coincidir con el flujo de instrucciones en busca de saltos / llamadas incondicionales tan pronto como se recupere.

Mi teoría actual es que estás disminuyendo la velocidad cuando te quedas sin entradas de búfer de destino de rama.

Consulte también ¿Qué predicción de rama detecta el búfer de destino de rama? que tiene una buena respuesta y discusión en este hilo de Realworldtech .

Un punto muy importante: el BTB predice en términos de qué bloque buscar a continuación, en lugar del destino exacto de una rama específica dentro de un bloque de recuperación. Entonces, en lugar de tener que predecir objetivos para todas las ramas en un bloque de búsqueda, la CPU solo necesita predecir la dirección de la próxima búsqueda.

Sí, el ancho de banda de la memoria puede ser un cuello de botella cuando se ejecutan cosas de muy alto rendimiento como xor-zeroing, pero está llegando a un cuello de botella diferente con jmp . La CPU tendría tiempo para recuperar 42B de la memoria, pero eso no es lo que está haciendo. La captación previa puede mantenerse fácilmente al día con 2 bytes por cada 3 relojes, por lo que debería haber fallos de L1 I-cache cercanos a cero.

En su xor con / sin prueba REX, el ancho de banda de la memoria principal podría haber sido el cuello de botella allí si probó con un bucle lo suficientemente grande como para no caber en el caché L3. Consumo 4 * 2B por ciclo en una CPU de ~ 3GHz, lo que hace un máximo de 25GB / s de DDR3-1600MHz. Sin embargo, incluso el caché L3 sería lo suficientemente rápido como para mantenerse al día con 4 * 3B por ciclo.

Es interesante que la memoria principal BW sea el cuello de botella; Inicialmente supuse que la decodificación (en bloques de 16 bytes) sería el cuello de botella para los XOR de 3 bytes, pero supongo que son lo suficientemente pequeños.

También tenga en cuenta que es mucho más normal medir tiempos en ciclos de reloj de núcleo. Sin embargo, supongo que sus mediciones en ns son útiles cuando está mirando la memoria, porque las velocidades de reloj bajas para ahorrar energía cambian la relación de la velocidad del reloj central a la velocidad de la memoria. (es decir, los cuellos de botella en la memoria son un problema menor a la velocidad mínima del reloj de la CPU).

Para la evaluación comparativa en ciclos de reloj, use perf stat ./a.out . Hay otros contadores de rendimiento útiles que son esenciales para tratar de comprender las características de rendimiento.

Consulte x86-64 Rendimiento relativo de jmp para obtener resultados del contador de rendimiento de Core2 (8 ciclos por jmp) y algunas microarquitecturas desconocidas donde es ~ 10c por jmp.

Los detalles de las características modernas de rendimiento de la CPU son lo suficientemente difíciles de entender incluso en condiciones de caja blanca más o menos (leyendo el manual de optimización de Intel y lo que han publicado sobre los componentes internos de la CPU). Te quedarás atrapado temprano y, a menudo, si insistes en las pruebas de recuadro negro en las que no lees cosas como artículos de arstechnica sobre el nuevo diseño de la CPU, o tal vez algunas cosas más detalladas como la descripción general de la microarquitectura Haswell de David Kanter, o similar Sandybridge relato que he vinculado anteriormente.

Si quedarse atascado temprano y con frecuencia está bien y te estás divirtiendo, entonces sigue haciendo lo que estás haciendo. Pero hace que sea más difícil para las personas responder sus preguntas si no conoce esos detalles, como en este caso. : / p. ej., mi primera versión de esta respuesta suponía que había leído lo suficiente como para saber cuál era el caché de UOP.