Pourquoi l’instruction de boucle est-elle lente? Intel ne pouvait-il pas le mettre en œuvre efficacement?

LOOP ( entrée manuelle de la référence Intel ) décrémente ecx / rcx, puis saute si elle est non nulle . C’est lent, mais Intel n’a-t-il pas pu faire vite? dec/jnz déjà macro-fusible en un seul uop sur la famille Sandybridge; la seule différence est que cela définit des drapeaux.

loop sur diverses microarchitectures, à partir des tables d’instructions d’ Agner Fog :

  • K8 / K10: 7 m-ops
  • Bulldozer-family / Ryzen : 1 m-op (même coût que le test et la twig fusionnés par macro, ou jecxz )

  • P4: 4 uops (idem jecxz )

  • P6 (PII / PIII): 8 uops
  • Pentium M, Core2: 11 uops
  • Nehalem: 6 uops. (11 pour loope / loopne ). Débit = 4c ( loop ) ou 7c ( loope/ne ).
  • Famille SnB : 7 uops. (11 pour loope / loopne ). Débit = un par cinq cycles , autant de goulot d’étranglement que de garder votre compteur de boucles en mémoire! jecxz n’est que 2 uops avec le même débit que jcc
  • Silvermont: 7 uops
  • AMD Jaguar (faible consommation): 8 uops, débit 5c
  • Via Nano3000: 2 uops

Les décodeurs ne pourraient-ils pas décoder le même que lea rcx, [rcx-1] / jrcxz ? Ce serait 3 uops. Au moins, ce serait le cas sans préfixe de taille d’adresse, sinon il faut utiliser ecx et tronquer RIP en EIP si le saut est effectué; peut-être le choix étrange de taille-adresse contrôlant la largeur du décrément explique-t-il les nombreux uops?

Ou mieux, décodez-le simplement comme une twig fusionnée qui ne met pas de drapeaux? dec ecx / jnz sur SnB décode en un seul uop (qui définit les indicateurs).

Je sais que le vrai code ne l’utilise pas (parce qu’il est lent depuis au moins P5 ou quelque chose du genre), mais AMD a décidé qu’il valait la peine de le faire rapidement pour Bulldozer. Probablement parce que c’était facile.


  • Serait-il facile pour la famille SnB-Uarch d’avoir une loop rapide? Si oui, pourquoi pas eux? Si non, pourquoi est-ce difficile? Beaucoup de transistors de décodeur? Ou des bits supplémentaires dans un fondu & twig fusionné pour enregistrer qu’il ne met pas de drapeaux? Que pourraient faire ces 7 uops? C’est une instruction vraiment simple.

  • Quelle est la particularité de Bulldozer qui a rendu une loop rapide facile / en vaut la peine? Ou AMD a-t-il gaspillé un tas de transistors en faisant une loop rapide? Si c’est le cas, il est probable que quelqu’un a pensé que c’était une bonne idée.


Si loop était rapide , ce serait parfait pour les boucles adc précision arbitraire BigInteger, pour éviter les blocages / ralentissements de fanions partiels (voir mes commentaires sur ma réponse), ou tout autre cas où vous souhaitez effectuer une boucle sans toucher de drapeaux. Il a également un avantage mineur sur la taille du code par rapport à dec/jnz . (Et dec/jnz seulement les macro-fusibles sur la famille SnB).

Sur les processeurs modernes où dec/jnz est correct dans une boucle ADC, la loop serait toujours agréable pour les boucles ADCX / ADOX (pour préserver OF).

Si la loop avait été rapide, les compilateurs l’utilisaient déjà comme une optimisation de judas pour la taille de code + la vitesse sur les processeurs sans macro-fusion.


Cela ne m’empêchera pas de me fâcher avec toutes les questions avec un mauvais code 16 bits utilisant une loop pour chaque boucle, même si elles ont également besoin d’un autre compteur dans la boucle. Mais au moins, ce ne serait pas aussi grave.

Maintenant que j’ai googlé après avoir écrit ma question, il s’agit d’une copie exacte de comp.arch , qui est apparue tout de suite. Je m’attendais à ce qu’il soit difficile de google (beaucoup de “pourquoi est-ce que ma boucle est lente” hits), mais mon premier essai ( why is the x86 loop instruction slow ) a eu des résultats.

Ce n’est pas une réponse correcte ou complète.

Ce serait peut-être le meilleur que nous obtiendrions, et nous devrons suffire à moins que quelqu’un puisse nous éclairer davantage. Je n’ai pas décidé d’écrire ceci comme un post de réponse à ma question.


Bons messages avec des théories différentes dans ce fil:

Robert

LOOP est devenu lent sur certaines des premières machines (environ 486) lorsque le pipeline a commencé à produire des quantités importantes, et l’exécution efficace des instructions les plus simples du pipeline était techniquement impossible. Donc, LOOP a été lente pour plusieurs générations. Donc, personne ne l’a utilisé. Donc, quand il était possible d’accélérer le processus, il n’y avait pas vraiment d’incitation à le faire, car personne ne l’utilisait réellement.


Anton Ertl :

IIRC LOOP a été utilisé dans certains logiciels pour les boucles de synchronisation; Il y avait un logiciel (important) qui ne fonctionnait pas sur les processeurs où LOOP était trop rapide (c’était au début des années 90 ou à peu près). Les fabricants de processeurs ont donc appris à ralentir LOOP.


(Paul et toute autre personne: vous êtes invités à republier votre propre écriture en tant que votre propre réponse. Je la retirerai de ma réponse et la voterez.)

@Paul A. Clayton (gars occasionnel de l’architecture SO et du CPU) a compris comment utiliser autant d’upops . (Cela ressemble à loope/ne qui vérifie à la fois le compteur et ZF):

Je pourrais imaginer une version de 6 µop probablement raisonnable:

 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 

(Notez que ceci est 6 uops, pas SnB 11 pour LOOPE / LOOPNE, et est une supposition totale n’essayant même pas de prendre en compte tout ce qui est connu des compteurs de perf SnB.)

Puis Paul a dit:

Je suis d’accord qu’une séquence plus courte devrait être possible, mais j’essayais de penser à une séquence gonflée qui pourrait avoir du sens si des ajustements micro-architecturaux minimaux étaient autorisés.

résumé: Les concepteurs ont souhaité que la loop soit supscope uniquement via un microcode, sans aucun ajustement du matériel proprement dit.

Si une instruction inutile, compatible uniquement avec la compatibilité, est transmise aux développeurs de microcodes, ils pourraient raisonnablement ne pas être capables ou disposés à suggérer des modifications mineures à la microarchitecture interne pour améliorer une telle instruction. Non seulement ils préféreraient utiliser leur “capital de suggestion de changement” de manière plus productive, mais la suggestion d’un changement pour un cas inutile réduirait la crédibilité des autres suggestions.

(Mon avis: Intel est probablement en train de le rendre lent à dessein, et n’a pas pris la peine de réécrire son microcode pour longtemps . Les processeurs modernes sont probablement trop rapides pour tout ce qui utilise la loop de manière naïve pour fonctionner correctement.)

… Paul continue:

Les architectes à l’origine de Nano ont peut-être trouvé que l’évitement du boîtier spécial de LOOP simplifiait leur conception en termes de surface ou de puissance. Ou bien, les utilisateurs incorporés peuvent les inciter à fournir une implémentation rapide (pour des avantages de densité de code). Ce ne sont que des suppositions WILD .

Si l’optimisation de LOOP est tombée des autres optimisations (comme la fusion de la comparaison et de la twig), il serait plus facile de modifier LOOP dans une instruction de chemin rapide que de la gérer dans un microcode même si les performances de LOOP étaient sans importance.

Je soupçonne que de telles décisions sont basées sur des détails spécifiques de la mise en œuvre. L’information sur ces détails ne semble pas être disponible et l’interprétation de ces informations dépasse le niveau de compétence de la plupart des gens. (Je ne suis pas un concepteur de matériel – et je n’ai jamais joué à la télévision ou logé dans un Holiday Inn Express. 🙂


Le fil est ensuite passé hors-sujet dans le domaine d’AMD, ce qui nous a donné l’occasion de nettoyer le codage des instructions x86. Il est difficile de leur en vouloir, car chaque changement est un cas où les décodeurs ne peuvent pas partager les transistors. Et avant qu’Intel n’adopte x86-64, il n’était même pas clair que cela allait faire son chemin. AMD ne voulait pas surcharger ses processeurs avec du matériel que personne n’utilisait si AMD64 n’était pas pris en charge.

Mais encore, il y a tellement de petites choses: setcc pourrait avoir 32bits. (Habituellement, vous devez utiliser xor-zero / test / setcc pour éviter les fausses dépendances ou parce que vous avez besoin d’un registre sans extension). Shift pourrait avoir écrit des drapeaux inconditionnellement, même avec un nombre de décalage nul (suppression de la dépendance des données d’entrée sur les eflags pour le décalage de compte variable pour une exécution OOO). La dernière fois que j’ai tapé cette liste de bêtes noires, je pense qu’il y en avait une troisième … Oh oui, bt / bts etc. avec des opérandes de mémoire a l’adresse dépendante des bits supérieurs de l’index (chaîne de bits, pas seulement bit un mot machine).

bts instructions bts sont très utiles pour les champs de bits, et elles sont plus lentes qu’elles ne le doivent, de sorte que vous voulez presque toujours charger dans un registre, puis l’utiliser. (Il est généralement plus rapide de décaler / masquer pour obtenir une adresse vous-même, au lieu d’utiliser 10 uop bts [mem], reg sur Skylake, mais cela nécessite des instructions supplémentaires. Donc, cela était logique sur 386, mais pas sur K8). La manipulation de bits atomique doit utiliser la forme de mémoire-dest, mais la version lock ed nécessite de nombreux uops. C’est encore plus lent que s’il ne pouvait pas accéder en dehors du dword il fonctionne.

S’il vous plaît voir le bel article par Aarmh, Michael, publié dans le Journal du Dr Dobb Mars 1991 v16 n3 p16 (8): http://archive.gamedev.net/archive/reference/articles/article369.html

Le résumé de l’article est le suivant:

L’optimisation du code pour les microprocesseurs 8088, 80286, 80386 et 80486 est difficile car les puces utilisent des architectures de mémoire et des temps d’exécution des instructions très différents. Le code ne peut pas être optimisé pour la famille 80×86; le code doit plutôt être conçu pour produire de bonnes performances sur une gamme de systèmes ou être optimisé pour des combinaisons particulières de processeurs et de mémoire. Les programmeurs doivent éviter les instructions inhabituelles sockets en charge par le 8088, qui ont perdu leur avantage en termes de performances dans les puces suivantes. Les instructions de chaîne doivent être utilisées mais ne doivent pas être utilisées. Les registres doivent être utilisés plutôt que les opérations de mémoire. Le twigment est également lent pour les quatre processeurs. Les access à la mémoire doivent être alignés pour améliorer les performances. En général, l’optimisation d’un 80486 nécessite exactement les étapes opposées, comme l’optimisation d’un 8088.

Par “instructions inhabituelles sockets en charge par le 8088”, l’auteur signifie également “boucle”:

N’importe quel programmeur 8088 remplacera instinctivement: DEC CX JNZ LOOPTOP par: LOOP LOOPTOP car LOOP est nettement plus rapide sur le 8088. LOOP est également plus rapide sur le 286. Sur le 386, cependant, LOOP est en réalité deux cycles plus lent que DEC / JNZ. Le pendule est encore plus bas sur le 486, où LOOP est environ deux fois plus lent que DEC / JNZ – et bien sûr, nous parlons de l’optimisation la plus évidente du jeu d’instructions 80×86.

C’est un très bon article et je le recommande vivement. Bien qu’il ait été publié en 1991, il est étonnamment très pertinent aujourd’hui.

Mais cet article ne fait que donner des conseils, il encourage à tester la vitesse d’exécution et à choisir des variantes plus rapides. Cela n’explique pas pourquoi certaines commandes deviennent très lentes, donc elles ne répondent pas complètement à votre question.

La réponse est que les processeurs antérieurs, comme 80386 (publié en 1985) et avant, exécutaient les instructions une par une, de manière séquentielle.

Les processeurs ultérieurs ont commencé à utiliser le pipeline d’instructions – initialement simple, pour 804086, et enfin, Pentium Pro (sorti en 1995) a introduit un pipeline interne radicalement différent, le qualifiant de kernel Out Of Order (OOO). des opérations appelées micro-ops ou µops, puis toutes les micro-opérations de différentes instructions ont été placées dans un large pool de micro-opérations où elles étaient censées s’exécuter simultanément tant qu’elles ne dépendaient pas les unes des autres. Ce principe de pipeline OOO est toujours utilisé, presque inchangé, sur les processeurs modernes. Vous pouvez trouver plus d’informations sur l’instruction en pipeline dans cet article génial: https://www.gamedev.net/resources/_/technical/general-programming/a-journey-through-the-cpu-pipeline-r3115

Afin de simplifier la conception des puces, Intel a décidé de construire des processeurs de manière à ce que les instructions soient transformées en micro-opérations de manière très efficace, alors que d’autres ne le sont pas.

La conversion efficace des instructions en micro-opérations nécessite davantage de transistors, de sorte qu’Intel a décidé de réaliser des économies sur les transistors, au prix d’un décodage plus lent et de l’exécution de certaines instructions «complexes» ou «rarement utilisées».

Par exemple, le «Manuel de référence Intel® Architecture Optimization» http://download.intel.com/design/PentiumII/manuals/24512701.pdf mentionne ce qui suit: «Évitez d’utiliser des instructions complexes (par exemple, entrer, quitter ou boucler ) qui ont généralement plus de quatre µops et nécessitent plusieurs cycles pour être décodés. Utilisez plutôt des séquences d’instructions simples.

Donc, Intel a en quelque sorte décidé que l’instruction «loop» est «complexe» et, depuis lors, elle est devenue très lente. Cependant, il n’y a pas de référence officielle Intel sur la décomposition des instructions: combien de micro-opérations chaque instruction produit-elle et combien de cycles sont nécessaires pour la décoder.

Vous trouverez également des informations sur le moteur d’exécution obsolète dans le “Manuel de référence de l’optimisation des architectures Intel® 64 et IA-32” http://www.intel.com/content/dam/www/public/us/en/ documents / manuals / 64-ia-32-architectures-optimisation-manual.pdf section the 2.1.2.