Lohnt es sich im Allgemeinen, virtuelle Funktionen zu verwenden, um Verzweigungen zu vermeiden?

Es scheint grobe Entsprechungen von Befehlen zu geben, die den Kosten einer Verzweigung entsprechen. Virtuelle Fehlfunktionen weisen einen ähnlichen Kompromiss auf:

• Befehl vs. Daten-Cache fehlgeschlagen
• Optimierungsbarriere

Wenn Sie sich etwas anschauen wie:

if (x==1) {
   p->do1();
}
else if (x==2) {
   p->do2();
}
else if (x==3) {
   p->do3();
}
...

Sie könnten ein Mitgliedsfunktionsarray haben, oder wenn viele Funktionen von derselben Kategorisierung abhängen oder eine komplexere Kategorisierung vorhanden ist, verwenden Sie virtuelle Funktionen:

p->do()

Aber im Allgemeinen, wie teuer sind virtuelle Funktionen vs Es Verzweigung ist schwer zu Test auf genügend Plattformen zu verallgemeinern, so dass ich mich gefragt , ob jemand eine grobe Daumenregel hatte (reizend , wenn es so einfach wie 4 waren ifs ist der Haltepunkt)

Im Allgemeinen sind virtuelle Funktionen klarer und ich würde mich zu ihnen neigen. Ich habe jedoch mehrere sehr wichtige Abschnitte, in denen ich Code von virtuellen Funktionen in Verzweigungen ändern kann. Ich würde es vorziehen, darüber nachzudenken, bevor ich dies unternehme. (Es ist keine triviale Änderung oder einfach, auf mehreren Plattformen zu testen.)

Ich wollte hier in diese bereits ausgezeichneten Antworten eintauchen und zugeben, dass ich den hässlichen Ansatz gewählt habe, tatsächlich rückwärts an dem Antimuster zu arbeiten, polymorphen Code mit gemessenen Gewinnen in switchesoder if/elseVerzweigungen zu ändern . Aber ich habe diesen Großhandel nicht gemacht, nur für die kritischsten Pfade. Es muss nicht so schwarz und weiß sein.

_{Als Haftungsausschluss arbeite ich in Bereichen wie Raytracing, in denen die Richtigkeit nicht so schwer zu erreichen ist (und die oft unscharf und ohnehin angenähert ist), während Geschwindigkeit oft eine der wettbewerbsfähigsten Eigenschaften ist, die gesucht werden. Eine Verkürzung der Renderzeiten ist oft eine der häufigsten Benutzeranforderungen, da wir uns ständig am Kopf kratzen und herausfinden, wie dies für die kritischsten gemessenen Pfade erreicht werden kann.}

Polymorphes Refactoring von Bedingungen

Zunächst ist zu verstehen, warum der Polymorphismus aus switchGründen der Wartbarkeit der bedingten Verzweigung ( oder einer Reihe von if/elseAnweisungen) vorzuziehen ist . Der Hauptvorteil hierbei ist die Erweiterbarkeit .

Mit polymorphem Code können wir unserer Codebasis einen neuen Subtyp hinzufügen, Instanzen davon zu einer polymorphen Datenstruktur hinzufügen und den gesamten vorhandenen polymorphen Code ohne weitere Änderungen weiterhin automatisch arbeiten lassen. Wenn Sie eine Menge Code in einer großen Codebasis haben, die der Form "Wenn dieser Typ 'foo' ist, tun Sie das" ähnelt , könnte es für Sie eine schreckliche Belastung sein, 50 unterschiedliche Codeabschnitte zu aktualisieren, um sie einzuführen eine neue Art von Sache, und am Ende noch ein paar fehlen.

Die Vorteile des Polymorphismus in Bezug auf die Wartbarkeit verringern sich hier natürlich, wenn Sie nur ein paar oder sogar einen Teil Ihrer Codebasis haben, die solche Typprüfungen durchführen müssen.

Optimierungsbarriere

Ich würde vorschlagen, dies nicht so sehr vom Standpunkt des Verzweigens und Pipelining aus zu betrachten und es eher vom Standpunkt des Compilerdesigns der Optimierungsbarrieren aus zu betrachten. Es gibt Möglichkeiten, die Verzweigungsvorhersage für beide Fälle zu verbessern, z. B. das Sortieren von Daten nach Untertypen (sofern diese in eine Sequenz passen).

Was sich zwischen diesen beiden Strategien stärker unterscheidet, ist die Informationsmenge, über die der Optimierer im Voraus verfügt. Ein bekannter Funktionsaufruf liefert viel mehr Informationen, ein indirekter Funktionsaufruf, der zur Kompilierzeit eine unbekannte Funktion aufruft, führt zu einer Optimierungsbarriere.

Wenn die aufgerufene Funktion bekannt ist, können Compiler die Struktur verwischen und sie auf kleinere Werte komprimieren, Aufrufe einbinden, potenziellen Aliasing-Overhead eliminieren, die Zuweisung von Befehlen / Registern verbessern und möglicherweise sogar Schleifen und andere Formen von Verzweigungen neu anordnen und so harte Verzweigungen erzeugen -codierte Miniatur-LUTs, falls zutreffend (etwas in GCC 5.3 überraschte mich kürzlich mit einer switchAussage, bei der anstelle einer Sprungtabelle eine hartcodierte Daten-LUT für die Ergebnisse verwendet wurde).

Einige dieser Vorteile gehen verloren, wenn wir Kompilierungszeit-Unbekannte in den Mix aufnehmen, wie im Fall eines indirekten Funktionsaufrufs, und hier kann die bedingte Verzweigung höchstwahrscheinlich einen Vorteil bieten.

Speicheroptimierung

Nehmen Sie ein Beispiel für ein Videospiel, bei dem eine Sequenz von Kreaturen wiederholt in einer engen Schleife verarbeitet wird. In einem solchen Fall könnten wir einen polymorphen Container wie diesen haben:

vector<Creature*> creatures;

_{Hinweis: Der Einfachheit halber habe ich unique_ptrhier gemieden .}

... wo Creatureist ein polymorpher Basistyp. In diesem Fall besteht eine der Schwierigkeiten bei polymorphen Behältern darin, dass sie häufig Speicher für jeden Subtyp separat / einzeln zuweisen möchten (z. B .: Standardwurf operator newfür jede einzelne Kreatur verwenden).

Dadurch wird häufig die erste Priorisierung für die Optimierung (falls erforderlich) des Speichers vorgenommen und nicht für die Verzweigung. Eine Strategie besteht darin, für jeden Subtyp einen festen Allokator zu verwenden und eine zusammenhängende Darstellung zu fördern, indem in großen Teilen Speicher für jeden zugeteilten Subtyp reserviert wird. Mit einer solchen Strategie kann es auf jeden Fall hilfreich sein, diesen creaturesContainer nach Subtyp (sowie nach Adresse) zu sortieren , da dies nicht nur die Verzweigungsvorhersage, sondern auch die Referenzlokalität verbessert (sodass auf mehrere Kreaturen desselben Subtyps zugegriffen werden kann) aus einer einzelnen Cache-Zeile vor der Räumung).

Partielle Devirtualisierung von Datenstrukturen und Schleifen

Nehmen wir an, Sie haben all diese Bewegungen durchlaufen und wünschen sich immer noch mehr Geschwindigkeit. Es ist erwähnenswert, dass jeder Schritt, den wir hier unternehmen, die Wartbarkeit verschlechtert und wir uns bereits in einer Phase des Metallschleifens befinden, in der die Leistung abnimmt. Es muss also eine ziemlich große Leistungsanforderung geben, wenn wir dieses Gebiet betreten, in dem wir bereit sind, die Wartbarkeit für immer kleinere Leistungssteigerungen weiter zu opfern.

Der nächste Schritt zu versuchen (und immer mit der Bereitschaft, unsere Änderungen zurückzunehmen, wenn es überhaupt nicht hilft) könnte die manuelle Devirtualisierung sein.

_{Tipp zur Versionskontrolle: Wenn Sie nicht viel optimierungsfähiger sind als ich, kann es sich lohnen, an dieser Stelle einen neuen Zweig zu erstellen, der bereit ist, ihn wegzuwerfen, wenn unsere Optimierungsbemühungen fehlschlagen, was sehr gut passieren kann. Für mich ist es alles nur Versuch und Irrtum, auch mit einem Profiler in der Hand.}

Trotzdem müssen wir diese Denkweise nicht im großen Stil anwenden. Nehmen wir an, dieses Videospiel besteht bei weitem zum größten Teil aus menschlichen Wesen. In einem solchen Fall können wir nur menschliche Kreaturen devirtualisieren, indem wir sie herausziehen und eine separate Datenstruktur nur für sie erstellen.

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures

Dies impliziert, dass alle Bereiche in unserer Codebasis, die Kreaturen verarbeiten müssen, eine separate Sonderfallschleife für menschliche Kreaturen benötigen. Damit entfällt jedoch der Aufwand für den dynamischen Versand (oder besser gesagt die Optimierungsbarriere) für den Menschen, der bei weitem der häufigste Kreaturentyp ist. Wenn diese Gebiete zahlreich sind und wir es uns leisten können, könnten wir dies tun:

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures
vector<Creature*> creatures;        // contains humans and other creatures

... wenn wir uns das leisten können, können die weniger kritischen Pfade so bleiben wie sie sind und einfach alle Kreaturentypen abstrakt verarbeiten. Die kritischen Pfade können humansin einer Schleife und other_creaturesin einer zweiten Schleife verarbeitet werden.

Wir können diese Strategie nach Bedarf erweitern und auf diese Weise möglicherweise einige Verbesserungen erzielen. Es ist jedoch erwähnenswert, inwieweit wir die Wartbarkeit in diesem Prozess herabsetzen. Die Verwendung von Funktionsvorlagen kann dabei helfen, den Code sowohl für Menschen als auch für Kreaturen zu generieren, ohne die Logik manuell zu duplizieren.

Teilweise Devirtualisierung von Klassen

Etwas, das ich vor Jahren gemacht habe und das wirklich eklig war, und ich bin mir nicht einmal sicher, ob es von Vorteil ist (dies war in der C ++ 03-Ära), war die teilweise Devirtualisierung einer Klasse. In diesem Fall haben wir bereits eine Klassen-ID für jede Instanz für andere Zwecke gespeichert (auf die über einen Accessor in der Basisklasse zugegriffen wurde, der nicht virtuell war). Da haben wir etwas Analoges gemacht (meine Erinnerung ist ein wenig verschwommen):

switch (obj->type())
{
   case id_common_type:
       static_cast<CommonType*>(obj)->non_virtual_do_something();
       break;
   ...
   default:
       obj->virtual_do_something();
       break;
}

... wo virtual_do_somethingimplementiert wurde, um nicht-virtuelle Versionen in einer Unterklasse aufzurufen. Ich weiß, es ist grob, einen expliziten statischen Downcast zu machen, um einen Funktionsaufruf zu devirtualisieren. Ich habe keine Ahnung, wie nützlich dies jetzt ist, da ich so etwas seit Jahren nicht mehr ausprobiert habe. Mit der Einführung in datenorientiertes Design empfand ich die oben beschriebene Strategie, Datenstrukturen und Schleifen heiß / kalt aufzuteilen, als weitaus nützlicher und öffnete mehr Türen für Optimierungsstrategien (und weitaus weniger hässlich).

Großhandel Devirtualization

Ich muss zugeben, dass ich noch nie so weit gekommen bin, eine Optimierungs-Denkweise anzuwenden, daher habe ich keine Ahnung von den Vorteilen. Ich habe indirekte Funktionen im Voraus vermieden, wenn ich wusste, dass es nur einen zentralen Satz von Bedingungen geben würde (z. B. Ereignisverarbeitung mit nur einem zentralen Platz, der Ereignisse verarbeitet), aber nie mit einer polymorphen Denkweise begonnen und den gesamten Weg optimiert bis hierher.

Theoretisch könnte der unmittelbare Vorteil darin bestehen, dass ein Typ möglicherweise weniger identifiziert wird als ein virtueller Zeiger (z. B. ein einzelnes Byte, wenn Sie sich auf 256 eindeutige Typen oder weniger festlegen können) und diese Optimierungsbarrieren vollständig beseitigt werden .

In einigen Fällen kann es auch hilfreich sein, einfacher zu verwaltenden Code zu schreiben (im Vergleich zu den oben beschriebenen Beispielen für die optimierte manuelle Devirtualisierung), wenn Sie nur eine zentrale switchAnweisung verwenden, ohne Ihre Datenstrukturen und Schleifen nach Subtyp aufteilen zu müssen, oder wenn eine Bestellung vorliegt -Abhängigkeit in diesen Fällen, in denen die Dinge in einer genauen Reihenfolge verarbeitet werden müssen (auch wenn dies dazu führt, dass wir uns überall verzweigen). Dies ist in Fällen der Fall, in denen Sie nicht zu viele Stellen haben, an denen Sie das tun müssen switch.

Ich würde dies im Allgemeinen nicht empfehlen, selbst bei einer sehr leistungskritischen Denkweise, es sei denn, dies ist relativ einfach zu warten. "Pflegeleicht" hängt in der Regel von zwei Faktoren ab:

• Sie benötigen keine echte Erweiterbarkeit (z. B. Sie müssen sicher sein, dass Sie genau 8 Arten von Dingen zu verarbeiten haben und nie mehr).
• Der Code enthält nicht viele Stellen, an denen diese Typen überprüft werden müssen (z. B. eine zentrale Stelle).

... dennoch empfehle ich in den meisten Fällen das obige Szenario und bei Bedarf Iteration zu effizienteren Lösungen durch teilweise Devirtualisierung. Es gibt Ihnen viel mehr Freiraum, um die Anforderungen an Erweiterbarkeit und Wartbarkeit mit der Leistung in Einklang zu bringen.

Virtuelle Funktionen vs. Funktionszeiger

Um das Ganze abzurunden, bemerkte ich hier, dass es einige Diskussionen über virtuelle Funktionen vs. Funktionszeiger gab. Es ist wahr, dass das Aufrufen von virtuellen Funktionen ein wenig zusätzliche Arbeit erfordert, dies bedeutet jedoch nicht, dass sie langsamer sind. Gegenintuitiv kann es sie sogar schneller machen.

Das ist hier nicht intuitiv, da wir es gewohnt sind, die Kosten in Form von Anweisungen zu messen, ohne auf die Dynamik der Speicherhierarchie zu achten, die tendenziell einen viel bedeutenderen Einfluss hat.

Wenn wir a classmit 20 virtuellen Funktionen vergleichen, gegenüber a, in structdem 20 Funktionszeiger gespeichert sind, und beide mehrfach instanziiert werden, beträgt der Arbeitsspeicher-Overhead jeder classInstanz in diesem Fall 8 Byte für den virtuellen Zeiger auf 64-Bit-Computern, während der Arbeitsspeicher Overhead von structist 160 Bytes.

Die praktischen Kosten dort können viel mehr obligatorische und nichtobligatorische Cache-Fehler mit der Tabelle der Funktionszeiger im Vergleich zur Klasse bei Verwendung virtueller Funktionen (und möglicherweise Seitenfehler bei einer ausreichend großen Eingabeskala) sein. Diese Kosten machen die zusätzliche Indizierungsarbeit für eine virtuelle Tabelle in der Regel zu kurz.

Ich habe auch ältere C-Codebasen (älter als ich) behandelt, bei denen das mehrfache Setzen solcher structsmit Funktionszeigern gefüllten und instanziierten Codebasen zu erheblichen Leistungssteigerungen führte (über 100% ige Verbesserungen), indem sie einfach in Klassen mit virtuellen Funktionen umgewandelt wurden aufgrund der massiven Reduzierung des Speicherverbrauchs, der erhöhten Cache-Freundlichkeit usw.

Auf der anderen Seite, wenn Vergleiche mehr über Äpfel zu Äpfeln werden, habe ich auch die entgegengesetzte Denkweise der Übersetzung von einer C ++ - Denkweise für virtuelle Funktionen in eine C-artige Funktionszeiger-Denkweise als nützlich für diese Arten von Szenarien befunden:

class Functionoid
{
public:
    virtual ~Functionoid() {}
    virtual void operator()() = 0;
};

... in der die Klasse eine einzelne überschreibbare Funktion gespeichert hat (oder zwei, wenn wir den virtuellen Destruktor zählen). In diesen Fällen kann es auf kritischen Pfaden durchaus hilfreich sein, dies zu verwandeln:

void (*func_ptr)(void* instance_data);

... idealerweise hinter einer typsicheren Schnittstelle, um die gefährlichen Würfe zu / von zu verbergen void*.

In den Fällen, in denen wir versucht sind, eine Klasse mit einer einzelnen virtuellen Funktion zu verwenden, kann es schnell hilfreich sein, stattdessen Funktionszeiger zu verwenden. Ein wichtiger Grund ist nicht unbedingt der reduzierte Aufwand beim Aufrufen eines Funktionszeigers. Dies liegt daran, dass wir nicht länger versucht sind, die einzelnen Funktionsbereiche auf die verstreuten Bereiche des Haufens zu verteilen, wenn wir sie zu einer dauerhaften Struktur zusammenfassen. Diese Art von Ansatz kann es einfacher machen, Heap-assoziierten Overhead und Speicherfragmentierungs-Overhead zu vermeiden, wenn die Instanzdaten beispielsweise homogen sind und nur das Verhalten variiert.

Es gibt also definitiv einige Fälle, in denen die Verwendung von Funktionszeigern hilfreich sein kann, aber ich habe es oft andersherum gefunden, wenn wir eine Reihe von Tabellen mit Funktionszeigern mit einer einzelnen vtable vergleichen, für die nur ein Zeiger pro Klasseninstanz gespeichert werden muss . Diese V-Tabelle befindet sich häufig in einer oder mehreren L1-Cache-Zeilen sowie in engen Schleifen.

Fazit

Das ist mein kleiner Dreh in diesem Thema. Ich empfehle in diesen Bereichen mit Vorsicht vorzugehen. Vertrauensmessungen, nicht Instinkt, und angesichts der Art und Weise, wie diese Optimierungen die Wartbarkeit oft verschlechtern, gehen Sie nur so weit, wie Sie es sich leisten können (und ein kluger Weg wäre, sich auf der Seite der Wartbarkeit zu irren).

Beobachtungen:

• In vielen Fällen sind virtuelle Funktionen schneller, da die vtable-Suche eine O(1)Operation ist, während die else if()Leiter eine O(n)Operation ist. Dies gilt jedoch nur, wenn die Verteilung der Fälle flach ist.

• Für eine einzelne if() ... elseist die Bedingung schneller, da Sie den Funktionsaufruf-Overhead speichern.

• Wenn Sie also eine flache Verteilung der Fälle haben, muss ein Break-Even-Punkt vorhanden sein. Die Frage ist nur, wo es sich befindet.

• Wenn Sie switch()anstelle von else if()Kontaktplan- oder virtuellen Funktionsaufrufen einen verwenden, erzeugt Ihr Compiler möglicherweise noch besseren Code: Er kann zu einer Position verzweigen, die aus einer Tabelle heraus gesucht wird, bei der es sich jedoch nicht um einen Funktionsaufruf handelt. Das heißt, Sie haben alle Eigenschaften des virtuellen Funktionsaufrufs ohne den gesamten Funktionsaufruf-Overhead.

• Wenn einer viel häufiger ist als der andere if() ... else, erhalten Sie die beste Leistung, wenn Sie mit diesem Fall beginnen : Sie führen einen einzelnen bedingten Zweig aus, der in den meisten Fällen korrekt vorhergesagt wird.

• Ihr Compiler kennt die erwartete Verteilung der Fälle nicht und geht von einer pauschalen Verteilung aus.

Da Ihr Compiler wahrscheinlich einige gute Heuristiken hat, um zu bestimmen, wann eine switch()als else if()Leiter oder als Tabellensuche codiert werden soll. Ich würde eher seinem Urteil vertrauen, wenn Sie nicht wissen, dass die Verteilung der Fälle voreingenommen ist.

Mein Rat ist also:

• Wenn einer der Fälle den Rest in Bezug auf die Häufigkeit in den Schatten stellt, verwenden Sie eine sortierte else if()Leiter.

• Verwenden Sie andernfalls eine switch()Anweisung, es sei denn, eine der anderen Methoden verbessert die Lesbarkeit Ihres Codes. Stellen Sie sicher, dass Sie keinen zu vernachlässigenden Leistungszuwachs mit deutlich verringerter Lesbarkeit erzielen.

• Wenn Sie a verwendet haben switch()und mit der Leistung immer noch nicht zufrieden sind, führen Sie den Vergleich durch, stellen Sie jedoch fest, dass dies switch()bereits die schnellste Möglichkeit war.

Lohnt es sich im Allgemeinen, virtuelle Funktionen zu verwenden, um Verzweigungen zu vermeiden?

Im Allgemeinen ja. Die Vorteile für die Wartung sind erheblich (Prüfung auf Trennung, Trennung von Bedenken, verbesserte Modularität und Erweiterbarkeit).

Aber im Allgemeinen, wie teuer sind virtuelle Funktionen im Vergleich zu Verzweigungen? Es ist schwierig, auf genügend Plattformen zu testen, um Verallgemeinerungen vorzunehmen. Daher habe ich mich gefragt, ob jemand eine grobe Faustregel hat.

Sofern Sie Ihr Code-Profil erstellt haben und nicht wissen, dass der Versand zwischen Zweigen ( die Bedingungsbewertung ) mehr Zeit in Anspruch nimmt als die durchgeführten Berechnungen ( der Code in den Zweigen ), optimieren Sie die durchgeführten Berechnungen.

Das heißt, die richtige Antwort auf die Frage, wie teuer virtuelle Funktionen im Vergleich zu Verzweigungen sind, lautet: Messen und herausfinden.

Faustregel : Sofern nicht die oben beschriebene Situation vorliegt (Unterscheidung von Zweigen teurer als Verzweigungsberechnungen), optimieren Sie diesen Teil des Codes für den Wartungsaufwand (verwenden Sie virtuelle Funktionen).

Sie möchten, dass dieser Abschnitt so schnell wie möglich ausgeführt wird. Wie schnell ist das Was ist Ihre konkrete Anforderung?

Im Allgemeinen sind virtuelle Funktionen klarer und ich würde mich zu ihnen neigen. Ich habe jedoch mehrere sehr wichtige Abschnitte, in denen ich Code von virtuellen Funktionen in Verzweigungen ändern kann. Ich würde es vorziehen, darüber nachzudenken, bevor ich dies unternehme. (Es ist keine triviale Änderung oder einfach, auf mehreren Plattformen zu testen.)

Verwenden Sie dann virtuelle Funktionen. Auf diese Weise können Sie bei Bedarf sogar die einzelnen Plattformen optimieren und den Client-Code trotzdem sauber halten.

Die anderen Antworten liefern bereits gute theoretische Argumente. Ich möchte die Ergebnisse eines Experiments hinzufügen, das ich kürzlich durchgeführt habe, um abzuschätzen, ob es eine gute Idee ist, eine virtuelle Maschine (VM) mit einem großen Wert switchüber dem Op-Code zu implementieren oder den Op-Code eher als Index zu interpretieren in ein Array von Funktionszeigern. Dies ist zwar nicht genau das gleiche wie ein virtualFunktionsaufruf, aber ich denke, es ist ziemlich nahe.

Ich habe ein Python-Skript geschrieben, um zufällig C ++ 14-Code für eine VM mit einer Befehlssatzgröße zwischen 1 und 10000 zu generieren, die zufällig ausgewählt wurde (wenn auch nicht gleichmäßig, um den unteren Bereich dichter abzutasten). Die generierte VM hatte immer 128 Register und Nr RAM. Die Anweisungen sind nicht aussagekräftig und haben alle die folgende Form.

inline void
op0004(machine_state& state) noexcept
{
  const auto c = word_t {0xcf2802e8d0baca1dUL};
  const auto r1 = state.registers[58];
  const auto r2 = state.registers[69];
  const auto r3 = ((r1 + c) | r2);
  state.registers[6] = r3;
}

Das Skript generiert auch Versandroutinen mit einer switchAnweisung ...

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  switch (opcode)
  {
  case 0x0000: op0000(state); return 0;
  case 0x0001: op0001(state); return 0;
  // ...
  case 0x247a: op247a(state); return 0;
  case 0x247b: op247b(state); return 0;
  default:
    return -1;  // invalid opcode
  }
}

… Und eine Reihe von Funktionszeigern.

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  typedef void (* func_type)(machine_state&);
  static const func_type table[VM_NUM_INSTRUCTIONS] = {
    op0000,
    op0001,
    // ...
    op247a,
    op247b,
  };
  if (opcode >= VM_NUM_INSTRUCTIONS)
    return -1;  // invalid opcode
  table[opcode](state);
  return 0;
}

Welche Versandroutine generiert wurde, wurde für jede generierte VM zufällig ausgewählt.

Für das Benchmarking wurde der Stream von Op-Codes von einer zufällig gesetzten ( std::random_device) Mersenne Twister Random Engine ( std::mt19937_64) generiert .

Der Code für jede VM wurde mit GCC 5.2.0 unter Verwendung der Schalter -DNDEBUG, -O3und kompiliert -std=c++14. Zunächst wurde es mit den -fprofile-generatefür die Simulation von 1000 zufälligen Anweisungen gesammelten Options- und Profildaten kompiliert . Der Code wurde dann mit der -fprofile-useOption neu kompiliert , Optimierungen basierend auf den gesammelten Profildaten zuzulassen.

Die VM wurde dann (im gleichen Verfahren) viermal für 50 000 000 Zyklen trainiert und die Zeit für jeden Lauf gemessen. Der erste Lauf wurde verworfen, um Cold-Cache-Effekte zu beseitigen. Das PRNG wurde zwischen den Läufen nicht erneut ausgesät, so dass sie nicht dieselbe Sequenz von Anweisungen ausführten.

Unter Verwendung dieses Aufbaus wurden 1000 Datenpunkte für jede Dispositionsroutine gesammelt. Die Daten wurden auf einer Quad-Core-APU AMD A8-6600K mit 2048 KiB Cache unter 64-Bit-GNU / Linux ohne grafischen Desktop oder andere Programme gesammelt. Unten ist eine grafische Darstellung der durchschnittlichen CPU-Zeit (mit Standardabweichung) pro Befehl für jede VM dargestellt.

Aufgrund dieser Daten konnte ich mir sicher sein, dass die Verwendung einer Funktionstabelle eine gute Idee ist, mit Ausnahme einer sehr geringen Anzahl von Op-Codes. Ich habe keine Erklärung für die Ausreißer der switchVersion zwischen 500 und 1000 Anweisungen.

Den gesamten Quellcode für den Benchmark sowie die vollständigen experimentellen Daten und ein hochauflösendes Diagramm finden Sie auf meiner Website .

Neben der guten Antwort von cmaster, die ich befürwortet habe, ist zu beachten, dass Funktionszeiger im Allgemeinen strikt schneller sind als virtuelle Funktionen. Beim Versenden virtueller Funktionen wird im Allgemeinen zuerst ein Zeiger vom Objekt auf die vtable verfolgt, entsprechend indiziert und dann ein Funktionszeiger dereferenziert. Der letzte Schritt ist also der gleiche, aber es gibt zunächst zusätzliche Schritte. Zusätzlich nehmen virtuelle Funktionen immer "dies" als Argument, Funktionszeiger sind flexibler.

Beachten Sie Folgendes: Wenn Ihr kritischer Pfad eine Schleife enthält, kann es hilfreich sein, die Schleife nach Versandziel zu sortieren. Offensichtlich ist dies nlogn, wohingegen das Durchlaufen der Schleife nur n ist, aber wenn Sie viele Male durchlaufen, kann sich dies lohnen. Indem Sie nach Versandzielen sortieren, stellen Sie sicher, dass derselbe Code wiederholt ausgeführt wird, sodass er im ICACHE immer aktuell bleibt und Cache-Ausfälle minimiert werden.

Eine dritte Strategie, die Sie beachten sollten: Wenn Sie sich von virtuellen Funktionen / Funktionszeigern zu if / switch-Strategien entfernen, kann es hilfreich sein, von polymorphen Objekten zu etwas wie boost :: variant (das auch den Schalter bereitstellt) zu wechseln Fall in Form der Besucherabstraktion). Polymorphe Objekte müssen mit dem Basiszeiger gespeichert werden, damit sich Ihre Daten überall im Cache befinden. Dies kann einen größeren Einfluss auf Ihren kritischen Pfad haben als die Kosten für die virtuelle Suche. Die Variante wird inline als diskriminierte Union gespeichert. Die Größe entspricht dem größten Datentyp (plus einer kleinen Konstante). Wenn sich Ihre Objekte in der Größe nicht zu stark unterscheiden, ist dies eine hervorragende Möglichkeit, mit ihnen umzugehen.

Eigentlich wäre ich nicht überrascht, wenn eine Verbesserung der Cache-Kohärenz Ihrer Daten eine größere Auswirkung hätte als Ihre ursprüngliche Frage, also würde ich das auf jeden Fall genauer untersuchen.

Darf ich erklären, warum ich das für ein XY-Problem halte ? (Sie sind nicht allein, wenn Sie sie fragen.)

Ich gehe davon aus, dass Ihr eigentliches Ziel darin besteht, Zeit zu sparen und nicht nur einen Punkt über Cache-Misses und virtuelle Funktionen zu verstehen.

Hier ist ein Beispiel für echte Leistungsoptimierung in echter Software.

In echter Software können Dinge, die für Programmierer unerheblich sind, besser erledigt werden. Man weiß nicht, was sie sind, bis das Programm geschrieben ist und die Leistung eingestellt werden kann. Es gibt fast immer mehrere Möglichkeiten, das Programm zu beschleunigen. Um zu sagen, dass ein Programm optimal ist, sagen Sie, dass im Pantheon der möglichen Programme zur Lösung Ihres Problems keines weniger Zeit in Anspruch nimmt. "Ja wirklich?"

In dem Beispiel, auf das ich verlinkt habe, dauerte es ursprünglich 2700 Mikrosekunden pro "Job". Es wurde eine Reihe von sechs Problemen behoben, bei denen die Pizza gegen den Uhrzeigersinn gedreht wurde. Die erste Beschleunigung entfernte 33% der Zeit. Der zweite entfernte 11%. Beachten Sie jedoch, dass das zweite Problem zu dem Zeitpunkt, als es gefunden wurde, nicht bei 11% lag, sondern bei 16%, da das erste Problem behoben war . In ähnlicher Weise wurde das dritte Problem von 7,4% auf 13% (fast doppelt so hoch) vergrößert, da die ersten beiden Probleme beseitigt waren.

Am Ende konnten durch diesen Vergrößerungsprozess alle bis auf 3,7 Mikrosekunden eliminiert werden. Das sind 0,14% der ursprünglichen Zeit oder eine Beschleunigung von 730x.

Das Entfernen der anfänglich großen Probleme führt zu einer moderaten Beschleunigung, ebnet jedoch den Weg für die Beseitigung späterer Probleme. Diese späteren Probleme könnten anfangs unbedeutende Teile der Gesamtmenge gewesen sein, aber nachdem frühe Probleme beseitigt wurden, werden diese kleinen Probleme groß und können zu großen Beschleunigungen führen. (Es ist wichtig zu verstehen, dass, um dieses Ergebnis zu erhalten, keines übersehen werden kann, und dieser Beitrag zeigt, wie einfach es sein kann.)

War das endgültige Programm optimal? Wahrscheinlich nicht. Keine der Beschleunigungen hatte etwas mit Cache-Fehlern zu tun. Würden Cache-Misses jetzt eine Rolle spielen? Vielleicht.

EDIT: Ich bekomme Ablehnungen von Leuten, die sich mit den "hochkritischen Abschnitten" der OP-Frage befassen. Sie wissen nicht, dass etwas "hochkritisch" ist, bis Sie wissen, welchen Bruchteil der Zeit es ausmacht. Wenn die durchschnittlichen Kosten dieser aufgerufenen Methoden im Laufe der Zeit 10 Zyklen oder mehr betragen, ist die Methode des Versendens an diese wahrscheinlich nicht "kritisch" im Vergleich zu dem, was sie tatsächlich tun. Ich sehe das immer und immer wieder, wo die Leute "jede Nanosekunde brauchen" als Grund behandeln, um penny-weise und Pfund-dumm zu sein.