performance - ¿Por qué la instrucción de bucle es lenta? ¿No podría Intel haberlo implementado eficientemente?

assembly x86

Question

LOOP ( entrada manual de referencia de Intel ) disminuye ecx / rcx, y luego salta si no es cero . Es lento, pero ¿no podría Intel haberlo hecho barato a toda velocidad? dec/jnz ya se fusiona en una sola unidad en Sandybridge-family; La única diferencia es que establece banderas.

loop en varias microarquitecturas, de las tablas de instrucciones de Agner Fog :

• K8 / K10: 7 operaciones m

• Bulldozer-family / Ryzen : 1 m-op (el mismo costo que la prueba y ramificación con jecxz , o jecxz )

• P4: 4 uops (igual que jecxz )

• P6 (PII / PIII): 8 uops
• Pentium M, Core2: 11 uops
• Nehalem: 6 uops. (11 para loope / loopne ). Rendimiento = 4c ( loop ) o 7c ( loope/ne ).
• SnB-family : 7 uops. (11 para loope / loopne ). Rendimiento = uno por cada 5 ciclos , ¡tanto cuello de botella como mantener el contador de bucles en la memoria! jecxz es solo 2 uops con el mismo rendimiento que jcc regular
• Silvermont: 7 uops
• AMD Jaguar (baja potencia): 8 uops, rendimiento 5c
• Via Nano3000: 2 uops

¿No podrían los decodificadores decodificar lo mismo que lea rcx, [rcx-1] / jrcxz ? Eso sería 3 uops. Al menos ese sería el caso sin un prefijo de tamaño de dirección, de lo contrario, debe usar ecx y truncar RIP a EIP si se realiza el salto; ¿Tal vez la extraña elección del tamaño de la dirección que controla el ancho de la disminución explica los muchos uops?

O mejor, ¿solo decodificarlo como un dec-and-branch fusionado que no establece banderas? dec ecx / jnz en SnB decodifica en un solo uop (que establece banderas).

Sé que el código real no lo usa (porque ha sido lento desde al menos P5 o algo así), pero AMD decidió que valía la pena hacerlo rápido para Bulldozer. Probablemente porque fue fácil.

• ¿Sería fácil para Uuarch de la familia SnB tener un loop rápido? Si es así, ¿por qué no lo hacen? Si no, ¿por qué es difícil? ¿Muchos transistores decodificadores? ¿O bits adicionales en una unidad fusionada de dec & branch para registrar que no establece banderas? ¿Qué podrían estar haciendo esos 7 uops? Es una instrucción realmente simple.

• ¿Qué tiene de especial Bulldozer que hizo que un loop rápido fuera fácil / valió la pena? ¿O AMD desperdició un montón de transistores haciendo que el loop rápido? Si es así, presumiblemente alguien pensó que era una buena idea.

Si el loop fuera rápido , sería perfecto para los bucles adc precisión arbitraria BigInteger, para evitar paradas / ralentizaciones de adc parciales (vea mis comentarios en mi respuesta), o cualquier otro caso en el que desee hacer un bucle sin tocar banderas. También tiene una ventaja de tamaño de código menor sobre dec/jnz . (Y dec/jnz solo macro-fusibles en la familia SnB).

En las CPU modernas donde dec/jnz está bien en un bucle ADC, el loop aún sería bueno para los bucles ADCX / ADOX (para preservar OF).

Si el loop hubiera sido rápido, los compiladores ya lo estarían utilizando como una optimización de mirilla para el tamaño del código + velocidad en CPU sin macro fusión.

No evitaría que me molestaran todas las preguntas con un código incorrecto de 16 bits que utiliza el loop para cada bucle, incluso cuando también necesitan otro contador dentro del bucle. Pero al menos no sería tan malo.

Answer 1

Ahora que busqué en Google después de escribir mi pregunta, resulta ser un duplicado exacto de uno en comp.arch , que apareció de inmediato. Esperaba que fuera difícil de google (muchos éxitos "por qué mi bucle es lento"), pero mi primer intento ( why is the x86 loop instruction slow ) obtuvo resultados.

Esta no es una respuesta buena o completa.

Podría ser lo mejor que obtendremos, y tendrá que ser suficiente a menos que alguien pueda arrojar algo más de luz sobre ello. No me propuse escribir esto como una publicación de respuesta a mi propia pregunta.

Buenas publicaciones con diferentes teorías en ese hilo:

Robert

LOOP se volvió lento en algunas de las primeras máquinas (alrededor del 486) cuando comenzaron a ocurrir tuberías significativas, y ejecutar cualquier cosa menos la instrucción más simple en la tubería de manera eficiente no era tecnológicamente práctico. Entonces LOOP fue lento por varias generaciones. Entonces nadie lo usó. Entonces, cuando se hizo posible acelerarlo, no había un incentivo real para hacerlo, ya que en realidad nadie lo estaba usando.

Anton Ertl :

IIRC LOOP se utilizó en algunos programas para cronometrar bucles; había un software (importante) que no funcionaba en las CPU donde LOOP era demasiado rápido (esto fue a principios de los años 90 más o menos). Entonces, los fabricantes de CPU aprendieron a hacer LOOP lento.

(Paul y cualquier otra persona: puedes volver a publicar tu propia escritura como tu propia respuesta. La eliminaré de mi respuesta y votaré la tuya).

@Paul A. Clayton ( afiche ocasional de SO y tipo de arquitectura de CPU) groups.google.com/d/msg/comp.arch/5RN6EegUxE0/KETMqmKWVN4J . (Esto parece loope/ne que verifica tanto el contador como el ZF):

Me imagino una versión posiblemente sensata de 6 µop:

virtual_cc = cc; 
temp = test (cc); 
rCX = rCX - temp; // also setting cc 
cc = temp & cc; // assumes branch handling is not 
       // substantially changed for the sake of LOOP 
branch 
cc = virtual_cc 

(Tenga en cuenta que esto es 6 uops, no 11 de SnB para LOOPE / LOOPNE, y es una suposición total que ni siquiera trata de tener en cuenta nada conocido de los contadores de rendimiento de SnB).

Entonces Pablo dijo:

Estoy de acuerdo en que debería ser posible una secuencia más corta, pero estaba tratando de pensar en una secuencia hinchada que podría tener sentido si se permitieran ajustes microarquitecturales mínimos .

resumen: los diseñadores querían que el loop se admitiera solo a través de un microcódigo, sin ningún ajuste en el hardware adecuado.

Si se entrega una instrucción inútil, solo de compatibilidad a los desarrolladores de microcódigo, es posible que no puedan sugerir cambios menores en la microarquitectura interna para mejorar dicha instrucción. No solo preferirían utilizar su "capital de sugerencia de cambio" de manera más productiva, sino que la sugerencia de un cambio para un caso inútil reduciría la credibilidad de otras sugerencias.

(Mi opinión: Intel probablemente todavía lo está haciendo lento a propósito, y no se ha molestado en reescribir su microcódigo durante mucho tiempo. Las CPU modernas probablemente sean demasiado rápidas para que cualquier cosa que use el loop de una manera ingenua funcione correctamente).

... Paul continúa:

Los arquitectos detrás de Nano pueden haber descubierto que evitar la carcasa especial de LOOP simplificó su diseño en términos de área o potencia. O pueden haber tenido incentivos de usuarios integrados para proporcionar una implementación rápida (para beneficios de densidad de código). Esas son solo conjeturas SALVAJES .

Si la optimización de LOOP se cayó de otras optimizaciones (como la fusión de comparar y ramificar), podría ser más fácil ajustar LOOP en una instrucción de ruta rápida que manejarlo en microcódigo, incluso si el rendimiento de LOOP no era importante.

Sospecho que tales decisiones se basan en detalles específicos de la implementación. La información sobre tales detalles no parece estar disponible en general y su interpretación estaría más allá del nivel de habilidad de la mayoría de las personas. (No soy diseñador de hardware, y nunca he jugado uno en televisión ni me he alojado en un Holiday Inn Express. :-)

El hilo luego se desvió del tema en el ámbito de AMD, lo que sopló nuestra única oportunidad de limpiar el cruft en la codificación de instrucciones x86. Es difícil culparlos, ya que cada cambio es un caso en el que los decodificadores no pueden compartir transistores. Y antes de que Intel adoptara x86-64, ni siquiera estaba claro si iba a ponerse al día. AMD no quería cargar sus CPU con hardware que nadie usaría si AMD64 no se daba cuenta.

Pero aún así, hay muchas cosas pequeñas: setcc podría haber cambiado a 32 bits. (Por lo general, debe usar xor-zero / test / setcc para evitar falsas dependencias, o porque necesita un registro de extensión cero). Shift podría tener marcas escritas incondicionalmente, incluso con un conteo de desplazamiento cero (eliminando la dependencia de datos de entrada en eflags para el cambio de conteo variable para la ejecución de OOO). La última vez que escribí esta lista de manías, creo que había una tercera ... Oh, sí, bt / bts etc., con operandos de memoria, la dirección depende de los bits superiores del índice (cadena de bits, no solo bits dentro Una palabra de máquina).

bts instrucciones bts son muy útiles para cosas de campo de bits, y son más lentas de lo necesario, por lo que casi siempre desea cargar en un registro y luego usarlo. (Por lo general, es más rápido cambiar / enmascarar para obtener una dirección usted mismo, en lugar de usar 10 uop bts [mem], reg en Skylake, pero requiere instrucciones adicionales. Por lo tanto, tenía sentido en 386, pero no en K8). La manipulación atómica de bits tiene que usar la forma de memoria-dest, pero la versión lock necesita muchos uops de todos modos. Todavía es más lento que si no pudiera acceder fuera del dword en el que está operando.

Answer 2

Consulte el bonito artículo de Abrash, Michael, publicado en el Dr. Dobb''s Journal, marzo de 1991, v16 n3 p16 (8): http://archive.gamedev.net/archive/reference/articles/article369.html

El resumen del artículo es el siguiente:

La optimización del código para los microprocesadores 8088, 80286, 80386 y 80486 es difícil porque los chips utilizan arquitecturas de memoria y tiempos de ejecución de instrucciones significativamente diferentes. El código no se puede optimizar para la familia 80x86; más bien, el código debe estar diseñado para producir un buen rendimiento en una gama de sistemas u optimizado para combinaciones particulares de procesadores y memoria. Los programadores deben evitar las instrucciones inusuales respaldadas por el 8088, que han perdido su ventaja de rendimiento en chips posteriores. Las instrucciones de cadena deben usarse pero no deben confiarse en ellas. Los registros deben usarse en lugar de las operaciones de memoria. La ramificación también es lenta para los cuatro procesadores. Los accesos a la memoria deben estar alineados para mejorar el rendimiento. En general, la optimización de un 80486 requiere exactamente los pasos opuestos a la optimización de un 8088.

Por "instrucciones inusuales respaldadas por el 8088", el autor también quiere decir "bucle":

Cualquier programador 8088 reemplazaría instintivamente: DEC CX JNZ LOOPTOP con: LOOP LOOPTOP porque LOOP es significativamente más rápido en el 8088. LOOP también es más rápido en el 286. Sin embargo, en el 386, LOOP es en realidad dos ciclos más lento que DEC / JNZ. El péndulo se balancea aún más en el 486, donde LOOP es aproximadamente el doble de lento que DEC / JNZ, y, fíjate, estamos hablando de lo que originalmente era quizás la optimización más obvia en todo el conjunto de instrucciones de 80x86.

Este es un muy buen artículo, y lo recomiendo encarecidamente. Aunque se publicó en 1991, hoy sorprendentemente es muy relevante.

Pero este artículo solo da consejos, alienta a probar la velocidad de ejecución y elegir variantes más rápidas. No explica por qué algunos comandos se vuelven muy lentos, por lo que no responde completamente a su pregunta.

La respuesta es que los procesadores anteriores, como 80386 (lanzado en 1985) y antes, ejecutaban las instrucciones una por una, secuencialmente.

Los procesadores posteriores comenzaron a utilizar la canalización de instrucciones: inicialmente, simple, para 804086 y, finalmente, Pentium Pro (lanzado en 1995) introdujo una tubería interna radicalmente diferente, llamándola el núcleo Fuera de servicio (OOO) donde las instrucciones se transformaron en pequeños fragmentos de operaciones llamadas micro-ops o µops, y luego todas las micro-ops de diferentes instrucciones se colocaron en un gran grupo de micro-ops donde se suponía que se ejecutarían simultáneamente, siempre que no dependan el uno del otro. Este principio de tubería OOO todavía se usa, casi sin cambios, en los procesadores modernos. Puede encontrar más información sobre la canalización de instrucciones en este brillante artículo: https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

Para simplificar el diseño del chip, Intel decidió construir procesadores de tal manera que una de las instrucciones se transformara en micro-operaciones de una manera muy eficiente, mientras que otras no.

La conversión eficiente de instrucciones a micro-operaciones requiere más transistores, por lo que Intel ha decidido ahorrar en transistores a un costo de decodificación y ejecución más lenta de algunas instrucciones "complejas" o "raramente utilizadas".

Por ejemplo, el "Manual de referencia de optimización de arquitectura Intel®" http://download.intel.com/design/PentiumII/manuals/24512701.pdf menciona lo siguiente: "Evite el uso de instrucciones complejas (por ejemplo, ingresar, salir o bucle ) que generalmente tienen más de cuatro µops y requieren múltiples ciclos para decodificar. Utilice secuencias de instrucciones simples en su lugar ".

Entonces, Intel de alguna manera decidió que la instrucción "loop" es "compleja" y, desde entonces, se volvió muy lenta. Sin embargo, no hay una referencia oficial de Intel sobre el desglose de instrucciones: cuántas microoperaciones produce cada instrucción y cuántos ciclos son necesarios para decodificarla.

También puede leer sobre el motor de ejecución fuera de orden en el "Manual de referencia de optimización de arquitecturas Intel® 64 e IA-32" http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf sección 2.1.2.

Answer 3

En 1988, Glenn Henry , compañero de IBM, acababa de unirse a Dell, que tenía unos cientos de empleados en ese momento, y en su primer mes dio una charla técnica sobre 386 internos. Un grupo de programadores de BIOS nos habíamos preguntado por qué LOOP era más lento que DEC / JNZ, por lo que durante la sección de preguntas / respuestas alguien hizo la pregunta.

Su respuesta tenía sentido. Tenía que ver con la paginación.

LOOP consta de dos partes: disminuir CX, luego saltar si CX no es cero. La primera parte no puede causar una excepción de procesador, mientras que la parte de salto sí. Por un lado, podría saltar (o caer) a una dirección fuera de los límites del segmento, causando un SEGFAULT. Para dos, puede saltar a una página que se intercambia.

Un SEGFAULT generalmente significa el final de un proceso, pero los errores de página son diferentes. Cuando se produce un error de página, el procesador emite una excepción y el sistema operativo se encarga de cambiar la página del disco a la RAM. Después de eso, reinicia las instrucciones que causaron la falla.

Reiniciar significa restaurar el estado del proceso a lo que era justo antes de la instrucción ofensiva. En el caso de la instrucción LOOP en particular, significaba restaurar el valor del registro CX. Uno podría pensar que podría agregar 1 a CX, ya que sabemos que CX se redujo, pero aparentemente, no es tan simple. Por ejemplo, echa un vistazo a esta errata de Intel :

Las violaciones de protección involucradas generalmente indican un probable error de software y no se desea reiniciar si ocurre una de estas violaciones. En un sistema 80286 en modo protegido con estados de espera durante cualquier ciclo de bus, cuando el componente 80286 detecta ciertas violaciones de protección y el componente transfiere el control a la rutina de manejo de excepciones, el contenido del registro CX puede no ser confiable. (El hecho de que los contenidos de CX cambien es una función de la actividad del bus en el momento en que el microcódigo interno detecta la violación de la protección).

Para estar seguros, necesitaban guardar el valor de CX en cada iteración de una instrucción LOOP, para restaurarlo de manera confiable si fuera necesario.

Es esta carga extra de salvar CX lo que hizo que LOOP fuera tan lento.

Intel, como todos los demás en ese momento, estaba obteniendo cada vez más RISC. Las antiguas instrucciones CISC (LOOP, ENTER, LEAVE, BOUND) se estaban eliminando gradualmente. Todavía los usamos en ensambles codificados a mano, pero los compiladores los ignoraron por completo.