CRTP zur Vermeidung von dynamischem Polymorphismus

89

Wie kann ich CRTP in C ++ verwenden, um den Overhead virtueller Elementfunktionen zu vermeiden?

Leichtigkeitsrennen im Orbit
quelle

Antworten:

138

Es gibt zwei Möglichkeiten.

Die erste besteht darin, die Schnittstelle statisch für die Struktur der Typen anzugeben:

template <class Derived>
struct base {
  void foo() {
    static_cast<Derived *>(this)->foo();
  };
};

struct my_type : base<my_type> {
  void foo(); // required to compile.
};

struct your_type : base<your_type> {
  void foo(); // required to compile.
};

Die zweite Möglichkeit besteht darin, die Verwendung der Referenz-zu-Basis- oder Zeiger-zu-Basis-Sprache zu vermeiden und die Verkabelung zur Kompilierungszeit durchzuführen. Mit der obigen Definition können Sie Vorlagenfunktionen haben, die wie folgt aussehen:

template <class T> // T is deduced at compile-time
void bar(base<T> & obj) {
  obj.foo(); // will do static dispatch
}

struct not_derived_from_base { }; // notice, not derived from base

// ...
my_type my_instance;
your_type your_instance;
not_derived_from_base invalid_instance;
bar(my_instance); // will call my_instance.foo()
bar(your_instance); // will call your_instance.foo()
bar(invalid_instance); // compile error, cannot deduce correct overload

Wenn Sie also die Struktur- / Schnittstellendefinition und den Typabzug zur Kompilierungszeit in Ihren Funktionen kombinieren, können Sie statischen Versand anstelle von dynamischem Versand durchführen. Dies ist die Essenz des statischen Polymorphismus.

Dean Michael
quelle
15
Ausgezeichnete Antwort
Eli Bendersky
5
Ich möchte betonen, dass dies not_derived_from_baseweder von basenoch abgeleitet ist von base...
leftaroundabout
3
Tatsächlich ist die Deklaration von foo () in my_type / your_type nicht erforderlich. codepad.org/ylpEm1up (verursacht Stapelüberlauf) - Gibt es eine Möglichkeit, eine Definition von foo beim Kompilieren durchzusetzen? - Ok, habe eine Lösung gefunden: ideone.com/C6Oz9 - Vielleicht möchten Sie das in Ihrer Antwort korrigieren.
cooky451
3
Können Sie mir erklären, was die Motivation ist, CRTP in diesem Beispiel zu verwenden? Wenn bar als Vorlage <Klasse T> definiert wäre void void (T & obj) {obj.foo (); }, dann wäre jede Klasse, die foo bereitstellt, in Ordnung. Anhand Ihres Beispiels scheint es also die einzige Verwendung von CRTP zu sein, die Schnittstelle zur Kompilierungszeit anzugeben. Ist es das, wofür es ist?
Anton Daneyko
1
@ Dean Michael In der Tat wird der Code im Beispiel kompiliert, auch wenn foo nicht in my_type und your_type definiert ist. Ohne diese Überschreibungen wird base :: foo rekursiv aufgerufen (und Stackoverflows). Vielleicht möchten Sie Ihre Antwort korrigieren, wie cooky451 gezeigt hat?
Anton Daneyko
18

Ich habe selbst nach anständigen Diskussionen über CRTP gesucht. Todd Veldhuizens Techniken für wissenschaftliches C ++ sind eine großartige Ressource für dieses (1.3) und viele andere fortgeschrittene Techniken wie Ausdrucksvorlagen.

Außerdem habe ich festgestellt, dass Sie den größten Teil des ursprünglichen C ++ Gems-Artikels von Coplien in Google-Büchern lesen können. Vielleicht ist das immer noch der Fall.

Sprudler
quelle
@fizzer Ich habe den von Ihnen vorgeschlagenen Teil gelesen, verstehe aber immer noch nicht, was die doppelte Summe der Vorlage <Klasse T_leaftype> (Matrix <T_leaftype> & A) bedeutet. kauft Sie im Vergleich zur Vorlage <Klasse Whatever> Doppelsumme (Whatever & A);
Anton Daneyko
@AntonDaneyko Beim Aufruf einer Basisinstanz wird die Summe der Basisklasse aufgerufen, z. B. "Bereich einer Form" mit Standardimplementierung, als wäre es ein Quadrat. Das Ziel von CRTP in diesem Fall ist es, die am meisten abgeleitete Implementierung, den "Bereich eines Trapezes" usw. aufzulösen und gleichzeitig das Trapez als Form zu bezeichnen, bis ein abgeleitetes Verhalten erforderlich ist. Grundsätzlich immer dann, wenn Sie normalerweise dynamic_castvirtuelle Methoden benötigen .
John P
1

Ich musste CRTP nachschlagen . Nachdem ich das getan hatte, fand ich einige Dinge über statischen Polymorphismus . Ich vermute, dass dies die Antwort auf Ihre Frage ist.

Es stellt sich heraus, dass ATL dieses Muster ziemlich häufig verwendet.

Roger Lipscombe
quelle
-5

Diese Wikipedia-Antwort enthält alles, was Sie brauchen. Nämlich:

template <class Derived> struct Base
{
    void interface()
    {
        // ...
        static_cast<Derived*>(this)->implementation();
        // ...
    }

    static void static_func()
    {
        // ...
        Derived::static_sub_func();
        // ...
    }
};

struct Derived : Base<Derived>
{
    void implementation();
    static void static_sub_func();
};

Obwohl ich nicht weiß, wie viel dich das tatsächlich kauft. Der Overhead eines virtuellen Funktionsaufrufs ist (natürlich vom Compiler abhängig):

  • Speicher: Ein Funktionszeiger pro virtueller Funktion
  • Laufzeit: Ein Funktionszeigeraufruf

Während der Overhead des statischen CRTP-Polymorphismus ist:

  • Speicher: Duplizieren der Basis pro Vorlageninstanziierung
  • Laufzeit: Ein Funktionszeigeraufruf + was auch immer static_cast tut
user23167
quelle
4
Tatsächlich ist das Duplizieren von Base pro Template-Instanziierung eine Illusion, da der Compiler (sofern Sie noch keine vtable haben) den Speicher der Base und der abgeleiteten für Sie in einer einzigen Struktur zusammenführt. Der Funktionszeigeraufruf wird auch vom Compiler (dem static_cast-Teil) optimiert.
Dean Michael
19
Ihre CRTP-Analyse ist übrigens falsch. Es sollte sein: Erinnerung: Nichts, wie Dean Michael sagte. Laufzeit: Ein (schnellerer) statischer Funktionsaufruf, nicht virtuell, das ist der springende Punkt der Übung. static_cast macht nichts, es erlaubt nur den Code zu kompilieren.
Frederik Slijkerman
2
Mein Punkt ist, dass der Basiscode in allen Vorlageninstanzen dupliziert wird (genau das Zusammenführen, von dem Sie sprechen). Ähnlich wie bei einer Vorlage mit nur einer Methode, die auf dem Vorlagenparameter basiert. Alles andere ist in einer Basisklasse besser, sonst wird es mehrmals eingezogen ('zusammengeführt').
user23167
1
Jede Methode in der Basis wird für jede abgeleitete Methode erneut kompiliert. In dem (erwarteten) Fall, in dem jede instanziierte Methode anders ist (da die Eigenschaften von Derived unterschiedlich sind), kann dies nicht unbedingt als Overhead gezählt werden. Dies kann jedoch zu einer größeren Gesamtcodegröße führen, verglichen mit der Situation, in der eine komplexe Methode in der (normalen) Basisklasse virtuelle Methoden von Unterklassen aufruft. Wenn Sie in Base <Derived> Dienstprogrammmethoden einfügen, die überhaupt nicht von <Derived> abhängen, werden sie trotzdem instanziiert. Vielleicht wird die globale Optimierung das etwas beheben.
Greggo
Ein Aufruf, der mehrere CRTP-Schichten durchläuft, wird während der Kompilierung im Speicher erweitert, kann sich jedoch leicht über TCO und Inlining zusammenziehen. CRTP selbst ist dann nicht wirklich der Schuldige, oder?
John P