Quels opcodes sont plus rapides au niveau CPU? [fermé]

19

Dans chaque langage de programmation, il existe des ensembles d'opcodes recommandés par rapport aux autres. J'ai essayé de les énumérer ici, par ordre de vitesse.

  1. Au niveau du bit
  2. Addition / soustraction de nombres entiers
  3. Multiplication / division entière
  4. Comparaison
  5. Contrôle du flux
  6. Addition / soustraction de flotteur
  7. Multiplication / division de flotteur

Lorsque vous avez besoin de code haute performance, C ++ peut être optimisé manuellement en assembleur, pour utiliser des instructions SIMD ou un flux de contrôle plus efficace, des types de données, etc. J'essaie donc de comprendre si le type de données (int32 / float32 / float64) ou l'opération utilisée ( *, +, &) influe sur la performance au niveau du processeur.

  1. Une seule multiplication est-elle plus lente sur le processeur qu'un ajout?
  2. Dans la théorie MCU, vous apprenez que la vitesse des opcodes est déterminée par le nombre de cycles CPU nécessaires pour s'exécuter. Cela signifie-t-il donc que la multiplication prend 4 cycles et que l'addition prend 2 cycles?
  3. Quelles sont exactement les caractéristiques de vitesse des opcodes mathématiques et de flux de contrôle de base?
  4. Si deux opcodes prennent le même nombre de cycles à exécuter, alors les deux peuvent être utilisés de manière interchangeable sans aucun gain / perte de performances?
  5. Tout autre détail technique que vous pouvez partager concernant les performances du processeur x86 est apprécié
Robinicks
la source
17
Cela ressemble beaucoup à une optimisation prématurée, et rappelez-vous que le compilateur ne produit pas ce que vous tapez, et vous ne voulez vraiment pas écrire d'assembly à moins que vous ne l'ayez vraiment vraiment aussi.
Roy T.
3
La multiplication et la division des flotteurs sont des choses totalement différentes, vous ne devriez pas les mettre dans la même catégorie. Pour les nombres à n bits, la multiplication est un processus O (n) et la division est un processus O (nlogn). Cela rend la division environ 5 fois plus lente que la multiplication sur les processeurs modernes.
sam hocevar
1
La seule vraie réponse est "le profil".
Tetrad
1
S'étendant sur la réponse de Roy, l'assemblage optimisant la main sera presque toujours une perte nette, sauf si vous êtes vraiment vraiment exceptionnel. Les processeurs modernes sont des bêtes très complexes et de bons compilateurs d'optimisation effectuent des transformations de code qui sont entièrement non évidentes et non triviales à coder à la main. Même pour SSE / SIMD, utilisez toujours toujours les éléments intrinsèques en C / C ++ et laissez le compilateur optimiser leur utilisation pour vous. L'utilisation d'un assemblage brut désactive les optimisations du compilateur et vous perdez gros.
Sean Middleditch
Vous n'avez pas besoin d'optimiser manuellement l'assemblage pour utiliser SIMD. SIMD est très utile pour optimiser en fonction de la situation, mais il existe une convention généralement standard (il fonctionne sur GCC et MSVC au moins) pour utiliser SSE2. En ce qui concerne votre liste, sur un processeur multi-pipelines superserscalaire moderne, la dépendance des données et la pression de registre causent plus de problèmes que les performances en nombre entier brut et parfois en virgule flottante; il en va de même pour la localité des données. Au fait, la division entière est la même que la multiplication sur un x86 moderne
OrgnlDave

Réponses:

26

Les guides d'optimisation d'Agner Fog sont excellents. Il a des guides, des tableaux de synchronisation des instructions et des documents sur la microarchitecture de toutes les conceptions récentes de CPU x86 (remontant jusqu'à Intel Pentium). Voir aussi quelques autres ressources liées depuis /programming//tags/x86/info

Juste pour le plaisir, je répondrai à certaines des questions (chiffres des processeurs Intel récents). Le choix des opérations n'est pas le principal facteur d'optimisation du code (sauf si vous pouvez éviter la division.)

Une seule multiplication est-elle plus lente sur le processeur qu'un ajout?

Oui (sauf si c'est par une puissance de 2). (3-4x la latence, avec seulement un par débit d'horloge sur Intel.) Ne vous éloignez pas pour l'éviter, car c'est aussi rapide que 2 ou 3 ajouts.

Quelles sont exactement les caractéristiques de vitesse des opcodes mathématiques et de flux de contrôle de base?

Consultez les tableaux d'instructions et le guide de microarchitecture d'Agner Fog si vous voulez savoir exactement : P. Soyez prudent avec les sauts conditionnels. Les sauts inconditionnels (comme les appels de fonction) ont une petite surcharge, mais pas beaucoup.

Si deux opcodes prennent le même nombre de cycles à exécuter, alors les deux peuvent être utilisés de manière interchangeable sans aucun gain / perte de performances?

Non, ils pourraient rivaliser pour le même port d'exécution qu'autre chose, ou ils pourraient ne pas le faire. Cela dépend des autres chaînes de dépendance sur lesquelles le processeur peut travailler en parallèle. (En pratique, il n'y a généralement pas de décision utile à prendre. Il arrive parfois que vous puissiez utiliser un décalage vectoriel ou un shuffle vectoriel, qui s'exécutent sur différents ports sur les processeurs Intel. Mais le décalage par octets de l'ensemble du registre ( PSLLDQetc.) fonctionne dans l'unité de lecture aléatoire.)

Tout autre détail technique que vous pouvez partager concernant les performances du processeur x86 est apprécié

Les documents microarch d'Agner Fog décrivent les pipelines des processeurs Intel et AMD avec suffisamment de détails pour déterminer exactement combien de cycles une boucle devrait prendre par itération, et si le goulot d'étranglement est le débit uop, une chaîne de dépendance ou la contention pour un port d'exécution. Voir certaines de mes réponses sur StackOverflow, comme celle-ci ou celle-ci .

En outre, http://www.realworldtech.com/haswell-cpu/ (et similaire pour les conceptions antérieures) est amusant à lire si vous aimez la conception de CPU.

Voici votre liste, triée pour un processeur Haswell, basée sur mes meilleures estimations. Ce n'est pas vraiment une façon utile de penser aux choses pour autre chose que le réglage d'une boucle asm. Les effets de prédiction de cache / branche dominent généralement, alors écrivez votre code pour avoir de bons modèles. Les nombres sont très ondulants et essaient de tenir compte d'une latence élevée, même si le débit n'est pas un problème, ou de générer plus d'ups qui obstruent le tuyau pour que d'autres choses se produisent en parallèle. Esp. les numéros de cache / branche sont très composés. La latence est importante pour les dépendances transportées en boucle, le débit est important lorsque chaque itération est indépendante.

TL: DR ces chiffres sont composés en fonction de ce que j'imagine pour un cas d'utilisation "typique", en ce qui concerne les compromis entre la latence, les goulots d'étranglement des ports d'exécution et le débit frontal (ou les blocages pour des choses comme les échecs de branche ). Veuillez ne pas utiliser ces chiffres pour tout type d'analyse de performance sérieuse .

  • 0,5 à 1 au niveau du bit / addition entière / soustraction /
    décalage et rotation (nombre de const à la compilation) /
    versions vectorielles de tous ces éléments (1 à 4 par cycle de débit, 1 cycle de latence)
  • 1 vecteur min, max, comparer-égal, comparer-plus (pour créer un masque)
  • 1.5 mélange de vecteurs. Haswell et les plus récents n'ont qu'un seul port de lecture aléatoire, et il me semble qu'il est courant d'avoir besoin de beaucoup de lecture aléatoire si vous en avez besoin, donc je le pondère légèrement plus haut pour encourager à penser à utiliser moins de lecture aléatoire. Ils ne sont pas gratuits, surtout. si vous avez besoin d'un masque de contrôle pshufb de la mémoire.
  • 1.5 chargement / stockage (accès au cache L1. Débit supérieur à la latence)
  • 1,75 Multiplication de nombres entiers (latence 3c / une par sortie 1c sur Intel, lat 4c sur AMD et une seule par sortie 2c). Les petites constantes sont encore moins chères en utilisant LEA et / ou ADD / SUB / shift . Mais bien sûr, les constantes au moment de la compilation sont toujours bonnes et peuvent souvent être optimisées pour d'autres choses. (Et la multiplication dans une boucle peut souvent être réduite par le compilateur tmp += 7dans une boucle au lieu de tmp = i*7)
  • 1.75 quelques shuffle vectoriels 256b (latence supplémentaire sur les insns qui peuvent déplacer des données entre 128b voies d'un vecteur AVX). (Ou 3 à 7 sur Ryzen où les shuffles de franchissement de voie ont besoin de beaucoup plus d'ups)
  • 2 fp add / sub (et versions vectorielles de celui-ci) (1 ou 2 par débit de cycle, latence de 3 à 5 cycles). Peut être lent si vous goulot d'étranglement sur la latence, par exemple en sommant un tableau avec seulement 1 sumvariable. (Je pourrais peser cela et fp mul aussi bas que 1 ou aussi haut que 5 selon le cas d'utilisation).
  • 2 vecteurs fp mul ou FMA. (x * y + z est aussi bon marché qu'un mul ou un add si vous compilez avec le support FMA activé).
  • 2 insertion / extraction de registres à usage général dans des éléments vectoriels ( _mm_insert_epi8, etc.)
  • 2.25 vector int mul (éléments 16 bits ou pmaddubsw faisant 8 * 8 -> 16 bits). Moins cher sur Skylake, avec un meilleur débit que le scalaire mul
  • 2.25 décalage / rotation par nombre variable (latence 2c, un par débit 2c sur Intel, plus rapide sur AMD ou avec BMI2)
  • 2.5 Comparaison sans branchement ( y = x ? a : b, ou y = x >= 0) ( test / setccou cmov)
  • 3 conversion int-> float
  • 3 Flux de contrôle parfaitement prévu (branchement prévu, appel, retour).
  • 4 vecteurs int mul (éléments 32 bits) (2 uops, latence 10c sur Haswell)
  • 4 division entière ou %par une constante de temps de compilation (non-puissance de 2).
  • 7 opérations horizontales vectorielles (par exemple, PHADDajout de valeurs dans un vecteur)
  • 11 (vector) FP Division (latence 10-13c, une par débit 7c ou pire). (Peut être bon marché si utilisé rarement, mais le débit est 6 à 40 fois pire que FP mul)
  • 13? Flux de contrôle (branche mal prédite, peut-être 75% prévisible)
  • 13 division int ( oui vraiment , c'est plus lent que la division FP et ne peut pas vectoriser). (Notez que les compilateurs divisent par une constante en utilisant mul / shift / add avec une constante magique , et div / mod par des puissances de 2 est très bon marché.)
  • 16 (vecteur) FP sqrt
  • 25? charge (accès au cache L3). (les magasins cache-miss sont moins chers que les charges.)
  • 50? FP trig / exp / log. Si vous avez besoin de beaucoup d'exp / log et n'avez pas besoin d'une précision totale, vous pouvez échanger la précision contre la vitesse avec un polynôme plus court et / ou une table. Vous pouvez également vectoriser SIMD.
  • 50-80? branche toujours imprévue, coûtant 15 à 20 cycles
  • 200-400? charger / stocker (cache manquant)
  • 3000 ??? lire la page à partir du fichier (hit du cache du disque du système d'exploitation) (composition des nombres ici)
  • 20000 ??? page de lecture du disque (échec du cache du disque du système d'exploitation, SSD rapide) (numéro entièrement composé)

J'ai totalement inventé cela sur la base de suppositions . Si quelque chose ne va pas, c'est soit parce que je pensais à un cas d'utilisation différent, soit à une erreur d'édition.

Le coût relatif des choses sur les processeurs AMD sera similaire, sauf qu'ils ont des décaleurs entiers plus rapides lorsque le nombre de décalages est variable. Les processeurs de la famille AMD Bulldozer sont bien sûr plus lents sur la plupart des codes, pour diverses raisons. (Ryzen est assez bon pour beaucoup de choses).

Gardez à l'esprit qu'il est vraiment impossible de réduire les choses à un coût unidimensionnel . Outre les erreurs de cache et les erreurs de branchement, le goulot d'étranglement dans un bloc de code peut être la latence, le débit uop total (frontend) ou le débit d'un port spécifique (port d'exécution).

Une opération "lente" comme la division FP peut être très bon marché si le code environnant maintient le CPU occupé avec d'autres travaux . (le vecteur FP div ou sqrt sont 1 uop chacun, ils ont juste une latence et un débit médiocres. Ils bloquent uniquement l'unité de division, pas le port d'exécution entier sur lequel il est activé. La division entière est de plusieurs uops.) Donc, si vous n'avez qu'une seule division FP pour chaque ~ 20 mul et ajouter, et il y a d'autres travaux à faire par le CPU (par exemple une itération de boucle indépendante), alors le "coût" de la div FP pourrait être à peu près le même qu'un FP mul. C'est probablement le meilleur exemple de quelque chose qui est à faible débit quand c'est tout ce que vous faites, mais qui se mélange très bien avec d'autres codes (lorsque la latence n'est pas un facteur), en raison du faible nombre total d'ups.

Notez que la division entière n'est pas aussi conviviale que le code environnant: Sur Haswell, c'est 9 uops, avec un par débit 8-11c, et une latence 22-29c. (La division 64 bits est beaucoup plus lente, même sur Skylake.) Ainsi, les nombres de latence et de débit sont quelque peu similaires à FP div, mais FP div n'est qu'un uop.

Pour des exemples d'analyse d'une courte séquence d'insns pour le débit, la latence et le nombre total d'ups, consultez certaines de mes réponses SO:

IDK si d'autres personnes écrivent des réponses SO incluant ce type d'analyse. J'ai beaucoup plus de facilité à trouver le mien, car je sais que je vais souvent dans ce détail et je me souviens de ce que j'ai écrit.

Peter Cordes
la source
La "branche prédite" à 4 est logique - quelle devrait être la "branche prédite" à 20-25? (J'avais pensé que les branches mal prévues (répertoriées autour de 13) étaient beaucoup plus chères que cela, mais c'est exactement pourquoi je suis sur cette page, pour apprendre quelque chose de plus proche de la vérité - merci pour la grande table!)
Matt
@Matt: Je pense que c'était une erreur d'édition et était censé être une "branche mal prévue". Merci d'avoir fait remarquer cela. Notez que 13 est pour une branche imparfaitement prédite, pas une branche toujours mal prédite, j'ai donc clarifié cela. J'ai refait le handwaving et ai fait quelques modifications. : P
Peter Cordes
16

Cela dépend du CPU en question, mais pour un CPU moderne, la liste est quelque chose comme ceci:

  1. Au niveau du bit, addition, soustraction, comparaison, multiplication
  2. Division
  3. Contrôler le flux (voir réponse 3)

Selon le processeur, il peut y avoir un coût considérable pour travailler avec des types de données 64 bits.

Vos questions:

  1. Pas du tout ou pas de façon appréciable sur un processeur moderne. Dépend du CPU.
  2. Cette information est quelque chose comme 20 à 30 ans (l'école craint, vous en avez maintenant la preuve), les processeurs modernes gèrent un nombre variable d'instructions par horloge, combien dépendent de ce que le planificateur propose.
  3. La division est un peu plus lente que les autres, le flux de contrôle est très rapide si la prédiction de branche est correcte et très lente si elle est incorrecte (quelque chose comme 20 cycles, dépend du CPU). Le résultat est que beaucoup de code est limité principalement par le flux de contrôle. Ne faites pas avec ifce que vous pouvez raisonnablement faire avec l'arithmétique.
  4. Il n'y a pas de nombre fixe pour le nombre de cycles qu'une instruction prend, mais parfois deux instructions différentes peuvent s'exécuter de manière égale, les mettre dans un autre contexte et peut-être pas, les exécuter sur un processeur différent et vous êtes susceptible de voir un 3e résultat.
  5. En plus du flux de contrôle, l'autre perte de temps importante est le manque de cache, chaque fois que vous essayez de lire des données qui ne sont pas dans le cache, le processeur devra attendre qu'il soit récupéré de la mémoire. En général, vous devriez essayer de gérer simultanément les éléments de données les uns à côté des autres plutôt que de sélectionner des données de partout.

Et enfin, si vous créez un jeu, ne vous inquiétez pas trop de tout cela, mieux vous concentrer sur la création d'un bon jeu que de couper les cycles CPU.

aaaaaaaaaaaa
la source
Je voudrais également souligner que le FPU est sacrément rapide: en particulier sur Intel - donc le point fixe n'est vraiment nécessaire que si vous voulez des résultats déterministes.
Jonathan Dickinson
2
Je mettrais juste plus l'accent sur la dernière partie - faire un bon match. Il est utile d'avoir un code clair - c'est pourquoi 3. ne s'applique que lorsque vous mesurez réellement un problème de performances. Il est toujours facile de changer ces ifs en quelque chose de mieux si le besoin s'en fait sentir. D'un autre côté, 5. est plus délicat - je suis tout à fait d'accord pour dire que c'est un cas où vous voulez vraiment réfléchir en premier, car cela signifie généralement changer l'architecture.
Luaan
3

J'ai fait un test sur le fonctionnement entier qui a bouclé un million de fois sur x64_64, arrive à une brève conclusion comme ci-dessous,

ajouter --- 116 microsecondes

sous ---- 116 microsecondes

mul ---- 1036 microsecondes

div ---- 13037 microsecondes

les données ci-dessus ont déjà réduit la surcharge induite par la boucle,

hxiao
la source
2

Les manuels du processeur Intel sont téléchargeables gratuitement sur leur site Web. Ils sont assez grands mais peuvent techniquement répondre à votre question. Le manuel d'optimisation en particulier est ce que vous recherchez, mais le manuel d'instructions contient également les temps et les latences pour la plupart des principales lignes de CPU pour les instructions simd car elles varient d'une puce à l'autre.

En général, je considérerais les branches complètes ainsi que la recherche de pointeurs (traverals de liste de liens, appeler des fonctions virtuelles) comme les meilleurs pour les tueurs de perf, mais les processeurs x86 / x64 sont très bons dans les deux, par rapport à d'autres architectures. Si vous portez sur une autre plate-forme, vous verrez à quel point ils peuvent être problématiques, si vous écrivez du code haute performance.

Zoner
la source
+1, les charges dépendantes (poursuite du pointeur) sont un gros problème. Un échec de cache empêchera même le démarrage de futures charges. Avoir plusieurs charges de la mémoire principale en vol à la fois donne une bien meilleure bande passante que d'avoir une seule opération nécessite que la précédente soit complètement terminée.
Peter Cordes