En C ++, pourquoi et comment les fonctions virtuelles sont-elles plus lentes?

38

Quelqu'un peut-il expliquer en détail comment fonctionne exactement la table virtuelle et quels pointeurs sont associés lorsque des fonctions virtuelles sont appelées.

S'ils sont en fait plus lents, pouvez-vous indiquer que le temps nécessaire à l'exécution d'une fonction virtuelle est plus long que les méthodes de classe normales? Il est facile de perdre la trace de comment / ce qui se passe sans voir un code.

MdT
la source
5
Rechercher le bon appel de méthode depuis une table virtuelle va évidemment prendre plus de temps que d'appeler directement la méthode, car il reste encore beaucoup à faire. Une autre question est de savoir combien de temps, ou si ce temps supplémentaire est significatif dans le contexte de votre propre programme. en.wikipedia.org/wiki/Virtual_method_table
Robert Harvey
10
Plus lent que quoi exactement? J'ai vu du code avec une implémentation lente et cassée du comportement dynamique avec de nombreuses instructions switch simplement parce qu'un programmeur avait entendu dire que les fonctions virtuelles étaient lentes.
Christopher Creutzig
7
Souvent, ce n'est pas que les appels virtuels sont lents, mais que le compilateur n'a pas la capacité de les intégrer.
Kevin Hsu
4
@ Kevin Hsu: oui c'est tout à fait. Presque chaque fois que quelqu'un vous dit qu'il est plus rapide d'éliminer un "surcoût d'appel d'appel de fonction virtuelle", si vous examinez la source de toute accélération, cela proviendra d'optimisations qui sont maintenant possibles car le compilateur ne pouvait pas optimiser l'appel indéterminé précédemment.
timday
7
Même une personne capable de lire le code d'assemblage ne peut pas prédire avec précision son temps système lors de l'exécution réelle du processeur. Les fabricants de processeurs basés sur des ordinateurs de bureau ont investi dans des décennies de recherche dans la prédiction de branche, mais aussi dans la prédiction de valeur et l'exécution spéculative, principalement pour masquer la latence des fonctions virtuelles. Pourquoi? Parce que les systèmes d’exploitation de bureau et les logiciels les utilisent beaucoup. (Je ne dirais pas la même chose à propos des processeurs mobiles.)
rwong

Réponses:

55

Les méthodes virtuelles sont généralement implémentées via des tables de méthodes virtuelles (vtable en abrégé), dans lesquelles les pointeurs de fonction sont stockés. Cela ajoute un indirection à l’appel réel (il faut aller chercher l’adresse de la fonction à appeler depuis la table vtable, puis l’appeler - au lieu de simplement l’appeler tout de suite). Bien sûr, cela prend du temps et du code supplémentaire.

Cependant, ce n'est pas nécessairement la cause principale de la lenteur. Le vrai problème est que le compilateur (généralement / généralement) ne peut pas savoir quelle fonction sera appelée. Donc, il ne peut pas y insérer ou effectuer d’autres optimisations. Cela seul pourrait ajouter une douzaine d'instructions inutiles (préparer des registres, appeler puis rétablir l'état par la suite) et empêcher d'autres optimisations apparemment sans rapport. De plus, si vous branchez comme un fou en appelant de nombreuses implémentations différentes, vous subissez les mêmes hits que vous auriez du mal à vous faire ramifier comme un fou par d'autres moyens: le prédicteur de cache et de branche ne vous aidera pas, les branches prendront plus de temps que ce qui est parfaitement prévisible branche.

Gros mais : Ces succès sont généralement trop minimes pour être importants. Ils valent la peine d’être pris en compte si vous souhaitez créer un code hautes performances et envisagez d’ajouter une fonction virtuelle appelée à une fréquence alarmante. Cependant, gardez également à l’esprit que le remplacement des appels de fonctions virtuelles par d’autres moyens de créer des branches ( if .. else,switch , pointeurs de fonction, etc.) ne résoudra pas le problème fondamental - il peut très bien être plus lent. Le problème (s'il existe du tout) n'est pas les fonctions virtuelles mais l'indirection (inutile).

Edit: La différence dans les instructions d’appel est décrite dans d’autres réponses. Fondamentalement, le code pour un appel statique ("normal") est le suivant:

  • Copiez certains registres de la pile pour permettre à la fonction appelée d’utiliser ces registres.
  • Copiez les arguments dans des emplacements prédéfinis, de sorte que la fonction appelée puisse les trouver indépendamment de l'endroit où elle est appelée.
  • Poussez l'adresse de retour.
  • Branche / saute au code de la fonction, qui est une adresse de compilation et donc codée en dur dans le binaire par le compilateur / éditeur de liens.
  • Obtenez la valeur de retour à partir d'un emplacement prédéfini et restaurez les registres que vous souhaitez utiliser.

Un appel virtuel fait exactement la même chose, à la différence que l’adresse de la fonction n’est pas connue au moment de la compilation. Au lieu de cela, quelques instructions ...

  • Obtenez le pointeur vtable, qui pointe vers un tableau de pointeurs de fonction (adresses de fonction), un pour chaque fonction virtuelle, à partir de l'objet.
  • Récupère la bonne adresse de la table vtable dans un registre (l’index où l’adresse de la bonne fonction est stockée est décidé au moment de la compilation).
  • Accédez à l'adresse de ce registre plutôt que de passer à une adresse codée en dur.

En ce qui concerne les branches: une branche est tout ce qui saute à une autre instruction au lieu de simplement exécuter l'instruction suivante. Cela inclut if, des switchparties de boucles diverses, des appels de fonction, etc. et parfois, le compilateur implémente des choses qui ne semblent pas créer de branche d’une manière qui nécessite réellement une branche sous le capot. Voir Pourquoi le traitement d'un tableau trié est-il plus rapide qu'un tableau non trié? car cela peut être lent, ce que les processeurs font pour contrer ce ralentissement et comment ce n’est pas une panacée.

Communauté
la source
6
@ JörgWMittag ils sont tous des interprètes, et ils sont toujours plus lents que le code binaire généré par les compilateurs C ++
Sam
13
@ JörgWMittag Ces optimisations existent principalement pour rendre les liaisons indirectionnelles / tardives (presque) gratuites quand elles ne sont pas nécessaires , car dans ces langues, chaque appel est techniquement tardif. Si vous appelez réellement plusieurs méthodes virtuelles différentes d'un même endroit sur une courte période, ces optimisations n'ont aucune incidence positive ou négative (créez beaucoup de code pour rien). Les optimistes en C ++ ne sont pas très intéressés par ces optimisations car ils se trouvent dans une situation très différente ...
10
@ JörgWMittag ... Les optimistes ne sont pas très intéressés par ces optimisations, car ils se trouvent dans une situation très différente: la méthode vtable compilée par AOT est déjà assez rapide, très peu d'appels sont réellement virtuels, de nombreux cas de polymorphisme sont précoces - lié (via des modèles) et donc modifiable à l'optimisation AOT. Enfin, faire ces optimisations de manière adaptative (au lieu de simplement spéculer au moment de la compilation) nécessite la génération de code à l'exécution, ce qui introduit des tonnes de maux de tête. Les compilateurs JIT ont déjà résolu ces problèmes pour d'autres raisons, donc cela ne les dérange pas, mais les compilateurs AOT veulent l'éviter.
3
bonne réponse, +1. Il convient toutefois de noter que les résultats de la création de branches sont connus au moment de la compilation, par exemple lorsque vous écrivez des classes de structure devant prendre en charge différentes utilisations, mais une fois que le code de l'application interagit avec ces classes, leur utilisation est déjà connue. Dans ce cas, l'alternative aux fonctions virtuelles pourrait être les modèles C ++. Le bon exemple serait CRTP, qui émule le comportement de la fonction virtuelle sans aucun vtables: en.wikipedia.org/wiki/Curiously_recurring_template_pattern
DXM
3
@ James Vous avez un point. Ce que j’ai essayé de dire, c’est que toute indirection a les mêmes problèmes, elle n’a rien de spécifique virtual.
23

Voici un code désassemblé réel d'un appel de fonction virtuelle et d'un appel non virtuel, respectivement:

mov    -0x8(%rbp),%rax
mov    (%rax),%rax
mov    (%rax),%rax
callq  *%rax

callq  0x4007aa

Vous pouvez constater que l'appel virtuel nécessite trois instructions supplémentaires pour rechercher l'adresse correcte, tandis que l'adresse de l'appel non virtuel peut être compilée.

Toutefois, notez que la plupart du temps, ce temps de recherche supplémentaire peut être considéré comme négligeable. Dans les situations où le temps de recherche serait important, comme dans une boucle, la valeur peut généralement être mise en cache en effectuant les trois premières instructions avant la boucle.

L'autre situation dans laquelle le temps de recherche devient important est si vous avez une collection d'objets et que vous passez en boucle en appelant une fonction virtuelle sur chacun d'eux. Cependant, dans ce cas, vous aurez besoin d' un moyen de sélectionner la fonction à appeler de toute façon, et une recherche dans une table virtuelle est un moyen aussi efficace que n'importe lequel. En fait, étant donné que le code de recherche vtable est si largement utilisé, il est fortement optimisé. Par conséquent, essayer de le contourner manuellement a de bonnes chances d’entraîner une dégradation des performances.

Karl Bielefeldt
la source
1
Ce qu'il faut comprendre, c'est que la consultation de vtable et l'appel indirect auront dans la quasi-totalité des cas un impact négligeable sur la durée totale d'exécution de la méthode appelée.
John R. Strohm
12
@ JohnR.Strohm Un homme négligeable est le goulot d'étranglement d'un autre homme
James
1
-0x8(%rbp). oh mon ... cette syntaxe AT & T.
Abyx
" trois instructions additionnelles " non, seulement deux: chargement du vptr et chargement du pointeur de fonction
curaryguy
@curiousguy, il s'agit en fait de trois instructions supplémentaires. Vous avez oublié qu'une méthode virtuelle est toujours appelée sur un pointeur . Vous devez donc d'abord charger le pointeur dans un registre. Pour résumer, la toute première étape consiste à charger l’adresse que la variable pointeur contient dans le registre% rax, puis, en fonction de l’adresse dans le registre, chargez le vtpr sur cette adresse pour enregistrer% rax, puis en fonction de cette adresse dans le registre. inscrivez-vous, chargez l'adresse de la méthode à appeler dans% rax, puis appelez q *% rax !.
Gab
18

Plus lent que quoi ?

Les fonctions virtuelles résolvent un problème qui ne peut pas être résolu par des appels de fonction directs. En général, vous ne pouvez comparer que deux programmes calculant la même chose. "Ce traceur de rayons est plus rapide que ce compilateur" n'a pas de sens, et ce principe se généralise même aux petites choses comme les fonctions individuelles ou les constructions de langage de programmation.

Si vous n'utilisez pas une fonction virtuelle pour basculer de manière dynamique sur un morceau de code basé sur une donnée, telle que le type d'un objet, vous devrez alors utiliser quelque chose d'autre, switch instruction, pour accomplir la même chose. Ce quelque chose d'autre a ses propres frais généraux, plus des implications sur l'organisation du programme qui influencent sa maintenabilité et sa performance globale.

Notez qu'en C ++, les appels aux fonctions virtuelles ne sont pas toujours dynamiques. Lorsque des appels sont effectués sur un objet dont le type exact est connu (parce que l'objet n'est pas un pointeur ou une référence, ou parce que son type peut être inféré de manière statique), les appels ne sont que des appels de fonction membres normaux. Cela signifie non seulement qu'il n'y a pas de surcharge d'expédition, mais également que ces appels peuvent être intégrés de la même manière que les appels ordinaires.

En d'autres termes, votre compilateur C ++ peut fonctionner lorsque les fonctions virtuelles ne nécessitent pas de répartition virtuelle. Il n'y a donc généralement aucune raison de s'inquiéter de leurs performances par rapport aux fonctions non virtuelles.

Nouveau: De plus, nous ne devons pas oublier les bibliothèques partagées. Si vous utilisez une classe qui se trouve dans une bibliothèque partagée, l'appel d'une fonction membre ordinaire ne sera pas simplement une belle séquence d'instruction semblable à celle-ci callq 0x4007aa. Il doit passer par quelques étapes, comme indirecte via une "table de liaison de programme" ou une telle structure. Par conséquent, l'indirection indirecte des bibliothèques partagées pourrait niveler (sinon complètement) la différence de coût entre un appel virtuel (réellement indirect) et un appel direct. Le raisonnement sur les compromis de la fonction virtuelle doit donc tenir compte de la construction du programme: si la classe de l'objet cible est liée de manière monolithique au programme qui effectue l'appel.

Kaz
la source
4
"Plus lent que quoi?" - Si vous faites une méthode virtuelle qui n’a pas à être, vous avez un très bon matériel de comparaison.
tdammers
2
Merci de signaler que les appels aux fonctions virtuelles ne sont pas toujours dynamiques. Chaque réponse ici donne l’impression que déclarer une fonction virtuelle signifie un impact automatique sur les performances, quelles que soient les circonstances.
Syndog
12

parce qu'un appel virtuel équivaut à

res_t (*foo)(arg_t);
foo = (obj->vtable[foo_offset]);
foo(obj,args)

où, avec une fonction non virtuelle, le compilateur peut plier de manière constante la première ligne, il s'agit d'un déréférencement d'un ajout et d'un appel dynamique transformé en un simple appel statique

cela lui permet également d’intégrer la fonction (avec toutes les conséquences de son optimisation)

monstre à cliquet
la source