Kann ich das Curiously Recurring Template Pattern hier (C++) verwenden?

Question

Ich habe eine C++ Anwendung, die so etwas wie dies vereinfacht werden kann:

class AbstractWidget { 
public: 
    virtual ~AbstractWidget() {} 
    virtual void foo() {} 
    virtual void bar() {} 
    // (other virtual methods) 
}; 

class WidgetCollection { 
private: 
    vector<AbstractWidget*> widgets; 

public: 
    void addWidget(AbstractWidget* widget) { 
    widgets.push_back(widget); 
    } 

    void fooAll() { 
    for (unsigned int i = 0; i < widgets.size(); i++) { 
     widgets[i]->foo(); 
    } 
    } 

    void barAll() { 
    for (unsigned int i = 0; i < widgets.size(); i++) { 
     widgets[i]->bar(); 
    } 
    } 

    // (other *All() methods) 
}; 

Meine Anwendung ist leistungs kritisch. In der Sammlung befinden sich normalerweise Tausende von Widgets. Die von AbstractWidget abgeleiteten Klassen (von denen es Dutzende gibt) lassen viele der virtuellen Funktionen in der Regel nicht überschrieben. Diejenigen, die außer Kraft gesetzt werden, haben typischerweise sehr schnelle Implementierungen.

Angesichts dieser, ich fühle mich, dass ich mein System mit einigen cleveren Meta-Programmierung optimieren kann. Das Ziel besteht darin, Funktionsinlining zu nutzen und virtuelle Funktionsaufrufe zu vermeiden, während der Code managbar bleibt. Ich habe das seltsam wiederkehrende Vorlagenmuster (siehe here für die Beschreibung) untersucht. Dies scheint fast tun, was ich will, aber nicht ganz.

Gibt es eine Möglichkeit, das CRTP hier für mich arbeiten zu lassen? Oder gibt es eine andere clevere Lösung, die man sich vorstellen kann?

Answer 1

CRTP oder Kompilierzeit-Polymorphie ist für, wenn Sie alle Ihre Typen zur Kompilierzeit kennen. Solange Sie addWidget verwenden, um eine Liste von Widgets zur Laufzeit zu sammeln und solange fooAll und dann Mitglieder der homogenen Liste von Widgets zur Laufzeit behandeln müssen, müssen Sie in der Lage sein, verschiedene Typen zur Laufzeit zu behandeln. Also für das Problem, das Sie vorgestellt haben, denke ich, dass Sie mit Laufzeit-Polymorphismus stecken bleiben.

Eine Standard-Antwort, natürlich, ist zu überprüfen, ob die Leistung der Laufzeit-Polymorphismus ist ein Problem, bevor Sie versuchen, es zu vermeiden ...

Wenn Sie wirklich Runtime Polymorphie vermeiden müssen, dann eine der folgenden Lösungen können funktionieren.

Option 1:

einen Compiler-Sammlung von Widgets Verwendung Wenn sich Ihre WidgetCollection-Mitglieder bei der Kompilierung bekannt ist, dann können Sie ganz einfach Vorlagen verwenden.

template<typename F> 
void WidgetCollection(F functor) 
{ 
    functor(widgetA); 
    functor(widgetB); 
    functor(widgetC); 
} 

// Make Foo a functor that's specialized as needed, then... 

void FooAll() 
{ 
    WidgetCollection(Foo); 
} 

Option 2: Laufzeit-Polymorphismus ersetzen mit freien Funktionen

class AbstractWidget { 
public: 
    virtual AbstractWidget() {} 
    // (other virtual methods) 
}; 

class WidgetCollection { 
private: 
    vector<AbstractWidget*> defaultFooableWidgets; 
    vector<AbstractWidget*> customFooableWidgets1; 
    vector<AbstractWidget*> customFooableWidgets2;  

public: 
    void addWidget(AbstractWidget* widget) { 
    // decide which FooableWidgets list to push widget onto 
    } 

    void fooAll() { 
    for (unsigned int i = 0; i < defaultFooableWidgets.size(); i++) { 
     defaultFoo(defaultFooableWidgets[i]); 
    } 
    for (unsigned int i = 0; i < customFooableWidgets1.size(); i++) { 
     customFoo1(customFooableWidgets1[i]); 
    } 
    for (unsigned int i = 0; i < customFooableWidgets2.size(); i++) { 
     customFoo2(customFooableWidgets2[i]); 
    } 
    } 
}; 

hässlich, und wirklich nicht OO. Vorlagen könnten dabei helfen, die Notwendigkeit zu reduzieren, jeden Spezialfall aufzulisten. versuche etwas wie das Folgende (vollständig ungetestet), aber du bist zurück zu keinem Inlining in diesem Fall.

class AbstractWidget { 
public: 
    virtual AbstractWidget() {} 
}; 

class WidgetCollection { 
private: 
    map<void(AbstractWidget*), vector<AbstractWidget*> > fooWidgets; 

public: 
    template<typename T> 
    void addWidget(T* widget) { 
    fooWidgets[TemplateSpecializationFunctionGivingWhichFooToUse<widget>()].push_back(widget); 
    } 

    void fooAll() { 
    for (map<void(AbstractWidget*), vector<AbstractWidget*> >::const_iterator i = fooWidgets.begin(); i != fooWidgets.end(); i++) { 
     for (unsigned int j = 0; j < i->second.size(); j++) { 
     (*i->first)(i->second[j]); 
     } 
    } 
    } 
}; 

Option 3: Beseitigen OO

OO ist nützlich, weil es die Komplexität hilft bei der Verwaltung und weil es hilft, die Stabilität in der sichts des Wandels zu halten. Für die Umstände, die Sie zu beschreiben scheinen - Tausende von Widgets, deren Verhalten sich im Allgemeinen nicht ändert und deren Mitgliedermethoden sehr einfach sind - haben Sie möglicherweise nicht viel Komplexität oder Änderungen zu verwalten. Wenn das der Fall ist, brauchen Sie möglicherweise OO nicht.

Diese Lösung entspricht dem Laufzeitpolymorphismus, außer dass Sie eine statische Liste von "virtuellen" Methoden und bekannten Unterklassen (die nicht OO ist) verwalten müssen und virtuelle Funktionsaufrufe durch eine Sprungtabelle ersetzen können Inline-Funktionen.

class AbstractWidget { 
public: 
    enum WidgetType { CONCRETE_1, CONCRETE_2 }; 
    WidgetType type; 
}; 

class WidgetCollection { 
private: 
    vector<AbstractWidget*> mWidgets; 

public: 
    void addWidget(AbstractWidget* widget) { 
    widgets.push_back(widget); 
    } 

    void fooAll() { 
    for (unsigned int i = 0; i < widgets.size(); i++) { 
     switch(widgets[i]->type) { 
     // insert handling (such as calls to inline free functions) here 
     } 
    } 
    } 
}; 

Answer 2

Das Problem, das Sie hier haben werden, ist mit WidgetCollection::widgets. Ein Vektor kann nur Elemente eines Typs enthalten, und die Verwendung des CRTP erfordert, dass jeder AbstractWidget einen anderen Typ hat, der durch den gewünschten abgeleiteten Typ templatisiert wird. Das heißt, du bist AbstractWidget etwas würde wie folgt aussehen:

template< class Derived > 
class AbstractWidget { 
    ... 
    void foo() { 
     static_cast< Derived* >(this)->foo_impl(); 
    }   
    ... 
} 

was bedeutet, dass jeder AbstractWidget mit einem anderen Derived Typ einen anderen Typ AbstractWidget<Derived> darstellen würde. Das alles in einem Vektor zu speichern funktioniert nicht. Es sieht also so aus, als wären virtuelle Funktionen der richtige Weg.

Answer 3

Nicht, wenn Sie einen Vektor von ihnen brauchen. Die STL-Container sind vollständig homogen. Wenn Sie also ein WidgetA und ein WidgetB in demselben Container speichern müssen, müssen sie von einem gemeinsamen übergeordneten Objekt geerbt werden. Und wenn widgetA :: bar() etwas anderes als widgetB :: bar() tut, müssen Sie die Funktionen virtuell machen.

Müssen sich alle Widgets im selben Container befinden? Sie könnten etwas wie

vector<widgetA> widget_a_collection; 
vector<widgetB> widget_b_collection; 

tun Und dann müssten die Funktionen nicht virtuell sein.

Answer 4

Simulated dynamische Bindung (es gibt auch andere Verwendungen von CRTP) zum, wenn der Basisklasse versteht sich als polymorph zu sein, aber Kunden tatsächlich nur über eine bestimmte abgeleitete Klasse kümmern. Zum Beispiel könnten Sie Klassen haben, die eine Schnittstelle zu einigen plattformspezifischen Funktionen darstellen, und jede gegebene Plattform wird immer nur eine Implementierung benötigen. Der Punkt des Musters besteht darin, die Basisklasse zu templatisieren, so dass, obwohl es mehrere abgeleitete Klassen gibt, die Basisklasse zur Kompilierzeit weiß, welche verwendet wird.

Es hilft Ihnen nicht, wenn Sie wirklich Laufzeit-Polymorphismus benötigen, wie zum Beispiel wenn Sie einen Container von AbstractWidget* haben, kann jedes Element eine von mehreren abgeleiteten Klassen sein, und Sie müssen darüber iterieren. In CRTP (oder einem beliebigen Vorlagencode) sind base<derived1> und base<derived2> nicht miteinander in Beziehung stehende Klassen. Daher sind auch derived1 und derived2. Es gibt keinen dynamischen Polymorphismus zwischen ihnen, es sei denn, sie haben eine andere gemeinsame Basisklasse, aber dann sind Sie wieder da, wo Sie mit virtuellen Aufrufen begonnen haben.

Sie könnten eine Beschleunigung erzielen, indem Sie Ihren Vektor durch mehrere Vektoren ersetzen: einen für jede abgeleitete Klasse, den Sie kennen, und einen generischen, wenn Sie später neue abgeleitete Klassen hinzufügen und den Container nicht aktualisieren. Dann fügt addWidget einige (langsam) typeid Überprüfung oder einen virtuellen Aufruf an das Widget, um das Widget zum richtigen Container hinzuzufügen, und hat möglicherweise einige Überladungen für, wenn der Aufrufer die Laufzeitklasse kennt. Achten Sie darauf, nicht versehentlich eine Unterklasse von WidgetIKnowAbout in den Vektor WidgetIKnowAbout* einzufügen. fooAll und barAll können Schleife über jeden Container der Reihe nach (schnell) Anrufe zu nicht-virtuellen fooImpl und barImpl Funktionen machen, die dann inline sind. Sie schleifen dann über den hoffentlich viel kleineren AbstractWidget* Vektor und rufen die virtuellen foo oder bar Funktionen auf.

Es ist ein bisschen chaotisch und nicht pure-OO, aber wenn fast alle Ihre Widgets zu Klassen gehören, die Ihr Container kennt, dann sehen Sie möglicherweise eine Leistungssteigerung.

Wenn die meisten Widgets zu Klassen gehören, die Ihr Container möglicherweise nicht kennt (weil sie sich beispielsweise in verschiedenen Bibliotheken befinden), können Sie möglicherweise keine Inlining-Operationen ausführen (es sei denn, Ihr dynamischer Linker kann inline sein t). Sie könnten den virtuellen Anruf-Overhead fallen lassen, indem Sie sich mit Mitgliedsfunktionszeigern herumärgern, aber der Gewinn wäre mit ziemlicher Sicherheit vernachlässigbar oder sogar negativ. Der größte Teil des Overheads eines virtuellen Anrufs liegt im Anruf selbst, nicht in der virtuellen Suche, und Anrufe über Funktionszeiger sind nicht inline.

Sehen Sie es sich anders an: Wenn der Code inline sein soll, bedeutet dies, dass der tatsächliche Maschinencode für die verschiedenen Typen unterschiedlich sein muss. Dies bedeutet, dass Sie entweder mehrere Schleifen oder eine Schleife mit einem Schalter benötigen, da der Maschinencode im ROM bei jedem Durchlauf durch die Schleife nicht geändert werden kann, je nachdem, welcher Zeiger aus einer Sammlung gezogen wurde.

Nun, ich denke, vielleicht könnte das Objekt einige Asm-Code enthalten, die die Schleife in RAM kopiert, markiert ausführbar und springt in. Aber das ist keine C++ - Memberfunktion. Und es kann nicht portabel gemacht werden. Und es wäre wahrscheinlich nicht einmal schnell, was mit dem Kopieren und der Icache-Entwertung. Deshalb existieren virtuelle Anrufe ...

Answer 5

Die kurze Antwort ist nein.

Die lange Antwort (oder noch kurz auf einige andere Antworten campared :-)

Sie versuchen, dynamisch, herauszufinden, was funktioniert zur Laufzeit ausgeführt werden (das ist, was virtuelle Funktionen sind). Wenn Sie einen Vektor haben (dessen Mitglieder zum Zeitpunkt der Kompilierung nicht bestimmt werden können), können Sie nicht herausfinden, wie Sie die Funktionen zusammenfassen können, ganz gleich, was Sie versuchen.

Der einzige Nachteil ist, dass wenn die Vektoren immer dieselben Elemente enthalten (dh Sie könnten eine Kompilierzeit ausarbeiten, was zur Laufzeit ausgeführt wird). Sie könnten dies dann erneut bearbeiten, aber es würde etwas anderes als ein Vektor erfordern, um die Elemente zu halten (wahrscheinlich eine Struktur mit allen Elementen als Mitglieder).

Denken Sie wirklich, dass der virtuelle Versand ein Flaschenhals ist?
Persönlich bezweifle ich es sehr.

Answer 6

Wahrscheinlichkeiten sind, dass, nachdem Sie alle diese Bemühungen durchlaufen haben, Sie keinen Leistungsunterschied sehen werden.

Dies ist absolut die falsche Weg zu optimieren. Sie würden keinen logischen Fehler beheben, indem Sie zufällige Codezeilen ändern, oder? Nein, das ist albern. Sie "reparieren" den Code nicht, bis Sie zuerst herausfinden, welche Zeilen tatsächlich Ihr Problem verursachen. Also warum würden Sie Leistung Bugs anders behandeln?

Sie müssen Ihre Anwendung profilieren und finden Sie, wo die echten Engpässe sind. Beschleunigen Sie dann diesen Code und führen Sie den Profiler erneut aus. Wiederholen Sie den Vorgang, bis der Leistungsfehler (zu langsame Ausführung) behoben ist.