3. Viele Basisklassen, Zeitverlust?

Viele Basisklassen, Zeitverlust?

  • Administrator

    Grüsse zusammen,

    Aus meinem vorherigen Thread, bin ich auf den Visitor gestossen, welcher bei mir aber etwas umständlich umzusetzen ist. Ich habe für mich nun eine einigermasen befriedigende Lösung gefunden.

    Ich habe allerdings schon oft gehört, dass Polymorphie ein grosser Zeitverlust auslösen kann. Erst recht, wenn man von mehreren Basisklassen erbt.

    Ich denke nicht, dass es bei mir zu irgendwelchen Problemen kommen wird, da andere Bereiche des Codes, wesentlich mehr Zeit verschlingen werden, trotzdem hätte ich gerne gewusst, in welchem Masse sich der Zeitverlust etwa bewegt.

    Deshalb mal ein wenig Code:

    // Grundstruktur

template<typename T>
class CVisitorMethod
{
protected:
    CVisitorMethod() { };
    virtual ~CVisitorMethod() { };

public:
    virtual void visit(T&) { };
};

class CBasicVisitor
{
public:
    template<typename T>
    void visit(T& rT)
    {
        CVisitorMethod<T>* pVM = dynamic_cast<CVisitorMethod<T>*>(this);

        if(pVM)
        { pVM->visit(rT); }
        else
        { undefined_visit(); }
    }

    virtual void undefined_visit() = 0;
};

// Eine Basisklasse

class B
{
public:
    virtual void apply_visitor(CBasicVisitor& rVisitor) = 0;
};

// Eine paar Klassen

class X : public B
{
public:
    virtual void apply_visitor(CBasicVisitor& rVisitor) { rVisitor.visit(*this); };
};

class Y : public B
{
public:
    virtual void apply_visitor(CBasicVisitor& rVisitor) { rVisitor.visit(*this); };
};

// Ein paar Visitoren
class CNormalVisitor : public CBasicVisitor, public CVisitorMethod<X>, public CVisitorMethod<Y>
{
public:
    virtual void visit(X&) { std::cout << "X" << std::endl; };
    virtual void visit(Y&) { std::cout << "Y" << std::endl; };

    virtual void undefined_visit() { std::cout << "Undefined visit" << std::endl; };
};

template<typename T>
class CIsType : public CBasicVisitor, public CVisitorMethod<T>
{
private:
    bool m_bIsTrue;

public:
    CIsType() : m_bIsTrue(false) { };

    virtual void visit(T&) { m_bIsTrue = true; };
    virtual void undefined_visit() { m_bIsTrue = false; };

    bool is_true() const { return m_bIsTrue; };
};

int main()
{
    B* pX = new X;
    B* pY = new Y;

    CNormalVisitor NormalVisitor;

    pX->apply_visitor(NormalVisitor);
    pY->apply_visitor(NormalVisitor);

    CIsType<Y> IsTypeY;

    pX->apply_visitor(IsTypeY);
    std::cout << (IsTypeY.is_true() ? "true" : "false") << std::endl;

    pY->apply_visitor(IsTypeY);
    std::cout << (IsTypeY.is_true() ? "true" : "false") << std::endl;

    delete pX;
    delete pY;

    std::cin.clear();
    std::cin.sync();
    std::cin.get();
}

    Es geht halt dann vor allem darum, wenn man sehr viele CVisitorMethod Basisklassen hat. Wie stark könnte ein Programm deswegen ausgebremst werden? Ist das ein normaler dynamic_cast, wie auch bei normaler einzel Basisklassen Polymorphie oder kostet er wirklich mehr Zeit? Ab wievielen Basisklassen gibt es "Probleme"?

    Danke für die Antwort!

    Grüssli

    0
  • S

    naja also grundsätzlich gilt:

    virtual braucht etwas zeit...

    der compiler erstellt da vTables in der die addressen von den klassen gespeichert sind und muss sich immer erst die adressen aus der tabelle holen statt direkt darauf zu zugreifen
    Was kostet 'virtual'?

    0
  • ?

    kosten sind relativ. wie du selbst bereits bemerkt hast, brauchen andere ecken deines programms sowieso "ewig" im vergleich zu dem, was ein lookup in der vtable kostet. wenn man auf polymorphie verzichtet und sich als ersatz ein paar kontrollstrukturen einzieht, wirds eh auf dasselbe hinauslaufen.

    noch toller wirds mit so brutalen geschichten wie file access oder remote calls. da kannst du tausende virtual methoden einbauen, im vergleich zu den wirklich teuren operationen fallen die dann kaum noch ins gewicht.

    so als grobe faustformel vielleicht: wenn man irgendwo noch 2 ms mehr speed rauskitzeln muss, dann sollte man sich vielleicht auch mal die virtual methoden angucken.

    0
  • ?

    wobei zeitangaben wahrscheinlich sogar nichts bringen. eher wenn man taktzyklen sparen muss, lohnen sich solche mikrooptimierungen. wenn der code also auf nem toaster rennt 😉

    0
  • K

    Dravere schrieb:

    Ich habe allerdings schon oft gehört, dass Polymorphie ein grosser Zeitverlust auslösen kann.

    Leute, die sowas erzählen, gehören doch weggesperrt.

    Der Visitor in Deinem Code erfüllt doch einen gewissen Zweck. Wenn Du den ohne Visitor schreiben würdest, müsstest Du doch auch irgendwelche Tests ausführen – halt nur manuell. Das wird dadurch garantiert nicht schneller.

    Die Frage ist hingegen, ob der Visitor hier wirklich angebracht ist. Visitor ist von allen Entwurfsmustern wahrscheinlich das komplexeste, am aufwendigsten zu programmierende und zu erweiternde. IMHO sollte man lieber versuchen, um den Double Dispatch herumzukommen, indem man die Semantik ändern oder zweidimensionale Lookup-Tables verwendet (falls das in Deinem Fall möglich ist).

    0
  • Administrator

    Erstmal danke für die Antworten.

    Mir ist schon klar, dass virtual mehr Zeit braucht, dass es allerdings auch eher Mikro, wenn nicht gar sogar Nanooptimierungen sind. Mir ging es mehr darum, ob es einen Unterschied macht, wenn man viele Basisklassen hat im Gegensatz zu wenigen. Also steigt dieser minimale Zeitverlust proportional zu den Anzahl Basisklassen, bzw. virtueller Methoden?

    @Konrad Rudolph,
    Ja, der Visitor erfüllt einen gewissen Zweck. Und mit den meisten anderen Lösungen bräuchte ich wohl so oder so ca. 4-16 If -Abfragen und wohl auch noch Schleifen.

    Und der Visitor ist zum Beispiel bei CIsType nicht angebracht. Da würde theoretisch ein dynamic_cast reichen, aber das war ja nur ein Beispiel.
    Beim tatsächlichen Code ist es so, dass ich eine extrem allgemeine Visitor Schnittstelle benötige, bzw. möchte.
    Das wichtigste an diesem Visitor ist, dass die Basis ( CBasicVisitor ) keine Ahnung haben soll, was für Klassen von B abgeleitet wurden, aber trotzdem darauf reagieren können soll.

    Übrigens, noch eine zusätzliche Frage: Ist die Zeit, welche für einen dynamic_cast verwendet wird gleich der Zeit, welche für einen Aufruf einer virtuellen Funktion benötigt wird?

    Grüssli

    0
  • K

    Dravere schrieb:

    Übrigens, noch eine zusätzliche Frage: Ist die Zeit, welche für einen dynamic_cast verwendet wird gleich der Zeit, welche für einen Aufruf einer virtuellen Funktion benötigt wird?

    Nein. Ein virtueller Aufruf ist im Normalfall einfach eine Addition zweier Zeiger plus ein Call. Ein 'dynamic_cast' hingegen führt eine Typenüberprüfung durch, welche sehr unterschiedlich implementiert werden kann; selbst in der effizientesten Implementierung kann es aber passieren, dass mehrere Zeigervergleiche ausgeführt werden müssen. Allerdings könnte es sein, dass der 'dynamic_cast' zumindest bei einer flachen Vererbungshierarchie (d.h. nur eine Basisklasse, welche ihrerseits keine weiteren Basisklassen besitzt) in etwa gleichschnell ist wie ein virtueller Methodenaufruf.

    0
  • Administrator

    Herzlichen Dank für die Info.
    Wo kann man eigentlich solche Dinge nachlesen? Gibt es irgendein Buch, welches den C++ Standard wirklich gründlich und trocken erläutert? Bzw. am besten eigentlich ein Nachschlagewerk.

    Grüssli

    0
  • K

    Dravere schrieb:

    Wo kann man eigentlich solche Dinge nachlesen? Gibt es irgendein Buch, welches den C++ Standard wirklich gründlich und trocken erläutert? Bzw. am besten eigentlich ein Nachschlagewerk.

    Hmm. Also ganz praktisch ist da „Effective C++“ von Meyers. Ultimatives Nachschlagewerk ist natürlich der Standard selbst, der aber ein nettes Sümmchen kostet (wobei im Netz irgendwo eine PDF-Version rumfliegt …).

    Ich muss aber ehrlich zugeben, dass ich gar nicht weiß, inwiefern diese Implementierungsdetails im Standard so genau erklärt sind, soweit ich weiß, steht es dem Implementierer frei, wie er diesen Typenvergleich realisiert. Ein wenig Erfahrung mit Compilerbau verrät einem aber, wie sowas effizient geht.

    0
  • ?

    Na, im Standard stehen natürlich nur Vorschriften zum Verhalten drin. Wie das Verhalten implementiert ist, steht da nicht drin. Ist auch nicht Sinn des Standards. Z.B. steht bei Vectoren drin, das die Daten darin sequenziell abgelegt werden sollen. Wie dieses sequenzielle implementiert ist, steht jedoch offen. Es ist lediglich für den Implementierer meistens offensichtlich, das es bei einem Array enden wird. 😉

    In Effektiv C++ von Scott Meyers werden solche Dinge angesprochen. Aber auch dort steht dann so sinngemäß drin "Die meisten Compiler die ich getestet habe, implementieren es so und so.". Weil man es einfach nicht für jeden Compiler und Standardlib dieses Planeten sagen kann.

    0
  • S

    Hi,

    also in der "exceptional"-Serie von Herb Sutter stehen tw. auch so Sachen drin und etwas ausführlicher habe ich dazu noch in "Imperfect C++" von Matthew Wilson gelesen.
    Da geht's oftmals aber eher um "C++-Std"-Themen (wie (gut) ist welches Feature vom Compiler umgesetzt ?). Einige ganz nette Informationen konkret zum Thema "Optimierung" gab es in einem Skript, das hier im Forum mal erwähnt wurde (überhaupt sieht dessen Homepage ganz interessant aus: http://www.agner.org/optimize/).

    Wo man das aber mal "gesammelt" überblicken kann, weiß ich auch nicht.

    Gruß,

    Simon2.

    0
Anmelden zum Antworten