Table de méthodes virtuelles

En programmation informatique , une table de méthodes virtuelles ( VMT ), une table de fonctions virtuelles , une table d'appels virtuelle , une table de répartition , vtable ou vftable est un mécanisme utilisé dans un langage de programmation pour prendre en charge la répartition dynamique (ou la liaison de méthode d'exécution ).

Chaque fois qu'une classe définit une fonction virtuelle (ou méthode ), la plupart des compilateurs ajoutent une variable membre cachée à la classe qui pointe vers un tableau de pointeurs vers des fonctions (virtuelles) appelé table de méthodes virtuelles. Ces pointeurs sont utilisés lors de l'exécution pour appeler les implémentations de fonctions appropriées, car au moment de la compilation, on ne sait peut-être pas encore si la fonction de base doit être appelée ou une fonction dérivée implémentée par une classe qui hérite de la classe de base.

Il existe de nombreuses façons différentes d'implémenter une telle répartition dynamique, mais l'utilisation de tables de méthodes virtuelles est particulièrement courante en C++ et dans les langages apparentés (tels que D et C# ). Les langages qui séparent l'interface de programmation des objets de l'implémentation, comme Visual Basic et Delphi , ont également tendance à utiliser cette approche, car elle permet aux objets d'utiliser une implémentation différente simplement en utilisant un ensemble différent de pointeurs de méthode. Cette méthode permet de créer des bibliothèques externes, là où d'autres techniques ne le permettraient peut-être pas.

Supposons qu'un programme contienne trois classes dans une hiérarchie d'héritage : une superclasse , Cat , et deux sous-classes , HouseCat et Lion . La classe Cat définit une fonction virtuelle nommée speak , de sorte que ses sous-classes peuvent fournir une implémentation appropriée (par exemple, meow ou roar ). Lorsque le programme appelle la fonction speak sur une référence Cat (qui peut faire référence à une instance de Cat , ou à une instance de HouseCat ou Lion ), le code doit être capable de déterminer à quelle implémentation de la fonction l'appel doit être envoyé . Cela dépend de la classe réelle de l'objet, et non de la classe de la référence à celui-ci ( Cat ). La classe ne peut généralement pas être déterminée de manière statique (c'est-à-dire au moment de la compilation ), de sorte que le compilateur ne peut pas non plus décider quelle fonction appeler à ce moment-là. L'appel doit être envoyé à la bonne fonction de manière dynamique (c'est-à-dire au moment de l'exécution ).

La table de méthodes virtuelles d'un objet contiendra les adresses des méthodes liées dynamiquement de l'objet. Les appels de méthode sont effectués en récupérant l'adresse de la méthode à partir de la table de méthodes virtuelles de l'objet. La table de méthodes virtuelles est la même pour tous les objets appartenant à la même classe et est donc généralement partagée entre eux. Les objets appartenant à des classes compatibles avec le type (par exemple, des frères et sœurs dans une hiérarchie d'héritage) auront des tables de méthodes virtuelles avec la même disposition : l'adresse d'une méthode donnée apparaîtra au même décalage pour toutes les classes compatibles avec le type. Ainsi, la récupération de l'adresse de la méthode à partir d'un décalage donné dans une table de méthodes virtuelle obtiendra la méthode correspondant à la classe réelle de l'objet.

Les normes C++ n'indiquent pas exactement comment la répartition dynamique doit être implémentée, mais les compilateurs utilisent généralement des variations mineures sur le même modèle de base.

En règle générale, le compilateur crée une table de méthodes virtuelles distincte pour chaque classe. Lorsqu'un objet est créé, un pointeur vers cette table, appelé pointeur de table virtuelle , vpointer ou VPTR , est ajouté en tant que membre caché de cet objet. Ainsi, le compilateur doit également générer du code « caché » dans les constructeurs de chaque classe pour initialiser le pointeur de table virtuelle d'un nouvel objet vers l'adresse de la table de méthodes virtuelles de sa classe.

De nombreux compilateurs placent le pointeur de table virtuelle comme dernier membre de l'objet ; d'autres le placent comme premier ; le code source portable fonctionne dans les deux sens. Par exemple, g++ plaçait auparavant le pointeur à la fin de l'objet.

Considérez les déclarations de classe suivantes dans la syntaxe C++ :

classe B1 { public : virtuel ~ B1 () {} void fnonvirtual () {} virtuel void f1 () {} int int_in_b1 ; };
classe B2 { public : virtuel ~ B2 () {} virtuel void f2 () {} int int_in_b2 ; };

utilisé pour dériver la classe suivante :

classe D : public B1 , public B2 { public : void d () {} void f2 () override {} int int_in_d ; };

et le morceau de code C++ suivant :

B2 * b2 = nouveau B2 (); D * d = nouveau D ();

g++ 3.4.6 de GCC produit la disposition de mémoire 32 bits suivante pour l'objet b2:

b2: +0 : pointeur vers la table de méthodes virtuelles de B2 +4 : valeur de int_in_b2 table de méthode virtuelle de B2 : +0 : B2::f2() 

et la disposition de mémoire suivante pour l'objetd :

d: +0 : pointeur vers la table des méthodes virtuelles de D (pour B1) +4 : valeur de int_in_b1 +8 : pointeur vers la table des méthodes virtuelles de D (pour B2) +12 : valeur de int_in_b2 +16 : valeur de int_in_d Taille totale : 20 octets. table de méthodes virtuelles de D (pour B1) : +0 : B1::f1() // B1::f1() n'est pas remplacé table de méthodes virtuelles de D (pour B2) : +0 : D::f2() // B2::f2() est remplacé par D::f2() // L'emplacement de B2::f2 n'est pas dans la table des méthodes virtuelles pour D 

Notez que les fonctions qui ne contiennent pas le mot clé virtualdans leur déclaration (comme fnonvirtual()et d()) n'apparaissent généralement pas dans la table des méthodes virtuelles. Il existe des exceptions pour les cas particuliers posés par le constructeur par défaut .

Notez également les destructeurs virtuels dans les classes de base B1et B2. Ils sont nécessaires pour garantir delete dla libération de mémoire non seulement pour D, mais aussi pour B1et B2, si dest un pointeur ou une référence aux types B1ou B2. Ils ont été exclus des dispositions de mémoire pour garder l'exemple simple.

Le remplacement de la méthode f2() dans la classe Dest implémenté en dupliquant la table des méthodes virtuelles de B2et en remplaçant le pointeur vers B2::f2()par un pointeur vers D::f2().

Le compilateur g++ implémente l' héritage multiple des classes B1et B2de la classe Den utilisant deux tables de méthodes virtuelles, une pour chaque classe de base. (Il existe d'autres façons d'implémenter l'héritage multiple, mais c'est la plus courante.) Cela conduit à la nécessité de « corrections de pointeurs », également appelées thunks , lors du casting .

Considérez le code C++ suivant :

D * d = nouveau D (); B1 * b1 = d ; B2 * b2 = d ;

Tandis que det b1pointeront vers le même emplacement mémoire après l'exécution de ce code, b2pointeront vers l'emplacement d+8(huit octets au-delà de l'emplacement mémoire de d). Ainsi, b2pointe vers la région à l'intérieur dqui « ressemble » à une instance de B2, c'est-à-dire qui a la même disposition de mémoire qu'une instance de B2.

Un appel à d->f1()est géré en déréférençant le vpointer dde D::B1, en recherchant l' f1entrée dans la table des méthodes virtuelles, puis en déréférençant ce pointeur pour appeler le code.

Héritage unique

Dans le cas d'un héritage simple (ou dans un langage avec un seul héritage), si le vpointer est toujours le premier élément d(comme c'est le cas avec de nombreux compilateurs), cela se réduit au pseudo-C++ suivant :

( * (( * d )[ 0 ]))( d )

Où *dfait référence à la table des méthodes virtuelles de Det [0]fait référence à la première méthode dans la table des méthodes virtuelles. Le paramètre ddevient le pointeur "this " vers l'objet.

Héritage multiple

Dans le cas le plus général, appeler B1::f1()ou D::f2()est plus compliqué :

( * ( * ( d [ 0 ] /*pointeur vers la table des méthodes virtuelles de D (pour B1)*/ )[ 0 ]))( d ) /* Appel d->f1() */ ( * ( * ( d [ 8 ] /*pointeur vers la table des méthodes virtuelles de D (pour B2)*/ )[ 0 ]))( d + 8 ) /* Appel d->f2() */

L'appel à d->f1()passe un B1pointeur comme paramètre. L'appel à d->f2()passe un B2pointeur comme paramètre. Ce deuxième appel nécessite une correction pour produire le pointeur correct. L'emplacement de B2::f2n'est pas dans la table des méthodes virtuelles pour D.

En comparaison, un appel à d->fnonvirtual()est beaucoup plus simple :

( * B1 :: fnonvirtual )( d )

Un appel virtuel nécessite au moins une déréférence indexée supplémentaire et parfois un ajout de « correction », par rapport à un appel non virtuel, qui est simplement un saut vers un pointeur compilé. Par conséquent, l'appel de fonctions virtuelles est intrinsèquement plus lent que l'appel de fonctions non virtuelles. Une expérience réalisée en 1996 indique qu'environ 6 à 13 % du temps d'exécution est consacré simplement à la répartition vers la fonction correcte, bien que la surcharge puisse atteindre 50 %. Le coût des fonctions virtuelles peut ne pas être aussi élevé sur les architectures CPU modernes en raison de caches beaucoup plus volumineux et d'une meilleure prédiction des branches .

De plus, dans les environnements où la compilation JIT n'est pas utilisée, les appels de fonctions virtuelles ne peuvent généralement pas être intégrés . Dans certains cas, il peut être possible pour le compilateur d'effectuer un processus connu sous le nom de dévirtualisation dans lequel, par exemple, la recherche et l'appel indirect sont remplacés par une exécution conditionnelle de chaque corps intégré, mais de telles optimisations ne sont pas courantes.

Pour éviter cette surcharge, les compilateurs évitent généralement d'utiliser des tables de méthodes virtuelles chaque fois que l'appel peut être résolu au moment de la compilation .

Ainsi, l'appel à f1ci-dessus peut ne pas nécessiter de recherche de table car le compilateur peut être en mesure de dire que dne peut contenir qu'un Dà ce stade et Dne remplace pas f1. Ou le compilateur (ou l'optimiseur) peut être en mesure de détecter qu'il n'y a aucune sous-classe de B1n'importe où dans le programme qui remplace f1. L'appel à B1::f1ou B2::f2ne nécessitera probablement pas de recherche de table car l'implémentation est spécifiée explicitement (bien qu'elle nécessite toujours la correction du pointeur 'this').

La table de méthodes virtuelles est généralement un bon compromis de performances pour obtenir une répartition dynamique, mais il existe des alternatives, telles que la répartition par arbre binaire, avec des performances plus élevées dans certains cas typiques, mais des compromis différents.

Cependant, les tables de méthodes virtuelles ne permettent qu'une seule répartition sur le paramètre spécial « this », contrairement à la répartition multiple (comme dans CLOS , Dylan ou Julia ), où les types de tous les paramètres peuvent être pris en compte dans la répartition.

Les tables de méthodes virtuelles ne fonctionnent également que si la répartition est limitée à un ensemble connu de méthodes, de sorte qu'elles peuvent être placées dans un tableau simple construit au moment de la compilation, contrairement aux langages de typage canard (tels que Smalltalk , Python ou JavaScript ).

Les langages qui fournissent l'une ou l'autre de ces fonctionnalités, ou les deux, effectuent souvent une recherche en recherchant une chaîne dans une table de hachage ou une autre méthode équivalente. Il existe diverses techniques pour accélérer cette opération (par exemple, l'internalisation /la tokenisation des noms de méthodes, la mise en cache des recherches, la compilation juste à temps ).