performance - ¿Qué configuración hace REP?

assembly optimization

Question

Citando el manual de referencia de optimización de arquitecturas Intel® 64 e IA-32 , §2.4.6 "Mejora de cadenas REP":

Las características de rendimiento del uso de la cadena REP se pueden atribuir a dos componentes: sobrecarga de inicio y rendimiento de transferencia de datos.

[...]

Para la cadena REP de transferencia de datos de granularidad más grande, a medida que aumenta el valor de ECX, la sobrecarga de inicio de la cadena REP muestra un aumento gradual :

• Cadena corta (ECX <= 12): la latencia de REP MOVSW / MOVSD / MOVSQ es de aproximadamente 20 ciclos ,

• Cadena rápida (ECX> = 76: excluyendo REP MOVSB): la implementación del procesador proporciona optimización de hardware al mover tantos datos en 16 bytes como sea posible. La latencia de la latencia de cadena REP variará si uno de los 16 bytes de transferencia de datos se extiende a través del límite de la línea de caché:

  • Sin división: la latencia consiste en un costo inicial de aproximadamente 40 ciclos y cada 64 bytes de datos agrega 4 ciclos,
  • Divisiones de caché: la latencia consiste en un costo de inicio de aproximadamente 35 ciclos y cada 64 bytes de datos agrega 6 ciclos.

• Longitudes de cadena intermedias: la latencia de REP MOVSW / MOVSD / MOVSQ tiene un costo inicial de aproximadamente 15 ciclos más un ciclo por cada iteración del movimiento de datos en word / dword / qword.

(énfasis mío)

No hay más mención de dicho costo de inicio. ¿Qué es? ¿Qué hace y por qué lleva siempre más tiempo?

Answer 1

El microcódigo rep movs tiene varias estrategias para elegir. Si src y dest no se superponen estrechamente, el bucle microcodificado puede transferirse en fragmentos de 64b más grandes. (Esta es la característica llamada "cadenas rápidas" introducida con P6 y ocasionalmente reajustada para CPU posteriores que admitan cargas / almacenes más amplios). Pero si dest es solo un byte de src, rep movs debe producir exactamente el mismo resultado que obtendría de tantas instrucciones movs separadas.

Por lo tanto, el microcódigo debe verificar la superposición y probablemente la alineación (de src y dest por separado, o la alineación relativa). Probablemente también elija algo basado en valores de contador pequeños / medianos / grandes.

De acuerdo con los comentarios de Andy Glew sobre una respuesta a ¿Por qué son complicados memcpy / memset superiores? , las ramas condicionales en microcódigo no están sujetas a predicción de ramas . Entonces, hay una penalización significativa en los ciclos de inicio si la ruta predeterminada no tomada no es la que realmente se tomó, incluso para un ciclo que usa los mismos rep movs con la misma alineación y tamaño.

Supervisó la implementación inicial de la cadena de rep en P6, por lo que debería saberlo. :)

REP MOVS utiliza una función de protocolo de caché que no está disponible para el código normal. Básicamente, como las tiendas de transmisión SSE, pero de una manera que sea compatible con las reglas normales de ordenamiento de memoria, etc. // La "gran sobrecarga para elegir y configurar el método correcto" se debe principalmente a la falta de predicción de ramificaciones de microcódigo. Durante mucho tiempo deseé haber implementado REP MOVS utilizando una máquina de estado de hardware en lugar de un microcódigo, lo que podría haber eliminado por completo la sobrecarga.

Por cierto, he dicho durante mucho tiempo que una de las cosas que el hardware puede hacer mejor / más rápido que el software son las ramas complejas de múltiples vías.

Intel x86 ha tenido "secuencias rápidas" desde el Pentium Pro (P6) en 1996, que supervisé. Las cadenas rápidas P6 tomaron REP MOVSB ​​y más grandes, y las implementaron con cargas y almacenes de microcódigos de 64 bits y un protocolo de caché sin RFO. No violaron los pedidos de memoria, a diferencia de ERMSB en iVB.

La gran debilidad de hacer secuencias rápidas en el microcódigo fue (a) las predicciones erróneas de la rama del microcódigo, y (b) el microcódigo se desactivó con cada generación, volviéndose más y más lento hasta que alguien lo solucionó. Al igual que una copia de la biblioteca, los hombres se desafinan. Supongo que es posible que una de las oportunidades perdidas sea utilizar cargas y tiendas de 128 bits cuando estén disponibles, y así sucesivamente.

En retrospectiva, debería haber escrito una infraestructura de autoajuste, para obtener un microcódigo razonablemente bueno en cada generación. Pero eso no habría ayudado a utilizar nuevas, más amplias, cargas y tiendas, cuando estuvieron disponibles. // El kernel de Linux parece tener una infraestructura de autoajuste, que se ejecuta en el arranque. // Sin embargo, en general, defiendo las máquinas de estado de hardware que pueden realizar una transición sin problemas entre los modos, sin incurrir en predicciones erróneas de las ramas. // Es discutible si una buena predicción de ramificación de microcódigo evitaría esto.

En base a esto, mi mejor conjetura en una respuesta específica es: la ruta rápida a través del microcódigo (tantas ramas como sea posible realmente toman la ruta predeterminada no tomada) es el caso de inicio de 15 ciclos, para longitudes intermedias.

Dado que Intel no publica todos los detalles, las medidas de recuadro negro de recuentos de ciclos para varios tamaños y alineaciones son lo mejor que podemos hacer. Afortunadamente, eso es todo lo que necesitamos para tomar buenas decisiones. El manual de Intel y http://agner.org/optimize/ tienen buena información sobre cómo usar rep movs .

Dato curioso: sin ERMSB (IvB y posterior): rep movsb está optimizado para copias pequeñas. Se tarda más en iniciar que rep movsd o rep movsq para rep movsq grandes (más de un par de bytes, creo), e incluso después de eso puede no alcanzar el mismo rendimiento.

La secuencia óptima para copias grandes alineadas sin ERMSB y sin SSE / AVX (por ejemplo, en el código del núcleo) puede ser rep movsq y luego limpiar con algo como un mov no alineado que copia los últimos 8 bytes del búfer, posiblemente solapándose con el último parte alineada de lo que hizo el rep movsq . (básicamente use la estrategia de memcpy copia pequeña de memcpy ). Pero si el tamaño puede ser menor a 8 bytes, debe ramificarse a menos que sea seguro copiar más bytes de los necesarios. O rep movsb es una opción de limpieza si el tamaño de código pequeño es más importante que el rendimiento. (el rep copiará 0 bytes si RCX = 0).

Un bucle vectorial SIMD a menudo es al menos un poco más rápido que rep movsb incluso en CPU con Enhanced Rep Move / Stos B. Especialmente si no se garantiza la alineación. ( REP MOVSB ​​mejorado para memcpy , y consulte también el manual de optimización de Intel. Enlaces en la wiki de etiquetas x86 )

Answer 2

La cita que ha dado solo se aplica a la microarquitectura Nehalem (procesadores Intel Core i5, i7 y Xeon lanzados en 2009 y 2010), e Intel es explícito al respecto.

Antes de Nehalem, REP MOVSB ​​era aún más lento. Intel no dice nada sobre lo que sucedió en las microarquitecturas posteriores, pero, luego, con la microarquitectura Ivy Bridge (procesadores lanzados en 2012 y 2013) Intel ha introducido MOVSB ​​REP mejorado (aún tenemos que verificar el bit CPUID correspondiente) que nos permitió copiar memoria rápida

Las versiones más baratas de procesadores posteriores: Kaby Lake "Celeron" y "Pentium", lanzadas en 2017, no tienen AVX que podría haber sido usado para una copia rápida de la memoria, pero todavía tienen el MOVSB ​​REP mejorado. Es por eso que REP MOVSB ​​es muy beneficioso para los procesadores lanzados desde 2013.

Sorprendentemente, los procesadores Nehalem tuvieron una implementación REP MOVSD / MOVSQ bastante rápida (pero no REP MOVSW / MOVSB) para bloques de gran tamaño: solo 4 ciclos para copiar cada 64 bytes de datos posteriores (si los datos están alineados con los límites de la línea de caché) después Pagamos costos de inicio de 40 ciclos, lo cual es excelente cuando copiamos 256 bytes y más, ¡y no necesita usar registros XMM!

Por lo tanto, en la microarquitectura Nehalem, REP MOVSB ​​/ MOVSW es ​​casi inútil, pero REP MOVSD / MOVSQ es excelente cuando necesitamos copiar más de 256 bytes de datos y los datos están alineados con los límites de la línea de caché.

En microarquitecturas Intel anteriores (antes de 2008), los costos de inicio son aún más altos.

Estas son las pruebas de REP MOVS * cuando el origen y el destino estaban en la caché L1, de bloques lo suficientemente grandes como para no verse seriamente afectados por los costos de inicio, pero no tan grandes como para exceder el tamaño de la caché L1. Fuente: http://users.atw.hu/instlatx64/

Yonah (2006-2008)

    REP MOVSB 10.91 B/c
    REP MOVSW 10.85 B/c
    REP MOVSD 11.05 B/c

Nehalem (2009-2010)

    REP MOVSB 25.32 B/c
    REP MOVSW 19.72 B/c
    REP MOVSD 27.56 B/c
    REP MOVSQ 27.54 B/c

Westmere (2010-2011)

    REP MOVSB 21.14 B/c
    REP MOVSW 19.11 B/c
    REP MOVSD 24.27 B/c

Ivy Bridge (2012-2013) - con MOVSB ​​REP mejorado

    REP MOVSB 28.72 B/c
    REP MOVSW 19.40 B/c
    REP MOVSD 27.96 B/c
    REP MOVSQ 27.89 B/c

SkyLake (2015-2016) - con MOVSB ​​REP mejorado

    REP MOVSB 57.59 B/c
    REP MOVSW 58.20 B/c
    REP MOVSD 58.10 B/c
    REP MOVSQ 57.59 B/c

Kaby Lake (2016-2017) - con MOVSB ​​REP mejorado

    REP MOVSB 58.00 B/c
    REP MOVSW 57.69 B/c
    REP MOVSD 58.00 B/c
    REP MOVSQ 57.89 B/c

Como puede ver, la implementación de REP MOVS difiere significativamente de una microarquitectura a otra.

Según Intel, en Nehalem, los costos de inicio de REP MOVSB ​​para cadenas de más de 9 bytes son de 50 ciclos, pero para REP MOVSW / MOVSD / MOVSQ son de 35 a 40 ciclos, por lo que REP MOVSB ​​tiene mayores costos de inicio; Las pruebas han demostrado que el rendimiento general es peor para REP MOVSW, no REP MOVSB ​​en Nehalem y Westmere.

En Ivy Bridge, SkyLake y Kaby Lake, los resultados son lo contrario de estas instrucciones: REP MOVSB ​​es más rápido que REP MOVSW / MOVSD / MOVSQ, aunque solo un poco. En Ivy Bridge, REP MOVSW sigue siendo un rezagado, pero en SkyLake y Kaby Lake REP MOVSW no es peor que REP MOVSD / MOVSQ.

Tenga en cuenta que he presentado los resultados de las pruebas para SkyLake y Kaby Lake, tomadas del http://users.atw.hu/instlatx64/ solo para confirmarlo: estas arquitecturas tienen los mismos datos de ciclo por instrucción.

Conclusión: puede usar MOVSD / MOVSQ para bloques de memoria muy grandes, ya que produce resultados suficientes en todas las microarquitecturas Intel desde Yohan hasta Kaby Lake. Aunque, en arquitecturas de Yonan y anteriores, la copia SSE puede producir mejores resultados que REP MOVSD, pero, en aras de la universalidad, se prefiere REP MOVSD. Además de eso, REP MOVS * puede usar internamente diferentes algoritmos para trabajar con caché, que no está disponible para instrucciones normales.

En cuanto a REP MOVSB ​​para cadenas muy pequeñas (menos de 9 bytes o menos de 4 bytes), ni siquiera lo hubiera recomendado. En el lago Kaby, un solo MOVSB incluso sin REP es de 4 ciclos, en Yohan es de 5 ciclos. Dependiendo del contexto, puede hacerlo mejor solo con MOV normales.

Los costos de inicio no aumentan con el aumento de tamaño, como ha escrito. Es la latencia de la instrucción general para completar la secuencia completa de bytes que se incrementa, lo cual es bastante obvio, más bytes necesita copiar, más ciclos que toma, es decir, la latencia general, no solo el costo de inicio. Intel no reveló el costo de inicio para cadenas pequeñas, solo especificó para cadenas de 76 bytes y más, para Nehalem. Por ejemplo, tome estos datos sobre el Nehalem:

• La latencia para MOVSB ​​es de 9 ciclos si ECX <4. Por lo tanto, significa que se necesitan exactamente 9 ciclos para copiar cualquier cadena tan pronto como esta cadena tenga 1 byte o 2 bytes o 3 bytes. Esto no es tan malo, por ejemplo, si necesita copiar una cola y no desea usar tiendas superpuestas. Solo 9 ciclos para determinar el tamaño (entre 1 y 3) y copiar los datos, es difícil lograr esto con instrucciones normales y toda esta ramificación, y para una copia de 3 bytes, si no copió datos anteriores, tendrá que usar 2 cargas y 2 tiendas (palabra + byte), y dado que tenemos como máximo una unidad de tienda, no lo haremos mucho más rápido con las instrucciones MOV normales.
• Intel no menciona qué latencia tiene REP MOVSB ​​si ECX está entre 4 y 9
• Cadena corta (ECX <= 12): la latencia de REP MOVSW / MOVSD / MOVSQ es de aproximadamente 20 ciclos para copiar la cadena completa, no solo el costo de inicio de 20 ciclos. Por lo tanto, se necesitan alrededor de 20 ciclos para copiar la cadena completa de <= 12 bytes, por lo tanto, tenemos una tasa de salida por byte más alta que con REP MOVSB ​​con ECX <4.
• ECX> = 76 con REP MOVSD / MOVSQ: sí, aquí tenemos un costo de inicio de 40 ciclos, pero esto es más que razonable, ya que luego usamos copiar cada 64 bytes de datos en solo 4 ciclos. No soy un ingeniero de Intel autorizado para responder POR QUÉ hay un costo de inicio, pero supongo que se debe a que para estas cadenas, REP MOVS * utiliza (de acuerdo con los comentarios de Andy Glew en una respuesta a Por qué son complicados memcpy / memset superiores ? de la respuesta de Peter Cordes) una función de protocolo de caché que no está disponible para el código normal. Y viene una explicación en esta cita: "La gran sobrecarga para elegir y configurar el método correcto se debe principalmente a la falta de predicción de ramificaciones de microcódigo". También ha habido una nota interesante de que Pentium Pro (P6) implementó en 1996 REP MOVS * con cargas y almacenes de microcódigos de 64 bits y un protocolo de caché sin RFO: no violaron los pedidos de memoria, a diferencia de ERMSB en Ivy Bridge.

Answer 3

Solo por la descripción me parece que hay un tamaño de transferencia óptimo de 16 bytes, por lo que si está transfiriendo 79 bytes es 4 * 16 + 15. por lo tanto, no saber más sobre la alineación podría significar que hay un costo para el 15 bytes, ya sea al frente o al final (o divididos) y las transferencias de 4 16 bytes son más rápidas que las fracciones de 16. Algo así como una marcha alta en su automóvil frente a cambiar a través de las velocidades a alta velocidad.

Mire una memoria optimizada en glibc o gcc u otros lugares. Transfieren hasta unos pocos bytes individuales, luego pueden hacer transferencias de 16 bits hasta que alcancen un tamaño alineado óptimo de una dirección de 32 bits, 64 bits, 128 bits, y luego pueden hacer transferencias de varias palabras para gran parte de la copia, luego se reducen, tal vez una cosa de 32 bits, tal vez un 16 tal vez 1 byte para cubrir la falta de alineación en el back-end.

Parece que el representante hace el mismo tipo de cosas, transferencias individuales ineficientes para llegar a un tamaño de alineación optimizado, luego transferencias grandes hasta cerca y luego finalizar, y quizás algunas transferencias individuales pequeñas para cubrir la última fracción.