CPU modernes Inner Loop indirection Optimisations

Question

De http://www.boost.org/community/implementation_variations.html

» ... les différences de codage telles que la modification d'une classe du virtuel aux membres non virtuels ou la suppression d'un niveau d'indirection ne sont pas susceptibles de faire une différence mesurable à moins profonde dans une boucle intérieure. Et même dans une boucle intérieure, les processeurs modernes exécuter souvent de telles séquences de code concurrentes dans le même nombre de cycles d'horloge! "

J'essaie de comprendre la partie « même dans la boucle intérieure ». Plus précisément quels mécanismes mettre en œuvre les processeurs pour exécuter les deux codes (virtuels vs niveau supplémentaire non virtuel ou un de indirection) dans le même nombre de cycles d'horloge? Je sais que sur le pipelining d'instruction et la mise en cache, mais comment est-il possible d'effectuer un appel virtuel dans le même nombre de cycles d'horloge comme un appel non virtuel? Comment est le indirection "perdu"?

Answer 1

Caching (par exemple mise en mémoire cache cible branche ), les unités de chargement parallèles (partie de pipelining, mais aussi des choses comme « coup sous miss » qui ne bloque pas le pipeline), et out-of-order exécution sont susceptibles d'aider à transformer un load-load-branch en quelque chose qui est plus proche d'un branch fixe. pliage Instruction / élimination (ce qui est le terme approprié pour cela?) dans la phase de décodage ou prédiction de branchement du pipeline peut également contribuer.

Tout cela repose sur beaucoup de choses différentes, cependant: combien de cibles de différentes succursales, il y a (par exemple, combien de différentes surcharges virtuelles sont vous susceptibles de déclencher), combien de choses vous en boucle sur (est le cache cible de branche " chaud "? Que diriez-vous Icache / dcache?), comment les tables virtuelles ou des tables de indirection sont décrits dans cet mémoire (sont-ils mettre en cache l'environnement, ou est chaque nouvelle charge vtable expulse éventuellement un vieux vtable?), est le cache invalidée à plusieurs reprises en raison de ping-ponging multi-cœurs, etc ...

(Disclaimer: Je ne suis certainement pas un expert ici, et beaucoup de mes connaissances vient étudier en ordre des processeurs embarqués, donc une partie de cette extrapolation est Si vous avez des corrections, ne hésitez pas à commentaire.!)

La bonne façon de déterminer si elle va être un problème pour un programme spécifique est bien sûr de profil. Si vous le pouvez, le faire avec l'aide de compteurs matériels -. Ils peuvent vous dire beaucoup de choses sur ce qui se passe dans les différentes étapes du pipeline

---

Edit:

Comme Hans souligne en Passant un commentaire ci-dessus CPU moderne Inner Loop indirection Optimisations , la clé pour obtenir ces deux choses à prendre la même quantité de temps est la capacité de « retraite » effectivement plus d'une instruction par cycle. élimination d'instruction peut aider, mais superscalaire conception est probablement plus important (coup sous manquer est un exemple très petit et spécifique, les unités de charge redondants pourraient être un meilleur).

Prenons une situation idéale, et d'assumer une branche directe est juste une instruction:

branch dest

... et une branche indirecte est de trois (vous pouvez peut-être obtenir en deux, mais il est supérieur à un):

load vtable from this
load dest from vtable
branch dest

Supposons une situation absolument parfaite: * cela et l'ensemble vtable sont dans le cache L1, le cache L1 est assez rapide pour supporter amorti un cycle par coût d'instruction pour les deux charges. (Vous pouvez même prendre le processeur réorganisés les charges et les entremêlées avec des instructions antérieures pour laisser le temps pour eux de terminer avant la branche, il n'a pas d'importance pour cet exemple.) Supposons également le cache cible de branchement est chaud, et il n'y a pas de pipeline coût de chasse pour la branche et l'instruction de branchement se résume à un seul cycle (après amortissement).

minimum théorique temps pour le premier exemple est donc 1 cycle (après amortissement).

Le minimum théorique pour le deuxième exemple, l'élimination d'instruction absent ou des unités fonctionnelles redondante ou quelque chose qui va permettre à la retraite plus d'une instruction par cycle, est de 3 cycles (il y a 3 instructions)!

La charge indirecte sera toujours plus lent, car il y a plus d'instructions, jusqu'à ce que vous atteignez en quelque chose comme la conception superscalaire qui permet de prendre sa retraite plus d'une instruction par cycle.

Une fois que vous avez cela, le minimum pour les deux exemples devient quelque chose entre 0 et 1 cycles, encore une fois, tout est fourni d'autre idéal. On peut dire que vous devez avoir des circonstances plus idéales pour le second exemple pour atteindre réellement ce minimum théorique que pour le premier exemple, mais il est maintenant possible.

Dans certains cas, vous auriez souciez, vous allez probablement pas pour atteindre ce minimum soit pour exemple. Soit le cache cible de branchement sera froid, ou la vtable ne sera pas dans le cache de données, ou la machine ne sera pas capable de réordonner les instructions pour tirer le meilleur parti des unités fonctionnelles redondantes.

... c'est là le profilage arrive, qui est généralement une bonne idée de toute façon.

peut juste épouser une légère paranoïa virtuals en premier lieu. Voir article de Noel Llopis sur des données axées sur la conception , l'excellent Pitfalls de diapositives orientée objet Programmation et présentations grincheux-encore-éducatifs de Mike Acton . Maintenant, vous avez soudainement emménagé dans les modèles que la CPU est déjà susceptible d'être heureux avec, si vous traitez beaucoup de données.

caractéristiques linguistiques de haut niveau comme virtuel sont généralement un compromis entre l'expressivité et le contrôle. Je pense sincèrement, mais, simplement augmenter votre conscience de ce que virtuel est en fait faire (ne pas avoir peur de lire le point de vue du démontage de temps en temps, et certainement coup d'oeil à des manuels d'architecture de votre CPU), vous aurez tendance à utiliser quand il est logique et non quand il ne fonctionne pas et un profileur peut couvrir le reste si nécessaire.

one-size-fits-toutes les déclarations sur « ne pas utiliser virtuelle » ou « l'utilisation virtuelle est peu susceptible de faire une différence mesurable » me font Grouchy. La réalité est généralement plus compliqué, et soit vous allez être dans une situation où vous vous souciez assez au profil ou éviter, ou vous êtes dans cet autre 95% où il est probablement pas la peine attentionnée, sauf pour le contenu pédagogique possible.

Answer 2

Pipelining est la voie principale.

Il peut prendre 20 cycles d'horloge pour charger une instruction, le décoder, effectuer des actions de références et les charger de mémoire indirecte. Mais en raison de la construction de ce pipeline du processeur peut être exécuter des parties de 19 autres instructions en même temps à différents stades de la canalisation donnant un débit global de 1 instruction à chaque cycle d'horloge, peu importe combien de temps il faut en fait pour nourrir cette instruction par le pipeline.

Answer 3

Qu'est-ce qui se passe, je pense est que le processeur a un cache spécial qui contient les emplacements et les cibles des branches et des sauts indirects. Si un saut indirect est rencontré à 12.345.678 $, et la dernière fois qu'il a été rencontré, il est allé répondre à 12.348.765 $, le processeur peut commencer l'exécution spéculative des instructions à l'adresse 12.348.765 $ avant même qu'elle résout l'adresse de la branche. Dans de nombreux cas, dans la boucle interne d'une fonction, un saut indirect particulier sera toujours sauter à la même adresse pendant toute la durée de la boucle. Le cache-saut indirect peut ainsi éviter les pénalités de branchement.

Answer 4

unités centrales modernes utilisent une technique de prédiction de branchement adaptatif qui peut prédire de nombreux sauts indirects tels que vous obtenez avec une implémentation vtable des fonctions virtuelles. Voir http://en.wikipedia.org/wiki/Branch_prediction#Prediction_of_indirect_jumps

Answer 5

Si la CPU a déjà l'adresse de la mémoire dans le cache, puis l'exécution d'une instruction de chargement est trivial, si cela.