¿Por qué la instrucción de bucle es lenta? ¿No pudo Intel implementarlo de manera eficiente?

LOOP ( entrada manual Intel ref ) decrementa ecx / rcx, y luego salta si no es cero . Es lento, pero ¿no podría Intel haberlo hecho rápidamente? dec/jnz ya se fusiona macro en un solo uop en Sandybridge-family; la única diferencia es que eso establece banderas.

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

  • K8 / K10: 7 m-ops
  • Bulldozer-family / Ryzen : 1 m-op (mismo costo que macro-fused test-and-branch, 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 ). Throughput = 4c ( loop ) o 7c ( loope/ne ).
  • Familia SnB : 7 uops. (11 para loope / loopne ). Rendimiento = uno por 5 ciclos , ¡tanto de un cuello de botella como mantener el contador de bucle en la memoria! jecxz es solo 2 uops con el mismo rendimiento que jcc regular
  • Silvermont: 7 uops
  • AMD Jaguar (baja potencia): 8 uops, 5c de rendimiento
  • Via Nano3000: 2 uops

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

O mejor, ¿solo decodifícalo como una twig fusionada que no establece banderas? dec ecx / jnz en SnB decodifica a un único uop (que establece flags).

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 la familia UB de uarch tener loop rápido? Si es así, ¿por qué no? Si no, ¿por qué es difícil? Muchos transistores decodificadores? ¿O bits adicionales en una fusión fusionada y una twig uop 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 hace que un loop rápido sea fácil / lo valga? ¿O AMD desperdició un montón de transistores en hacer loop rápido? Si es así, presumiblemente alguien pensó que era una buena idea.


Si el loop fue rápido , sería perfecto para los bucles adc precisión arbitraria de BigInteger, para evitar paradas / ralentizaciones de bandera parcial (ver mis comentarios en mi respuesta), o cualquier otro caso en el que desee hacer un bucle sin tocar indicadores. 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 sería bueno para bucles ADCX / ADOX (para preservar OF).

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


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

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

Esta no es una respuesta buena o completa.

Puede ser lo mejor que obtengamos, y tendrá que ser suficiente a menos que alguien pueda arrojar más luz sobre él. 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 máquinas más antiguas (alrededor de 486) cuando comenzó a ocurrir una importante canalización, y la ejecución de las instrucciones más sencillas a través de la canalización de manera eficiente era tecnológicamente poco práctica. Entonces LOOP fue lento durante varias generaciones. Entonces nadie lo usó. Entonces, cuando fue posible acelerarlo, no había ningún incentivo real para hacerlo, ya que nadie realmente lo estaba usando.


Anton Ertl :

IIRC LOOP se usó en algunos softwares para sincronizar bucles; había un software (importante) que no funcionaba en las CPU donde LOOP era demasiado rápido (esto fue a principios de los 90). Entonces, los fabricantes de CPU aprendieron a hacer que LOOP sea lento.


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

@Paul A. Clayton (ocasional creador de SO y arquitecto de la CPU) adivinó cómo podrías usar tantos uops . (Esto se ve como loope/ne que verifica tanto el contador como ZF):

Podría imaginar 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 SnB 11 para LOOPE / LOOPNE, y es una suposición total ni siquiera tratando de tener en cuenta cualquier cosa conocida de los contadores de rendimiento SnB).

Entonces Pablo dijo:

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

resumen: los diseñadores querían que el loop fuera soportado solo a través de microcódigo, sin ajustes de ningún tipo al hardware propiamente dicho.

Si se entrega una instrucción inútil y de solo compatibilidad a los desarrolladores de microcódigos, es posible que razonablemente no puedan o no quieran sugerir cambios menores a la microarchitecture interna para mejorar dicha instrucción. No solo preferirían usar su “capital de sugerencias de cambio” de forma más productiva, sino que la sugerencia de un cambio por un caso inútil reduciría la credibilidad de otras sugerencias.

(Mi opinión: Intel probablemente siga haciéndolo lentamente a propósito, y no se haya tomado la molestia de reescribir su microcódigo durante mucho tiempo. Las CPU modernas son probablemente demasiado rápidas para que cualquier cosa pueda usarse de forma ingenua para funcionar correctamente).

… Paul continúa:

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

Si la optimización de LOOP caía fuera de otras optimizaciones (como la fusión de comparación y bifurcación), podría ser más fácil ajustar LOOP en una instrucción de ruta rápida que manejarla 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 generalmente disponible e interpretar dicha información estaría más allá del nivel de habilidad de la mayoría de las personas. (No soy diseñador de hardware, nunca había jugado en televisión ni me había alojado en un Holiday Inn Express. 🙂


El hilo se fue fuera de tema en el reino de AMD soplando nuestra única oportunidad de limpiar el cruft en la encoding de instrucciones x86. Es difícil culparlos, ya que cada cambio es un caso donde los decodificadores no pueden compartir transistores. Y antes de que Intel adoptara x86-64, ni siquiera estaba claro si se pondría de moda. AMD no quería cargar sus CPU con hardware que nadie usó si AMD64 no funcionaba.

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

bts instrucciones de bts son muy útiles para cosas de campo de bits, y son más lentas de lo que deben ser, así que casi siempre quieres cargarlas en un registro y luego usarlas. (Por lo general, es más rápido cambiar / enmascarar para obtener una dirección, en lugar de usar 10 uop bts [mem], reg en Skylake, pero sí requiere instrucciones adicionales, así que tiene sentido en 386, pero no en K8). La manipulación atómica de bits tiene que usar el formulario 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á funcionando.

Por favor vea el buen artículo de Abrash, Michael, publicado en el Dobb’s Journal en 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 usan architectures de memoria y tiempos de ejecución de instrucciones significativamente diferentes. El código no se puede optimizar para la familia 80×86; más bien, el código debe diseñarse para producir un buen rendimiento en un rango de sistemas u optimizado para combinaciones particulares de procesadores y memoria. Los progtwigdores deben evitar las inusuales instrucciones admitidas por el 8088, que han perdido su ventaja de rendimiento en chips posteriores. Las instrucciones de cadena deberían usarse pero no 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 alinearse para mejorar el rendimiento. Generalmente, la optimización de un 80486 requiere exactamente los pasos opuestos como la optimización de un 8088.

Por “instrucciones inusuales respaldadas por el 8088”, el autor también significa “bucle”:

Cualquier progtwigdor 8088 reemplazará instintivamente: DEC CX JNZ LOOPTOP con: LOOPTOP DE BUCLE 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 oscila aún más en el 486, donde LOOP es aproximadamente el doble de lento que DEC / JNZ, y, claro, estamos hablando de lo que originalmente era la optimización más obvia en todo el conjunto de instrucciones 80×86.

Este es un artículo muy bueno, y lo recomiendo encarecidamente. A pesar de que fue publicado en 1991, sorprendentemente es muy relevante hoy.

Pero este artículo simplemente 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, ejecutaron las instrucciones una a una, secuencialmente.

Los procesadores posteriores han comenzado 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 microoperaciones o μops, y luego todas las microoperaciones de diferentes instrucciones se colocaron en un gran conjunto de microoperaciones donde debían ejecutarse simultáneamente siempre que no dependieran unas de otras. Este principio de oleoducto OOO todavía se utiliza, casi sin cambios, en los procesadores modernos. Puede encontrar más información sobre la canalización de instrucciones en este shiny artículo: https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

Para simplificar el diseño de los chips, Intel decidió construir procesadores de tal manera que una de las instrucciones se transformara en microoperaciones de una manera muy eficiente, mientras que otras no.

La conversión eficiente de instrucciones a microoperaciones requiere más transistores, por lo que Intel ha decidido ahorrar en transistores a un costo de deencoding y ejecución más lenta de algunas instrucciones “complejas” o “raramente usadas”.

Por ejemplo, el “Manual de referencia de optimización de architecture Intel®” http://download.intel.com/design/PentiumII/manuals/24512701.pdf menciona lo siguiente: “Evite el uso de instrucciones complejas (por ejemplo, enter, leave, o loop ) que generalmente tienen más de cuatro μops y requieren múltiples ciclos para decodificar. Use secuencias de instrucciones simples en su lugar “.

Entonces, Intel de alguna manera ha decidido que la instrucción de “bucle” es “compleja” y, desde entonces, se volvió muy lenta. Sin embargo, no existe una referencia oficial de Intel sobre el desglose de la instrucción: cuántas microoperaciones produce cada instrucción y cuántos ciclos se requieren para decodificarla.

También puede leer sobre El motor de ejecución fuera de servicio en el “Manual de referencia de optimización de architectures Intel® 64 e IA-32” http://www.intel.com/content/dam/www/public/us/en/ documentos / manuales / 64-ia-32-architectures-optimization-manual.pdf sección 2.1.2.