Vermeidung von virtuellen Funktionen

Question

Nehmen wir also an, ich möchte eine Reihe von Klassen erstellen, die jeweils eine Member-Funktion mit dem gleichen Inhalt haben. Nennen wir die Funktion

void doYourJob();

Ich möchte schließlich alle diese Klassen in den gleichen Container zu setzen, so dass ich durch sie Schleife und haben jeweils "doYourJob()" durchführen können

Die offensichtliche Lösung besteht darin, eine abstrakte Klasse zu erstellen, die die Funktion

 virtual void doYourJob();

aber ich zögere, dies zu tun. Dies ist ein zeitaufwändiges Programm, und eine virtuelle Funktion würde es erheblich verschlimmern. Außerdem ist diese Funktion das einzige, was die Klassen miteinander gemeinsam haben, und doYourJob ist für jede Klasse völlig anders implementiert.

Gibt es eine Möglichkeit zu vermeiden, eine abstrakte Klasse mit einer virtuellen Funktion zu verwenden, oder werde ich es zu schlucken haben?

Answer 1

Wenn Wenn Sie die Geschwindigkeit benötigen, sollten Sie in Erwägung ziehen, eine "Typ(-identifizierende) Nummer" in die Objekte einzubetten und eine Switch-Anweisung zu verwenden, um den typspezifischen Code auszuwählen. Auf diese Weise kann der Overhead für Funktionsaufrufe vollständig vermieden werden - es genügt ein lokaler Sprung. Schneller geht es nicht. Der Preis (in Bezug auf Wartbarkeit, Neukompilierungsabhängigkeiten usw.) besteht darin, dass die typspezifische Funktionalität lokalisiert werden muss (in der switch-Anweisung).

---

UMSETZUNG

#include <iostream>
#include <vector>

// virtual dispatch model...

struct Base
{
    virtual int f() const { return 1; }
};

struct Derived : Base
{
    virtual int f() const { return 2; }
};

// alternative: member variable encodes runtime type...

struct Type
{
    Type(int type) : type_(type) { }
    int type_;
};

struct A : Type
{
    A() : Type(1) { }
    int f() const { return 1; }
};

struct B : Type
{
    B() : Type(2) { }
    int f() const { return 2; }
};

struct Timer
{
    Timer() { clock_gettime(CLOCK_MONOTONIC, &from); }
    struct timespec from;
    double elapsed() const
    {
        struct timespec to;
        clock_gettime(CLOCK_MONOTONIC, &to);
        return to.tv_sec - from.tv_sec + 1E-9 * (to.tv_nsec - from.tv_nsec);
    }
};

int main(int argc)
{
  for (int j = 0; j < 3; ++j)
  {
    typedef std::vector<Base*> V;
    V v;

    for (int i = 0; i < 1000; ++i)
        v.push_back(i % 2 ? new Base : (Base*)new Derived);

    int total = 0;

    Timer tv;

    for (int i = 0; i < 100000; ++i)
        for (V::const_iterator i = v.begin(); i != v.end(); ++i)
            total += (*i)->f();

    double tve = tv.elapsed();

    std::cout << "virtual dispatch: " << total << ' ' << tve << '\n';

    // ----------------------------

    typedef std::vector<Type*> W;
    W w;

    for (int i = 0; i < 1000; ++i)
        w.push_back(i % 2 ? (Type*)new A : (Type*)new B);

    total = 0;

    Timer tw;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
        {
            if ((*i)->type_ == 1)
                total += ((A*)(*i))->f();
            else
                total += ((B*)(*i))->f();
        }

    double twe = tw.elapsed();

    std::cout << "switched: " << total << ' ' << twe << '\n';

    // ----------------------------

    total = 0;

    Timer tw2;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
            total += (*i)->type_;

    double tw2e = tw2.elapsed();

    std::cout << "overheads: " << total << ' ' << tw2e << '\n';
  }
}

---

LEISTUNGSERGEBNISSE

Auf meinem Linux-System:

~/dev  g++ -O2 -o vdt vdt.cc -lrt
~/dev  ./vdt                     
virtual dispatch: 150000000 1.28025
switched: 150000000 0.344314
overhead: 150000000 0.229018
virtual dispatch: 150000000 1.285
switched: 150000000 0.345367
overhead: 150000000 0.231051
virtual dispatch: 150000000 1.28969
switched: 150000000 0.345876
overhead: 150000000 0.230726

Dies deutet darauf hin, dass ein Inline-Typ-Nummern-geschalteter Ansatz etwa (1,28 - 0,23) / (0,344 - 0,23) = 9.2 mal so schnell. Natürlich ist das spezifisch für das genaue System getestet / Compiler-Flags und Version usw., aber im Allgemeinen indikativ.

---

KOMMENTARE ZUM VIRTUELLEN VERSAND

Es muss jedoch gesagt werden, dass der Aufwand für virtuelle Funktionsaufrufe nur selten signifikant ist, und dann auch nur für oft so genannte triviale Funktionen (wie Getter und Setter). Selbst dann könnte man eine einzige Funktion zur Verfügung stellen, um eine ganze Menge Dinge auf einmal zu holen und zu setzen und so die Kosten zu minimieren. Die Leute machen sich viel zu viele Gedanken über die virtuelle Abfertigung - machen Sie also ein Profiling, bevor Sie unangenehme Alternativen finden. Das Hauptproblem bei ihnen ist, dass sie einen Funktionsaufruf außerhalb der Zeile durchführen, obwohl sie auch den ausgeführten Code delokalisieren, was die Cache-Nutzungsmuster verändert (zum Guten oder (häufiger) zum Schlechten).

Answer 2

Virtuelle Funktionen kosten nicht viel. Sie sind ein indirekter Aufruf, im Grunde wie ein Funktionszeiger. Was kostet die Leistung einer virtuellen Methode in einer C++-Klasse?

Wenn Sie sich in einer Situation befinden, in der jeder Zyklus pro Aufruf zählt, d.h. Sie machen nur sehr wenig Arbeit im Funktionsaufruf und Sie rufen die Funktion von Ihrer inneren Schleife in einer leistungskritischen Anwendung auf, brauchen Sie wahrscheinlich einen ganz anderen Ansatz.

Answer 3

Ich befürchte, dass eine Reihe von dynamic_cast Prüfungen in einer Schleife würden die Leistung mehr verschlechtern als eine virtuelle Funktion. Wenn man sie alle in einen Container werfen will, müssen sie einen gemeinsamen Typ haben, also kann man auch eine rein virtuelle Basisklasse mit dieser Methode darin erstellen.

In diesem Zusammenhang gibt es nicht viel, was die virtuelle Funktion auslöst: ein vtable lookup, eine Anpassung der gelieferten this Zeiger und einen indirekten Aufruf.

Wenn die Leistung so wichtig ist, könnten Sie für jeden Untertyp einen eigenen Container verwenden und jeden Container unabhängig verarbeiten. Wenn es auf die Reihenfolge ankommt, würden Sie so viele Rückwärtssprünge machen, dass der virtuelle Versand wahrscheinlich schneller ist.

Answer 4

Wenn Sie all diese Objekte im selben Container speichern wollen, müssen Sie entweder einen heterogenen Containertyp schreiben (langsam und teuer), oder Sie müssen einen Container mit void * s (igitt!), oder die Klassen müssen über Vererbung miteinander verbunden sein. Wenn Sie sich für eine der beiden ersten Optionen entscheiden, müssen Sie eine Logik einrichten, um jedes Element im Container zu betrachten, herauszufinden, welcher Typ es ist, und dann die entsprechende doYourJob() Implementierung, die im Wesentlichen auf Vererbung hinausläuft.

Ich empfehle dringend, zunächst den einfachen, geradlinigen Ansatz der Vererbung auszuprobieren. Wenn das schnell genug ist, ist das großartig! Sie sind fertig. Wenn nicht, dann versuchen Sie es mit einem anderen Schema. Verzichten Sie niemals auf eine nützliche Sprachfunktion wegen der Kosten, es sei denn, Sie haben einen guten Beweis dafür, dass die Kosten zu hoch sind.