Alternative virtuelle mécanisme implémentations?

Question

C++ prend en charge dynamique de la liaison par le biais de virtuel mécanisme. Mais ce que je comprends le virtuel mécanisme est un détail d'implémentation du compilateur et le standard spécifie les comportements de ce qui devrait se produire dans des scénarios spécifiques. La plupart des compilateurs de mettre en œuvre le virtuel mécanisme par le biais du virtuel tableau et pointeur virtuel. Et oui, je suis conscient de la façon dont cela fonctionne, Donc ma question n'est pas sur le détail de l'implémentation de virtuel pointeurs et de la table. Mes questions sont les suivantes:

1. Existe-il des compilateurs qui mettent en œuvre Virtuel Mécanisme de toute autre façon autre que le pointeur virtuel et virtuel tableau mécanisme? Comme ce que j'ai vu(lu g++,Microsoft visual studio) mettre en œuvre par le biais de table virtuelle, mécanisme de pointeur. Donc, pratiquement, il n'existe aucun autre compilateur implémentations?
2. L' sizeof de toute la classe d'une fonction virtuelle sera de la taille d'un pointeur (vptr à l'intérieur d' this) sur ce compilateur, Donc vu que virtuel ptr et tbl mécanisme lui-même est le compilateur de mise en œuvre de cette déclaration que j'ai faite ci-dessus sera toujours vrai?

Answer 1

Il n'est pas vrai que vtable des pointeurs sur les objets sont toujours les plus efficaces. Mon compilateur pour un autre langage utilisé pour utiliser des pointeurs d'objet pour des raisons similaires, mais ne le fait plus: au lieu de cela il utilise une structure de données qui mappe l'adresse d'objet à l'exigence de méta-données: dans mon système, cela arrive à être la forme de l'information pour une utilisation par le garbage collector.

Cette mise en œuvre coûte un peu plus de stockage pour une simple et unique objet, est plus efficace pour des objets complexes avec de nombreuses bases, et il est largement plus efficace pour les tableaux, étant donné qu'une seule entrée est requis dans la table de correspondance pour tous les objets dans le tableau. Mon particulier la mise en œuvre trouverez également les méta-données d'un pointeur vers n'importe quel point de l'intérieur de l'objet.

La réelle recherche est extrêmement rapide, et les exigences de stockage très modeste, parce que je suis en utilisant les meilleures données de la structure de la planète: Judy tableaux.

Je connais aussi pas de compilateur C++ en utilisant rien d'autre que vtable des pointeurs, mais il n'est pas le seul moyen. En fait, l'initialisation de la sémantique pour les classes avec des bases faire toute la mise en œuvre désordonnée. C'est parce que l'complet de type a à voir-vu autour de l'objet est construit. En conséquence de ces sémantique, complexe mixin objets conduire à des ensembles de vtables généré de grands objets, et de ralentir l'initialisation des objets. Ce n'est probablement pas une conséquence de la vtable technique autant que la nécessité de suivre servilement la condition que le type à l'exécution d'un sous-objet l'être à tous les temps. En fait il n'y a aucune bonne raison à cela lors de la construction, puisque les constructeurs ne sont pas des méthodes et ne peut pas raisonnablement utiliser virtual expédition: ce n'est pas clair pour moi pour la destruction depuis les destructeurs sont de véritables méthodes.

Answer 2

À ma connaissance, tous les C++ implémentations utilisent une vtable pointeur, bien qu'il serait assez facile (et peut-être pas si mauvaise perf sage que vous pourriez le penser compte tenu de caches) de garder un petit type-index de l'objet (1-2 B) et par la suite obtenir la vtable et des informations de type avec une petite table de recherche.

Une autre approche intéressante, peut-être BIBOP (http://foldoc.org/BIBOP) -- grand sac de pages-bien qu'il aurait des problèmes pour le C++. Idée: mettre des objets de même type sur une page. Obtenir un pointeur vers le descripteur de type / vtable en haut de la page, simplement et avec hors les moins importants bits du pointeur d'objet. (Ne fonctionne pas bien pour les objets sur la pile, bien sûr!)

Une autre approche est de coder certaines balises de type/indices dans les pointeurs d'objet eux-mêmes. Par exemple, si par construction, tous les objets sont de 16 octets alignés, vous pouvez utiliser les 4 Lsb de mettre un 4 bits type de balise. (Pas vraiment suffisant.) Ou (en particulier pour les systèmes embarqués) si vous avez la garantie inutilisés plus significatif-bits de l'adresse, vous pouvez mettre plus de bits de tag là-haut, et de les récupérer avec un décalage et un masque.

Bien que ces deux régimes sont intéressants (et parfois utilisé) pour les autres implémentations de langue, ils sont problématiques pour le C++. Certains C++ sémantique, comme la classe de base virtuelle de la fonction de surcharge sont appelés lors de l' (classe de base), construction de l'objet et de la destruction, de vous conduire à un modèle où il existe un certain état de l'objet que vous modifiez comme vous entrez dans la classe de base ctors/dtors.

Vous pouvez trouver mon vieux tutoriel sur le C++ de Microsoft modèle d'objet de la mise en œuvre intéressante. http://www.openrce.org/articles/files/jangrayhood.pdf

Happy hacking!

Answer 3

1. Je ne pense pas qu'il y a tout les compilateurs modernes avec une approche autre que vptr/vtable. En effet, il serait difficile de trouver quelque chose d'autre qui n'est pas tout simplement inefficace.

   Cependant, il y a encore une assez grande salle pour la conception des compromis au sein de cette approche. Peut-être surtout concernant la façon dont l'héritage virtuel est manipulé. Il est donc logique de faire de cette mise en œuvre définies.

   Si vous êtes intéressé par ce genre de trucs, je vous suggère fortement la lecture à l'Intérieur de l'Objet C++ Modèle.

2. sizeof class dépend du compilateur. Si vous voulez un code portable, ne faites pas de suppositions.

Answer 4

Existe-il des compilateurs qui mettent en œuvre Virtuel Mécanisme de toute autre façon autre que le pointeur virtuel et virtuel tableau mécanisme? Comme ce que j'ai vu(lu g++,Microsoft visual studio) mettre en œuvre par le biais de table virtuelle, mécanisme de pointeur. Donc, pratiquement, il n'existe aucun autre compilateur implémentations?

Tous les compilateurs que je sais de l'utilisation de la vtable mécanisme.

C'est une optimisation qui est possible parce que le C++ est statiquement type cochée.

Dans certains plus dynamique des langues, il s'agit plutôt d'une dynamique de recherche de la classe de base de la chaîne(s), à la recherche d'une mise en œuvre d'une fonction membre appelée pratiquement, à partir de la plupart des dérivés de la classe de l'objet. Par exemple, c'est la façon dont il a travaillé dans l'original Smalltalk. Et le C++ standard décrit l'effet d'un appel virtuel comme si cette recherche avait été utilisée.

En Borland/Turbo Pascal dans les années 1990 ces dynamiques de recherche a été utilisé pour rechercher des gestionnaires de l'API Windows de la fenêtre "messages". Et je pense que peut-être le même en Borland C++. Il a été, en plus de la normale de la vtable mécanisme, utilisé uniquement pour les gestionnaires de messages.

Si elle a été utilisée dans Borland/Turbo C++ – je ne me souviens pas – alors qu'il était en faveur d'une des extensions de langage que vous a permis d'associer l'id de message avec le message des fonctions de gestionnaire.

Le sizeof de toute la classe d'une fonction virtuelle sera de la taille d'un pointeur(vptr à l'intérieur de la ce) sur ce compilateur, Donc vu que virtuel ptr et tbl mécanisme lui-même est le compilateur de mise en œuvre de cette déclaration que j'ai faite ci-dessus sera toujours vrai?

Officiellement pas (même avec une hypothèse de vtable mécanisme), il dépend du compilateur. Puisque la norme n'exige pas la vtable mécanisme, il ne dit rien sur le placement de la vtable pointeur dans chaque objet. Et d'autres règles de laisser le compilateur librement ajouter rembourrage, les octets non utilisés à la fin.

Mais, dans la pratique, peut-être. ;-)

Cependant, il n'est pas quelque chose que vous devez compter sur un, ou que vous avez besoin de s'appuyer sur. Mais dans l'autre sens, vous pouvez exiger ce, par exemple, si vous êtes à la définition de l'ABI. Puis un compilateur qui ne l'est pas, tout simplement n'est pas conforme à vos besoins.

Cheers & hth.,

Answer 5

En essayant d'imaginer un autre régime, j'en suis venu avec le suivant, le long de la lignes de Yttril de réponse. Autant que je sache, aucun compilateur utilise!

Étant donné un nombre suffisamment important de l'espace d'adressage virtuel et un système d'exploitation flexible d'allocation de mémoire routines, il serait possible pour new d'allouer des objets de types différents dans le fixe, le non-cumul des plages d'adresses. Ensuite, le type d'un objet peut être déduit rapidement à partir de son adresse à l'aide d'un décalage vers la droite de l'opération, et le résultat est utilisé pour indexer un tableau de vtables, donc une économie de 1 vtable pointeur par objet.

À première vue, cela pourrait sembler à rencontrer des problèmes avec pile d'objets alloué, mais cela peut être manipulé proprement:

1. Pour chaque pile objet alloué, le compilateur ajoute le code qui ajoute un enregistrement à un réseau mondial de (address range, type) paires lorsque l'objet est créé et supprime l'enregistrement lorsqu'il est détruit.
2. La plage d'adresses comprenant la pile de la carte à une seule vtable contenant un grand nombre de thunks lire l' this pointeur, analyse le tableau pour trouver le type correspondant (vptr) pour l'objet à cette adresse, et d'appeler la méthode correspondante dans la vtable souligné. (I. e. la 42e thunk fera appel à la 42e de la méthode dans la vtable -- si la plupart des fonctions virtuelles utilisées dans n'importe quelle classe est - n, alors au moins n thunks sont nécessaires.)

Ce schéma évidemment engage non négligeable, les frais généraux (au moins O(log n) pour la recherche) virtuel pour les appels de méthode sur la pile de base des objets. En l'absence de tableaux ou de la composition (confinement à l'intérieur d'un autre objet) de la pile d'objets, plus simple et plus rapide approche peut être utilisée dans lesquels le vptr est placé sur la pile immédiatement avant que l'objet (notez qu'il n'est pas considéré comme faisant partie de l'objet et de ne pas contribuer à sa taille mesurée en sizeof). Dans ce cas, les thunks il suffit de soustraire sizeof (vptr) de this pour trouver la bonne vptr à utiliser, et comme avant.