Kann ich die Merkwürdiger Recurring Template-Muster verwenden hier (C ++)?

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. Es ist in der Regel Tausende von Widgets in der Sammlung. Die Klassen von AbstractWidget abgeleitet (von denen es Dutzende) verlassen typischerweise viele der virtuellen Funktionen nicht außer Kraft gesetzt. Diejenigen, die außer Kraft gesetzt werden, haben in der Regel sehr schnelle Implementierungen.

Dies Da ich glaube, ich kann mein System mit einigen cleveren Meta-Programmierung optimieren. Das Ziel ist, Funktion inlining zu nutzen und virtuelle Funktionsaufrufe zu vermeiden, während Sie den Code verwaltbar zu halten. Ich habe in den Merkwürdiger Recurring Template-Muster sah (siehe hier für Beschreibung). Dies scheint darauf hinzu fast tun, was ich will, aber nicht ganz.

Gibt es eine Möglichkeit, die CRTP Arbeit für mich, hier zu machen? Oder gibt es eine andere clevere Lösung kann jeder denken?

Answer 1

CRTP oder Compiler-Polymorphismus ist, wenn Sie alle Ihre Arten bei der Kompilierung kennen. Solange Sie addWidget verwenden eine Liste von Widgets zur Laufzeit zu sammeln und solange fooAll und barAll dann Mitglieder dieser homogenen Liste von Widgets zur Laufzeit verarbeiten müssen, müssen Sie verschiedene Typen zur Laufzeit verarbeiten können zu. Also für das Problem, das Sie vorgestellt haben, ich glaube, ich ist Runtime Polymorphismus stecken verwenden.

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

Wenn Sie wirklich brauchen, um Laufzeit Polymorphie zu vermeiden, dann eine der folgenden Lösungen arbeiten kann.

Option 1: Verwenden Sie eine Compiler-Sammlung von Widgets

Wenn Ihre WidgetCollection-Mitglieder bei der Kompilierung bekannt sind, 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: Ersetzen Laufzeit-Polymorphismus 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önnen dabei helfen, indem die Notwendigkeit zu reduzieren jeden Sonderfall aufzulisten; versuchen, so etwas wie die folgenden (völlig ungetestet), aber du bist wieder 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 scheinen Sie zu beschreiben - Tausende von Widgets, deren Verhalten nicht ändert, im Allgemeinen, und deren Mitglied Methoden sind sehr einfach - Sie können nicht viel Komplexität haben oder zu verwalten ändern. Wenn das der Fall ist, dann können Sie nicht OO müssen.

Diese Lösung ist die gleiche wie Laufzeit-Polymorphismus, mit der Ausnahme, dass es erfordert, dass Sie eine statische Liste von „virtuellen“ Methoden und bekannten Unterklassen halten (die nicht OO) zur Verfügung und es kann Sie virtuelle Funktion aufruft, mit einem Sprungtabelle ersetzen inlined 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

Simulierte dynamische Bindung (es gibt auch andere Verwendungen von CRTP) für, wenn der Basisklasse versteht sich als polymorph zu sein, aber Kunden nur wirklich kümmern uns um eine bestimmte abgeleitet Klasse. So zum Beispiel könnten Sie Klassen verfügen über eine Schnittstelle in eine plattformspezifische Funktionalität darstellen, und jede gegebene Plattform wird immer nur eine Implementierung benötigen. Der Punkt des Musters ist die Basisklasse templatize, so dass, obwohl es mehrere abgeleitete Klassen sind, weiß die Basisklasse bei der Kompilierung, die man in Gebrauch ist.

Es ist Ihnen nicht helfen, wenn Sie wirklich Runtime-Polymorphismus, wie zum Beispiel benötigen, wenn Sie einen Container von AbstractWidget* haben, kann jedes Element eine von mehreren abgeleiteten Klassen, und Sie haben über ihnen zu wechseln. In CRTP (oder einem Template-Code), base<derived1> und base<derived2> sind nicht verwandte Klassen. Daher so sind derived1 und derived2. Es gibt keine dynamische Polymorphie zwischen ihnen, wenn sie nicht einem anderen gemeinsame Basisklasse haben, aber dann bist du wieder da, wo Sie mit virtuellen Anrufen gestartet.

Sie könnten einige Speedup durch den Austausch Ihrer Vektor mit mehreren Vektoren erhalten: eine für jede der abgeleiteten Klassen, die Sie kennen, und ein generisches, wenn Sie später neue abgeleitete Klassen hinzufügen und nicht den Container aktualisieren. Dann addWidget hat einige (langsam) typeid Prüfung oder einen virtuellen Aufruf an das Widget, das Widget auf den richtigen Container hinzuzufügen, und vielleicht hat einige Überlastungen für, wenn der Anrufer kennt die Laufzeitklasse. Achten Sie darauf, nicht versehentlich eine Unterklasse von WidgetIKnowAbout zum WidgetIKnowAbout* Vektor hinzuzufügen. fooAll und barAll kann Schleife über jeden Behälter wiederum machen (fast) ruft nicht-virtuelle fooImpl und barImpl Funktionen, die dann inlined werden. Sie dann Schleife über die hoffentlich viel kleiner AbstractWidget* Vektor, den Aufruf der virtuellen foo oder bar Funktionen.

Es ist ein bisschen chaotisch und nicht rein OO, aber wenn fast alle Ihre Widgets Klassen gehören, die Ihr Container kennt, dann könnten Sie eine Leistungssteigerung sehen.

Beachten Sie, dass, wenn die meisten Widgets Klassen gehören, die Ihr Behälter kann über nicht wissen (weil sie in verschiedenen Bibliotheken, zum Beispiel sind), dann können Sie nicht möglicherweise haben inlining (es sei denn, Ihre dynamischen Linker Inline können. Mine kann‘ t). Sie könnten die virtuelle Call-Overhead fallen von dem Mitgliedsfunktionszeiger Flickschusterei, aber der Gewinn würde mit ziemlicher Sicherheit zu vernachlässigen oder sogar negativ sein. Die meisten der Overhead eines virtuellen Call ist im Aufruf selbst, nicht die virtuelle Lookup und ruft durch Funktionszeiger nicht inlined werden.

Sehen Sie es eine andere Art und Weise: wenn der Code zu inlined ist, das bedeutet, dass der tatsächliche Maschinencode für die verschiedenen Typen, anders zu sein hat. Dies bedeutet, dass Sie entweder mehrere Schleifen benötigen, oder eine Schleife mit einem Schalter in ihm, weil der Maschinencode eindeutig nicht in ROM auf jeden Durchlauf durch die Schleife ändern kann, je nach Art einiger Zeiger aus einer Sammlung gezogen.

Nun, ich denke, vielleicht das Objekt könnte etwas asm Code enthält, der die Schleife Kopien in der RAM, ausführbare markiert, und springen in. Aber das ist keine C ++ Member-Funktion. Und es kann nicht portabel gemacht werden. Und es wäre wahrscheinlich nicht einmal schnell sein, was mit dem Kopieren und dem icache Ungültigkeits. Weshalb virtuelle Anrufe existieren ...

Answer 3

Die kurze Antwort ist nein.

Die lange Antwort (oder noch kurz campared zu einigen anderen Antworten: -)

Sie sind dynamisch, um herauszufinden, was zur Laufzeit auszuführen funktioniert (das ist, was virtuelle Funktionen sind). Wenn Sie einen Vektor haben (whoses Mitglieder können nicht bei der Kompilierung festgelegt werden), dann können Sie nicht arbeiten, wie die Funktionen Inline egal, was Sie versuchen.

Der einzige caviat darauf ist, dass, wenn die Vektoren immer die gleichen Elemente enthalten (dh Sie eine Kompilierung trainieren konnte, was zur Laufzeit ausgeführt wird werden). Sie könnten dann diese wieder Arbeit, aber es würde somthing anderes als ein Vektor erfordern, um die Elemente zu halten (wahrscheinlich eine Struktur mit allen Elementen als Mitglieder).

Auch tun Sie wirklich denken, dass virtuelle Versand ist ein Engpass?
Ich persönlich bezweifle es stark.

Answer 4

Das Problem, das Sie hier haben, ist mit WidgetCollection::widgets. Ein Vektor kann nur Elemente eines Typs enthalten, und erfordert die Verwendung von CRTP dass jedes AbstractWidget einen anderen Typ aufweisen, durch die gewünschte abgeleiteten Typ templatized. Das heißt, sie ist AbstractWidget 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. diese alle in einem einzigen Vektor Speicherung wird nicht funktionieren. So wie es aussieht, in diesem Fall virtuelle Funktionen sind der Weg zu gehen.

Answer 5

Nicht, wenn Sie einen Vektor von ihnen benötigen. Die STL-Container sind völlig homogen, was bedeutet, dass, wenn Sie einen widgetA und widgetB in demselben Behälter speichern müssen, müssen sie von einem gemeinsamen Elternteil vererbt werden. Und wenn widgetA :: bar () tut etwas anderes als widgetB :: bar (), müssen Sie die Funktionen virtuellen machen.

Sie alle Widgets müssen im gleichen Behälter sein? Sie könnten wie etwas tun

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

Und dann würden die Funktionen nicht benötigen virtuellen sein.

Answer 6

Die Chancen stehen, dass Sie nach all diesen Bemühungen gehen, werden Sie keine Performance-Unterschied sehen.

Das ist absolut die falsch Art und Weise zu optimieren. Sie würden nicht einen logischen Fehler, indem Zufallscodezeilen würden Sie beheben? Nein, das ist albern. Sie müssen nicht „reparieren“ Code, bis Sie zum ersten Mal tatsächlich Ihr Problem verursacht werden, welche Linien finden. Also warum sollten Sie behandeln Leistung Bugs anders?

Sie benötigen eine Anwendung profilieren und finden, wo die wirklichen Engpässe sind. Dann beschleunigen diesen Code und wiederholen Sie die Profiler. Wiederholen, bis die Performance-Bug (zu langsam Ausführung) verschwunden ist.