Alternative Schemata zur Implementierung von vptr?

Question

Diese Frage bezieht sich nicht auf die C++ - Sprache selbst (dh nicht auf den Standard), sondern darauf, wie ein Compiler aufgerufen wird, um alternative Schemata für virtuelle Funktionen zu implementieren.

Das allgemeine Schema zum Implementieren virtueller Funktionen verwendet einen Zeiger auf eine Tabelle von Zeigern.

class Base { 
    private: 
     int m; 
    public: 
     virtual metha(); 
}; 

äquivalent in sagen würde C so etwas wie

struct Base { 
    void (**vtable)(); 
    int m; 
} 

das erste Element in der Regel ein Zeiger auf eine Liste der virtuellen Funktionen usw. (ein Stück Bereich im Speicher, die die Anwendung hat keine Kontrolle über). Und in den meisten Fällen kostet dies die Größe eines Zeigers, bevor man die Member usw. berücksichtigt. Also in einem 32-Bit-Adressierungsschema um 4 Bytes usw. Wenn Sie eine Liste von 40.000 polymorphen Objekten in Ihren Anwendungen erstellt haben, sind dies etwa 40.000 4 Bytes = 160k Bytes vor irgendwelchen Mitgliedsvariablen usw. Ich weiß auch, dass dies die schnellste und gebräuchlichste Implementierung unter C++ - Kompilierungen ist.

Ich weiß, dass dies durch Mehrfachvererbung (besonders mit virtuellen Klassen in ihnen, dh Diamant-Struktur, usw.) kompliziert ist.

Eine alternative Möglichkeit, das gleiche zu tun, ist die erste Variable als Index-ID auf eine Tabelle von vptrs (äquivalent in C wie unten)

struct Base { 
    char classid;  // the classid here is an index into an array of vtables 
    int  m; 
} 

die Gesamtzahl der Klassen in einer Anwendung, die bis haben, ist weniger als 255 (einschließlich aller möglichen Template-Instanziierungen, usw.), dann ist ein char gut genug, um einen Index zu halten, wodurch die Größe aller polymorphen Klassen in der Anwendung reduziert wird (Ich schließe Ausrichtungsprobleme usw. aus).

Meine Fragen ist, gibt es irgendeinen Schalter in GNU C++, LLVM oder irgendeinem anderen Compiler, um dies zu tun ?? oder reduzieren Sie die Größe von polymorphen Objekten?

Bearbeiten: Ich verstehe über die Ausrichtung Probleme hingewiesen. Auch ein weiterer Punkt, wenn dies in einem 64-Bit-System (unter der Annahme von 64 Bit vptr) mit jedem polymorphen Objektelement, das ungefähr 8 Byte kostet, ist, dann betragen die Kosten von vptr 50% des Speichers. Dies bezieht sich hauptsächlich auf kleine Polymorphe, die in Masse erzeugt werden, also frage ich mich, ob dieses Schema für zumindest bestimmte virtuelle Objekte möglich ist, wenn nicht die gesamte Anwendung.

Answer 1

Sie sind Vorschlag ist interessant, aber es wird nicht funktionieren, wenn die ausführbare Datei aus mehreren Modulen besteht, Objekte zwischen ihnen übergeben. Wenn sie einzeln kompiliert werden (zB DLLs), wenn ein Modul ein Objekt erstellt und es an ein anderes weitergibt und das andere eine virtuelle Methode aufruft - woher soll es wissen, auf welche Tabelle sich die classid bezieht? Sie können keine weitere moduleid hinzufügen, da die beiden Module sich möglicherweise nicht kennen, wenn sie kompiliert werden. Also, wenn Sie Zeiger verwenden, ich denke, es ist eine Sackgasse ...

Answer 2

Ein paar Beobachtungen:

1. Ja, ein kleinerer Wert verwendet werden könnte, um die Klasse zu vertreten, aber einige Prozessoren benötigen Daten zu so ausgerichtet sein, dass Platzeinsparungen durch die Anforderung zum Ausrichten von Datenwerten auf z 4 Byte Grenzen. Außerdem muss sich die Klassen-ID für alle Mitglieder eines polymorphen Vererbungsbaums an einer gut definierten Stelle befinden, so dass sie wahrscheinlich einem anderen Datum voraus ist, so dass Ausrichtungsprobleme nicht vermieden werden können.

2. Die Kosten für die Speicherung des Zeigers wurden in den Code verschoben, wo jede Verwendung einer polymorphen Funktion Code erfordert, um die Klassen-ID in einen Vtable-Zeiger oder eine äquivalente Datenstruktur zu übersetzen. Es ist also nicht umsonst. Offensichtlich hängt der Kosten-Trade-Off vom Volumen des Codes gegenüber der Anzahl der Objekte ab.

3. Wenn Objekte aus dem Heap zugewiesen werden, wird normalerweise in orer Raum verschwendet, um sicherzustellen, dass Objekte an der schlechtesten Grenze erkannt werden. Selbst wenn es nur wenig Code und eine große Anzahl polymorpher Objekte gibt Speicherverwaltungsaufwand migh ist wesentlich größer als der Unterschied zwischen einem Zeiger und einem Zeichen.

4. Damit Programme unabhängig kompiliert werden können, muss die Anzahl der Klassen im gesamten Programm und damit die Größe der Klassen-ID zum Zeitpunkt der Kompilierung bekannt sein, sonst kann der Code nicht kompiliert werden . Dies wäre ein erheblicher Aufwand. Es ist einfacher, es für den schlimmsten Fall zu reparieren und das Kompilieren und Verknüpfen zu vereinfachen.

Bitte lassen Sie mich nicht aufhören zu versuchen, aber es gibt sehr viel mehr Probleme mit jeder Technik zu lösen, die eine variable Größe ID verwenden können, um die Funktion Adresse abzuleiten. Es braucht eigentlich einen anderen Ansatz

Ich würde Ihnen dringend ermutigen, bei Wikipedia Cola

bei Ian Piumarta's Cola auch zu schauen, und verwendet den Zeiger in einer viel flexibleren Art und Weise, um Vererbung zu bauen, oder Prototyp-basierte oder eine beliebige anderer Mechanismus, den der Entwickler benötigt.

Answer 3

Die kurze Antwort ist, dass nein, ich kenne keinen Schalter, um dies mit jedem gängigen C++ - Compiler zu tun. Die längere Antwort lautet, dass Sie dazu den Großteil der Intelligenz in den Linker einbauen müssen, damit er die Verteilung der IDs über alle miteinander verknüpften Objektdateien koordinieren kann.

Ich würde auch darauf hinweisen, dass es im Allgemeinen nicht viel Gutes tun würde. Zumindest in einem typischen Fall möchten Sie jedes Element in einer Struktur/Klasse an einer "natürlichen" Grenze haben, was bedeutet, dass seine Startadresse ein Vielfaches seiner Größe ist. Wenn Sie Ihr Beispiel einer Klasse verwenden, die ein einzelnes int enthält, würde der Compiler ein Byte für den vtable-Index zuweisen, unmittelbar gefolgt von drei Byes of Padding, so dass das nächste int bei einer Adresse landet, die ein Vielfaches von vier ist. Das Endergebnis wäre, dass Objekte der Klasse genau die gleiche Menge an Speicherplatz belegen würden, als würden wir einen Zeiger verwenden.

Ich würde hinzufügen, dass dies auch keine weit hergeholte Ausnahme ist. Seit Jahren besteht der Standardratschlag zum Minimieren der in Strukturen/Klassen eingefügten Auffüllung darin, die erwarteten Elemente zu Beginn am größten und zum kleinsten zu entwickeln. Das heißt, in meisten Code, würden Sie mit den gleichen drei Bytes Padding vor dem ersten explizit definierten Mitglied der Struktur enden.

Um etwas Gutes daraus zu machen, müssen Sie sich dessen bewusst sein und eine Struktur mit (zum Beispiel) drei Bytes an Daten haben, die Sie verschieben könnten, wo Sie wollten. Dann würden Sie diese als die ersten explizit in der Struktur definierten Elemente verschieben. Leider würde das auch bedeuten, dass Sie, wenn Sie diesen Schalter ausschalten, so dass Sie einen Vtable-Pointer haben, den Compiler mit Padding ausstatten würden, der ansonsten unnötig wäre.

Zusammengefasst: Es ist nicht implementiert, und wenn es war, würde normalerweise nicht viel erreichen.

Answer 4

Nein, es gibt keinen solchen Schalter.

Die LLVM/Clang Codebasis vermeidet virtuelle Tabellen in Klassen, die von den Zehntausenden zugeordnet sind: diese Arbeit gut in ein Hierachie geschlossen, weil ein einzelner enum alle möglichen Klassen aufzählen kann, und dann wird jede Klasse ein verknüpftes Wert der enum. Die geschlossen ist offensichtlich wegen der enum.

Dann wird Virtualität durch eine switch auf der enum und entsprechende Casting vor dem Aufruf der Methode implementiert. Nochmals, geschlossen. Die switch muss für jede neue Klasse geändert werden.

---

Eine erste Alternative: externer vpointer.

Wenn Sie sich in einer Situation befinden, in der die vpointer-Steuer viel zu oft bezahlt wird, sind die meisten Objekte bekannter Art. Dann können Sie es externalisieren.

class Interface { 
public: 
    virtual ~Interface() {} 

    virtual Interface* clone() const = 0; // might be worth it 

    virtual void updateCount(int) = 0; 

protected: 
    Interface(Interface const&) {} 
    Interface& operator=(Interface const&) { return *this; } 
}; 

template <typename T> 
class InterfaceBridge: public Interface { 
public: 
    InterfaceBridge(T& t): t(t) {} 

    virtual InterfaceBridge* clone() const { return new InterfaceBridge(*this); } 

    virtual void updateCount(int i) { t.updateCount(i); } 

private: 
    T& t; // value or reference ? Choose... 
}; 

template <typename T> 
InterfaceBridge<T> interface(T& t) { return InterfaceBridge<T>(t); } 

Dann eine einfache Klasse vorstellen:

class Counter { 
public: 
    int getCount() const { return c; } 
    void updateCount(int i) { c = i; } 
private: 
    int c; 
}; 

Sie die Objekte in einem Array speichern können:

static Counter array[5]; 

assert(sizeof(array) == sizeof(int)*5); // no v-pointer 

Und noch sie mit polymorphen Funktionen nutzen:

void five(Interface& i) { i.updateCount(5); } 

InterfaceBridge<Counter> ib(array[3]); // create *one* v-pointer 
five(ib); 

assert(array[3].getCount() == 5); 

Der Wert vs Bezug Das ist eigentlich eine Designspannung. Im Allgemeinen müssen Sie, wenn Sie clone benötigen, nach Wert speichern, und Sie müssen klonen, wenn Sie nach Basisklasse speichern (z. B. boost::ptr_vector). Es ist möglich, tatsächlich beide Schnittstellen (und Brücken) zu bieten:

Interface <--- ClonableInterface 
    |     | 
InterfaceB  ClonableInterfaceB 

Es ist nur zusätzliche Eingabe.

---

Eine andere Lösung, viel mehr beteiligt.

Ein Switch ist durch eine Sprungtabelle implementierbar. Eine solche Tabelle perfekt zur Laufzeit erstellt, in einem std::vector zum Beispiel könnte:

class Base { 
public: 
    ~Base() { VTables()[vpointer].dispose(*this); } 

    void updateCount(int i) { 
    VTables()[vpointer].updateCount(*this, i); 
    } 

protected: 
    struct VTable { 
    typedef void (*Dispose)(Base&); 
    typedef void (*UpdateCount)(Base&, int); 

    Dispose dispose; 
    UpdateCount updateCount; 
    }; 

    static void NoDispose(Base&) {} 

    static unsigned RegisterTable(VTable t) { 
    std::vector<VTable>& v = VTables(); 
    v.push_back(t); 
    return v.size() - 1; 
    } 

    explicit Base(unsigned id): vpointer(id) { 
    assert(id < VTables.size()); 
    } 

private: 
    // Implement in .cpp or pay the cost of weak symbols. 
    static std::vector<VTable> VTables() { static std::vector<VTable> VT; return VT; } 

    unsigned vpointer; 
}; 

Und dann, ein Derived Klasse:

class Derived: public Base { 
public: 
    Derived(): Base(GetID()) {} 

private: 
    static void UpdateCount(Base& b, int i) { 
    static_cast<Derived&>(b).count = i; 
    } 

    static unsigned GetID() { 
    static unsigned ID = RegisterTable(VTable({&NoDispose, &UpdateCount})); 
    return ID; 
    } 

    unsigned count; 
}; 

Nun, Sie werden jetzt erkennen, wie groß es, dass das ist Compiler macht es für Sie, sogar auf Kosten einiger Overhead.

Oh, und wegen der Ausrichtung, sobald eine Derived Klasse einen Zeiger einführt, besteht die Gefahr, dass 4 Byte Padding zwischen Base und dem nächsten Attribut verwendet werden. Sie können sie verwenden, indem Sie vorsichtig die ersten paar Attribute in Derived auswählen, um das Auffüllen zu vermeiden ...