Implementierung von reinen abstrakten Klassen und Interfaces

27

Obwohl dies im C ++ - Standard nicht vorgeschrieben ist, sieht es so aus, als ob GCC beispielsweise übergeordnete Klassen, einschließlich rein abstrakter Klassen, implementiert, indem es in jeder Instanziierung der betreffenden Klasse einen Zeiger auf die v-Tabelle für diese abstrakte Klasse einfügt .

Dies erhöht natürlich die Größe jeder Instanz dieser Klasse um einen Zeiger für jede übergeordnete Klasse.

Aber ich habe bemerkt, dass viele C # -Klassen und -Strukturen viele übergeordnete Schnittstellen haben, die im Grunde genommen reine abstrakte Klassen sind. Es würde mich wundern, wenn jede Instanz von say Decimalmit 6 Zeigern auf die verschiedenen Schnittstellen aufgebläht wäre.

Also, wenn C # Schnittstellen anders macht, wie macht es diese, zumindest in einer typischen Implementierung (ich verstehe, dass der Standard selbst eine solche Implementierung möglicherweise nicht definiert)? Und haben irgendwelche C ++ - Implementierungen eine Möglichkeit, das Aufblähen der Objektgröße zu vermeiden, wenn Sie Klassen reine virtuelle Eltern hinzufügen?

Clinton
quelle
1
C # -Objekte haben normalerweise ziemlich viele Metadaten, vielleicht sind die vtables nicht so groß im Vergleich dazu
max630
Sie könnten mit der Prüfung des kompilierten Codes mit dem IDL-Disassembler beginnen
max630
C ++ macht einen erheblichen Teil seiner "Schnittstellen" statisch. Vergleichen Sie IComparermitCompare
Caleth
4
GCC verwendet beispielsweise einen vtable-Tabellenzeiger (einen Zeiger auf eine Tabelle mit vtables oder eine VTT) pro Objekt für Klassen mit mehreren Basisklassen. Daher verfügt jedes Objekt nur über einen zusätzlichen Zeiger und nicht über die Sammlung, die Sie sich vorstellen. Vielleicht bedeutet dies, dass es in der Praxis kein Problem ist, selbst wenn der Code schlecht gestaltet ist und eine massive Klassenhierarchie vorliegt.
Stephen M. Webb
1
@ StephenM.Webb Soweit ich aus dieser SO-Antwort verstanden habe , werden VTTs nur zum Ordnen von Konstruktion / Zerstörung mit virtueller Vererbung verwendet. Sie nehmen nicht am Methodenversand teil und sparen am Ende keinen Platz im Objekt. Da C ++ - Upcasts das Aufteilen von Objekten effektiv durchführen, ist es nicht möglich, den vtable-Zeiger an einer anderen Stelle als im Objekt zu platzieren (bei MI werden vtable-Zeiger in der Mitte des Objekts hinzugefügt). Ich überprüfte, indem ich g++-7 -fdump-class-hierarchyAusgabe betrachtete.
Amon

Antworten:

35

In C # - und Java-Implementierungen haben die Objekte normalerweise einen einzelnen Zeiger auf ihre Klasse. Dies ist möglich, da es sich um Sprachen mit einfacher Vererbung handelt. Die Klassenstruktur enthält dann die vtable für die Einfachvererbungshierarchie. Der Aufruf von Interface-Methoden birgt jedoch auch alle Probleme der Mehrfachvererbung. Dies wird normalerweise gelöst, indem zusätzliche vtables für alle implementierten Schnittstellen in die Klassenstruktur eingefügt werden. Dies spart im Vergleich zu typischen virtuellen Vererbungsimplementierungen in C ++ Platz, erschwert jedoch den Versand von Schnittstellenmethoden - was teilweise durch Caching kompensiert werden kann.

In der OpenJDK-JVM enthält jede Klasse ein Array von vtables für alle implementierten Schnittstellen (eine Schnittstellen-vtable wird itable genannt ). Wenn eine Schnittstellenmethode aufgerufen wird, wird dieses Array linear nach der Itable dieser Schnittstelle durchsucht, und die Methode kann über diese Itable verteilt werden. Das Caching wird verwendet, damit sich jeder Aufrufstandort das Ergebnis des Methodenversands merkt, sodass diese Suche nur wiederholt werden muss, wenn sich der konkrete Objekttyp ändert. Pseudocode für den Methodenversand:

// 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
}

(Vergleichen Sie den tatsächlichen Code im OpenJDK HotSpot- Interpreter oder im x86-Compiler .)

C # (oder genauer gesagt die CLR) verwendet einen verwandten Ansatz. In diesem Fall enthalten die Tabellen jedoch keine Zeiger auf die Methoden, sondern sind Slotmaps: Sie verweisen auf Einträge in der Haupttabelle der Klasse. Wie bei Java ist die Suche nach der korrekten itable nur das Worst-Case-Szenario, und es wird erwartet, dass das Caching am Aufrufstandort diese Suche fast immer vermeiden kann. Die CLR verwendet eine Technik namens Virtual Stub Dispatch, um den JIT-kompilierten Maschinencode mit verschiedenen Caching-Strategien zu patchen. 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
}

Der Hauptunterschied zum OpenJDK-Pseudocode besteht darin, dass in OpenJDK jede Klasse ein Array aller direkt oder indirekt implementierten Schnittstellen enthält, während die CLR nur ein Array von Slotmaps für Schnittstellen enthält, die direkt in dieser Klasse implementiert wurden. Wir müssen daher die Vererbungshierarchie nach oben durchlaufen, bis eine Slot-Map gefunden wird. Bei Hierarchien mit tiefer Vererbung führt dies zu Platzeinsparungen. Diese sind in CLR aufgrund der Art und Weise, wie Generika implementiert werden, besonders relevant: Bei einer generischen Spezialisierung wird die Klassenstruktur kopiert und Methoden in der Haupttabelle können durch Spezialisierungen ersetzt werden. Die Slotmaps zeigen weiterhin auf die richtigen vtable-Einträge und können daher von allen allgemeinen Spezialisierungen einer Klasse gemeinsam genutzt werden.

Abschließend gibt es noch weitere Möglichkeiten, den Interface-Versand zu implementieren. Anstatt den Zeiger vtable / itable im Objekt oder in der Klassenstruktur zu platzieren, können wir fette Zeiger auf das Objekt verwenden, die im Grunde genommen ein (Object*, VTable*)Paar sind. Der Nachteil ist, dass dies die Größe von Zeigern verdoppelt und Upcasts (von einem konkreten Typ zu einem Schnittstellentyp) nicht frei sind. Aber es ist flexibler, hat weniger Indirektion und bedeutet auch, dass Interfaces außerhalb einer Klasse implementiert werden können. Verwandte Ansätze werden von Go-Interfaces, Rust-Merkmalen und Haskell-Typenklassen verwendet.

Referenzen und weiterführende Literatur:

  • Wikipedia: Inline-Caching . Erläutert Caching-Ansätze, mit denen teure Methodensuchen vermieden werden können. In der Regel nicht erforderlich für vtable-basierten Versand, aber sehr wünschenswert für teurere Versandmechanismen wie die obigen Schnittstellen-Versandstrategien.
  • OpenJDK Wiki (2013): Schnittstellenaufrufe . Bespricht itables.
  • Pobar, Neward (2009): SSCLI 2.0 Internals. In Kapitel 5 des Buches werden Slot-Maps sehr detailliert behandelt. Wurde nie veröffentlicht, sondern von den Autoren auf ihren Blogs zur Verfügung gestellt . Der PDF-Link ist inzwischen umgezogen. Dieses Buch spiegelt wahrscheinlich nicht mehr den aktuellen Stand der CLR wider.
  • CoreCLR (2006): Virtual Stub Dispatch . In: Buch der Laufzeit. Erläutert Slot Maps und Caching, um teure Lookups zu vermeiden.
  • Kennedy, Syme (2001): Design und Implementierung von Generics für die .NET Common Language Runtime . ( PDF-Link ). Erläutert verschiedene Ansätze zur Implementierung von Generika. Generics interagieren mit dem Methodenversand, da Methoden möglicherweise spezialisiert sind und vtables möglicherweise neu geschrieben werden müssen.
amon
quelle
Vielen Dank @amon tolle Antwort freuen uns auf die zusätzlichen Details, wie Java und die CLR dies erreichen!
Clinton
@Clinton Ich habe den Beitrag mit einigen Referenzen aktualisiert. Sie können auch den Quellcode der VMs lesen, aber ich fand es schwierig, zu folgen. Meine Referenzen sind ein bisschen alt, wenn Sie etwas Neueres finden, wäre ich sehr interessiert. Diese Antwort ist im Grunde genommen ein Auszug von Notizen, die ich für einen Blog-Beitrag gemacht habe, aber ich bin nie dazu gekommen, sie zu veröffentlichen: /
amon
1
callvirtAKA CEE_CALLVIRTin CoreCLR ist die CIL-Anweisung, die aufrufende Schnittstellenmethoden verarbeitet, wenn Sie mehr darüber erfahren möchten , wie die Laufzeitumgebung dieses Setup verarbeitet.
Jrh
Beachten Sie, dass der callOpcode für staticMethoden verwendet wird, interessanterweise callvirtauch, wenn die Klasse verwendet wird sealed.
jrh
1
Betreff: "[C #] -Objekte haben normalerweise einen einzelnen Zeiger auf ihre Klasse ... weil [C #] eine Sprache mit einfacher Vererbung ist." Sogar in C ++ mit all dem Potenzial für komplexe Webs mit mehrfach vererbten Typen können Sie immer noch nur einen Typ an dem Punkt angeben, an dem Ihr Programm eine neue Instanz erstellt. Theoretisch sollte es möglich sein, einen C ++ - Compiler und eine Laufzeit-Unterstützungsbibliothek so zu entwerfen, dass keine Klasseninstanz mehr als einen Zeigerwert von RTTI enthält.
Solomon Slow
2

Dies erhöht natürlich die Größe jeder Instanz dieser Klasse um einen Zeiger für jede übergeordnete Klasse.

Wenn mit "Elternklasse" "Basisklasse" gemeint ist, dann ist dies in gcc nicht der Fall (was ich auch in keinem anderen Compiler erwarte).

Wenn C von B abgeleitet ist und A eine polymorphe Klasse ist, hat die C-Instanz genau eine vtable.

Der Compiler verfügt über alle Informationen, die zum Zusammenführen der Daten in der V-Tabelle von A mit den Daten von B und von B mit den Daten von C erforderlich sind.

Hier ist ein Beispiel: https://godbolt.org/g/sfdtNh

Sie werden sehen, dass es nur eine Initialisierung einer vtable gibt.

Ich habe die Assembly-Ausgabe für die Hauptfunktion hier mit Anmerkungen kopiert:

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

Komplette Quelle als Referenz:

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
quelle
Nehmen wir ein Beispiel, in dem die Unterklasse direkt von zwei Basisklassen wie erbt,class Derived : public FirstBase, public SecondBase dann kann es zwei vtables geben. Sie können ausführen g++ -fdump-class-hierarchy, um das Klassenlayout zu sehen (auch in meinem verknüpften Blog-Beitrag gezeigt). Godbolt zeigt dann vor dem Aufruf ein zusätzliches Zeigerinkrement an, um die 2. V-Tabelle auszuwählen.
Amon