Implémentation de classes et d'interfaces pures abstraites

27

Bien que cela ne soit pas obligatoire dans la norme C ++, il semble que la façon dont GCC implémente les classes parentes, y compris les classes abstraites pures, consiste à inclure un pointeur vers la table v pour cette classe abstraite à chaque instanciation de la classe en question .

Naturellement, cela gonfle la taille de chaque instance de cette classe par un pointeur pour chaque classe parente qu'elle possède.

Mais j'ai remarqué que de nombreuses classes et structures C # ont beaucoup d'interfaces parent, qui sont essentiellement des classes abstraites pures. Je serais surpris si chaque instance de say Decimal, était gonflée de 6 pointeurs vers toutes ses différentes interfaces.

Donc, si C # fait les interfaces différemment, comment les fait-il, au moins dans une implémentation typique (je comprends que la norme elle-même ne définit pas une telle implémentation)? Et les implémentations C ++ ont-elles un moyen d'éviter le gonflement de la taille de l'objet lors de l'ajout de parents virtuels purs aux classes?

Clinton
la source
1
Les objets C # ont généralement beaucoup de métadonnées attachées, peut-être que les vtables ne sont pas si gros par rapport à cela
max630
vous pouvez commencer par examiner le code compilé avec le désassembleur
idl
Le C ++ fait une fraction significative de ses "interfaces" statiquement. Comparer ICompareràCompare
Caleth
4
GCC, par exemple, utilise un pointeur de table vtable (un pointeur vers une table de vtables ou un VTT) par objet pour les classes avec plusieurs classes de base. Ainsi, chaque objet n'a qu'un seul pointeur supplémentaire plutôt que la collection que vous imaginez. Peut-être que cela signifie en pratique que ce n'est pas un problème même lorsque le code est mal conçu et qu'il y a une hiérarchie de classes massive impliquée.
Stephen M. Webb
1
@ StephenM.Webb D'après ce que j'ai compris de cette réponse SO , les VTT ne sont utilisés que pour commander la construction / destruction avec héritage virtuel. Ils ne participent pas à la répartition des méthodes et ne finissent pas par économiser de l'espace dans l'objet lui-même. Étant donné que les upcasts C ++ effectuent efficacement le découpage d'objets, il n'est pas possible de placer le pointeur vtable ailleurs que dans l'objet (qui pour MI ajoute des pointeurs vtable au milieu de l'objet). J'ai vérifié en regardant la g++-7 -fdump-class-hierarchysortie.
amon

Réponses:

35

Dans les implémentations C # et Java, les objets ont généralement un seul pointeur vers sa classe. Cela est possible car ce sont des langages à héritage unique. La structure de classe contient alors la table virtuelle pour la hiérarchie à héritage unique. Mais appeler des méthodes d'interface a également tous les problèmes d'héritage multiple. Ceci est généralement résolu en plaçant des vtables supplémentaires pour toutes les interfaces implémentées dans la structure de classe. Cela économise de l'espace par rapport aux implémentations d'héritage virtuel typiques en C ++, mais rend la répartition des méthodes d'interface plus compliquée - qui peut être partiellement compensée par la mise en cache.

Par exemple, dans la JVM OpenJDK, chaque classe contient un tableau de vtables pour toutes les interfaces implémentées (une interface vtable est appelée un itable ). Lorsqu'une méthode d'interface est appelée, ce tableau recherche linéairement l'itable de cette interface, puis la méthode peut être distribuée via cet itable. La mise en cache est utilisée pour que chaque site d'appel se souvienne du résultat de l'envoi de la méthode, de sorte que cette recherche ne doit être répétée que lorsque le type d'objet concret change. Pseudocode pour l'envoi de méthode:

// Dispatch SomeInterface.method
Method const* resolve_method(
    Object const* instance, Klass const* interface, uint itable_slot) {

  Klass const* klass = instance->klass;

  for (Itable const* itable : klass->itables()) {
    if (itable->klass() == interface)
      return itable[itable_slot];
  }

  throw ...;  // class does not implement required interface
}

(Comparez le vrai code dans l' interpréteur OpenJDK HotSpot ou le compilateur x86 .)

C # (ou plus précisément, le CLR) utilise une approche connexe. Cependant, ici les itables ne contiennent pas de pointeurs vers les méthodes, mais sont des mappages de slots: ils pointent vers des entrées dans la table principale de la classe. Comme pour Java, la recherche de l'itable correct n'est que le pire des cas, et il est prévu que la mise en cache sur le site d'appel puisse éviter cette recherche presque toujours. Le CLR utilise une technique appelée Virtual Stub Dispatch afin de patcher le code machine compilé JIT avec différentes stratégies de mise en cache. Pseudocode:

Method const* resolve_method(
    Object const* instance, Klass const* interface, uint interface_slot) {

  Klass const* klass = instance->klass;

  // Walk all base classes to find slot map
  for (Klass const* base = klass; base != nullptr; base = base->base()) {
    // I think the CLR actually uses hash tables instead of a linear search
    for (SlotMap const* slot_map : base->slot_maps()) {
      if (slot_map->klass() == interface) {
        uint vtable_slot = slot_map[interface_slot];
        return klass->vtable[vtable_slot];
      }
    }
  }

  throw ...;  // class does not implement required interface
}

La principale différence avec le pseudocode OpenJDK est que, dans OpenJDK, chaque classe possède un tableau de toutes les interfaces implémentées directement ou indirectement, tandis que le CLR ne conserve qu'un tableau de mappages d'emplacements pour les interfaces qui ont été directement implémentées dans cette classe. Nous devons donc remonter la hiérarchie d'héritage jusqu'à ce qu'une carte de slot soit trouvée. Pour les hiérarchies d'héritage profondes, cela se traduit par des économies d'espace. Celles-ci sont particulièrement pertinentes dans CLR en raison de la façon dont les génériques sont implémentés: pour une spécialisation générique, la structure de classe est copiée et les méthodes de la table principale peuvent être remplacées par des spécialisations. Les mappages d'emplacements continuent de pointer vers les entrées de table appropriées et peuvent donc être partagés entre toutes les spécialisations génériques d'une classe.

Pour finir, il existe plus de possibilités pour implémenter la répartition d'interface. Au lieu de placer le pointeur vtable / itable dans l'objet ou dans la structure de classe, nous pouvons utiliser de gros pointeurs vers l'objet, qui sont essentiellement une (Object*, VTable*)paire. L'inconvénient est que cela double la taille des pointeurs et que les upcasts (d'un type concret à un type d'interface) ne sont pas gratuits. Mais il est plus flexible, a moins d'indirection, et signifie également que les interfaces peuvent être implémentées en externe à partir d'une classe. Les approches associées sont utilisées par les interfaces Go, les caractères Rust et les classes de types Haskell.

Références et lectures complémentaires:

  • Wikipédia: mise en cache en ligne . Discute des approches de mise en cache qui peuvent être utilisées pour éviter une recherche de méthode coûteuse. Généralement non nécessaire pour la répartition basée sur vtable, mais très souhaitable pour les mécanismes de répartition plus coûteux comme les stratégies de répartition d'interface ci-dessus.
  • OpenJDK Wiki (2013): Appels d'interface . Discute des objets utilisables.
  • Pobar, Neward (2009): SSCLI 2.0 Internals. Le chapitre 5 du livre traite en détail des cartes des emplacements. N'a jamais été publié mais mis à disposition par les auteurs sur leurs blogs . Le lien PDF a depuis déménagé. Ce livre ne reflète probablement plus l'état actuel du CLR.
  • CoreCLR (2006): Virtual Stub Dispatch . Dans: Book Of The Runtime. Discute des cartes d'emplacements et de la mise en cache pour éviter les recherches coûteuses.
  • Kennedy, Syme (2001): Design and Implementation of Generics for the .NET Common Language Runtime . ( Lien PDF ). Discute de diverses approches pour implémenter des génériques. Les génériques interagissent avec la répartition des méthodes car les méthodes peuvent être spécialisées et les vtables doivent donc être réécrites.
amon
la source
Merci @amon une excellente réponse dans l'attente des détails supplémentaires sur la façon dont Java et le CLR y parviennent!
Clinton
@Clinton J'ai mis à jour le message avec quelques références. Vous pouvez également lire le code source des machines virtuelles, mais j'ai eu du mal à suivre. Mes références sont un peu anciennes, si vous trouvez quelque chose de nouveau je serais très intéressé. Cette réponse est essentiellement un extrait de notes que j'avais couché dans un billet de blog, mais je n'eu le temps de le publier: /
amon
1
callvirtAKA CEE_CALLVIRTdans CoreCLR est l'instruction CIL qui gère les méthodes d'interface d'appel, si quelqu'un veut en savoir plus sur la façon dont le runtime gère cette configuration.
2018
Notez que l' callopcode est utilisé pour les staticméthodes, il callvirtest intéressant de l' utiliser même si la classe l'est sealed.
2018
1
Re: "Les objets [C #] ont généralement un seul pointeur vers sa classe ... parce que [C # est un] langage à héritage unique." Même en C ++, avec tout son potentiel pour des sites Web complexes de types à héritage multiple, vous ne pouvez toujours spécifier qu'un type au point où votre programme crée une nouvelle instance. Il devrait être possible, en théorie, de concevoir un compilateur C ++ et une bibliothèque de prise en charge au moment de l'exécution de sorte qu'aucune instance de classe ne transporte jamais plus d'un pointeur de RTTI.
Solomon Slow
2

Naturellement, cela gonfle la taille de chaque instance de cette classe par un pointeur pour chaque classe parente qu'elle possède.

Si par «classe parent» vous voulez dire «classe de base», ce n'est pas le cas dans gcc (et je ne m'attends à aucun autre compilateur).

Dans le cas de C dérive de B dérive de A où A est une classe polymorphe, l'instance C aura exactement une vtable.

Le compilateur dispose de toutes les informations dont il a besoin pour fusionner les données de la table V de A en B et de B en C.

Voici un exemple: https://godbolt.org/g/sfdtNh

Vous verrez qu'il n'y a qu'une seule initialisation d'une table virtuelle.

J'ai copié la sortie de l'assembly pour la fonction principale ici avec des annotations:

main:
        push    rbx

# allocate space for a C on the stack
        sub     rsp, 16

# initialise c's vtable (note: only one)
        mov     QWORD PTR [rsp+8], OFFSET FLAT:vtable for C+16

# use c    
        lea     rdi, [rsp+8]
        call    do_something(C&)

# destruction sequence through virtual destructor
        mov     QWORD PTR [rsp+8], OFFSET FLAT:vtable for B+16
        lea     rdi, [rsp+8]
        call    A::~A() [base object destructor]

        add     rsp, 16
        xor     eax, eax
        pop     rbx
        ret
        mov     rbx, rax
        jmp     .L10

Source complète pour référence:

struct A
{
    virtual void foo() = 0;
    virtual ~A();
};

struct B : A {};

struct C : B {

    virtual void extrafoo()
    {
    }

    void foo() override {
        extrafoo();
    }

};

int main()
{
    extern void do_something(C&);
    auto c = C();
    do_something(c);
}
Richard Hodges
la source
Si nous prenons un exemple où la sous-classe hérite directement de deux classes de base comme class Derived : public FirstBase, public SecondBasealors il peut y avoir deux vtables. Vous pouvez exécuter g++ -fdump-class-hierarchypour voir la disposition de la classe (également affichée dans mon article de blog lié). Godbolt affiche alors un incrément de pointeur supplémentaire avant l'appel afin de sélectionner le 2ème vtable.
amon