2010-06-14 1 views
8

Hat jemand Erfahrung beim Reduzieren von Vorlagencode durch Vererbung?Reduzieren von Vorlagenblähung mit Vererbung

i zögern unsere Container auf diese Weise umschreiben:

class vectorBase 
{ 
    public: 
    int size(); 
    void clear(); 
    int m_size; 
    void *m_rawData; 
    //.... 
}; 

template< typename T > 
class vector : public vectorBase 
{ 
    void push_back(const T&); 
    //... 

}; 

ich maximale Leistung halten sollte, während die Zeit

reduzieren kompilieren Ich frage mich auch, warum stl Implementierungen nicht diesem Ansatz verwendet

Dank für Ihre Bewertungen

+0

Dieser Code funktioniert nicht wie er ist, da alle 'vectorBase'-Member' private' sind und daher von abgeleiteten Klassen nicht zugänglich sind. –

+1

Und es fehlt ';' überall, aber wir haben es verstanden. +1 Interessante Frage imho. – ereOn

+0

Ja, ich weiß, dass dieser Code nicht kompiliert wird. es ist mir egal;) Ich möchte nicht eine ganze STL-Container einfügen ... – benoitj

Antwort

1

Ich denke, das ist eine vorzeitige Optimierung. Im Allgemeinen, außer in eingebetteten Systemen, sind Speicherplatz und Speicher reichlich vorhanden und billig, so dass es keinen Grund gibt, zu versuchen, für eine kleine Menge an Coderaum zu optimieren. Indem man alles im Template-Code behält, macht es mehr offensichtlich, was vor sich geht, als Vererbung zu verwenden, was die Dinge komplizierter machen würde.

Zusätzlich werden die meisten Anwendungen nicht Hunderte von Instanziierungen generieren, und für jedes T können nicht alle Methoden verwendet werden, was den Code-Footprint weiter reduziert.

Nur wenn es extrem enge Speicherüberlegungen (eingebettet) gäbe, würde ich verschiedene mögliche Ansätze berücksichtigen (einschließlich der, die Sie vorgestellt haben).

EDIT: Ich bin mir nicht sicher, dass es in ein wenig von Standard-Container-Fällen viel zu gewinnen gibt, da sie immer noch viel Vorlagencode benötigen. Für interne Klassen, die nur wenig Template-spezifischen Code und viel gemeinsame Logik haben, könnte dies sowohl dem generierten Code als auch der Kompilierungsgeschwindigkeit helfen. Ich vermute, dass es nicht oft verwendet wird, weil es komplexer ist und die Vorteile auf bestimmte Szenarien beschränkt sind.

+1

Er redet über _compile Zeit zu reduzieren._ – Stephen

+2

@Stephen: Was ist genau das, was nicht mit diesem Ansatz passieren wird. Die meiste Komplexität in einem Container besteht darin, Konstruktoren und Destruktoren zu geeigneten Zeitpunkten aufzurufen, und dies kann nur in einem Vorlagencode erfolgen, in dem der enthaltene Typ vollständig definiert ist. –

+0

@Ben voigt: Bei diesem Ansatz liegen die ctor/dtor-Aufrufe natürlich im Template-Code. Aber ich kann in die Basisklasse die Speicherzuweisung/-zerstörung einfügen, zum Beispiel – benoitj

0

IIRC, Qt verwendet (oder verwendet?) Einen ähnlichen Ansatz für ihre QList et al.

Grundsätzlich würde es funktionieren, aber Sie müssen sicherstellen, dass Sie alles setzen, was auf T innerhalb Vektor Vorlage abhängt. Leider ist dies fast der gesamte Code in der Vektorklasse (in vielen Fällen muss der Code einige T Konstruktoren oder Destruktoren aufrufen), mit Ausnahme der Zuweisung von Rohspeicher und size()/capacity(). Ich bin mir nicht sicher, ob sich das auszahlt.

Es zahlt sich sicherlich aus, wenn man von einigen Vorlagenparametern abstrahieren kann (zB set<T>::iterator muss nicht auf den Komparator des Sets achten) oder wenn man eine vollständige Implementierung für eine große Klasse von Typen brauen kann (z. B. mit Trivial copy-ctor und dtor).

0

Der Code, den Sie gepostet haben, ist einfach falsch. Wenn die Klasse, die Sie im Vektor speichern, einen Destruktor hat, wird dieser Destruktor nicht aufgerufen, da der Compiler vectorBase alle Informationen darüber verloren hat, wann der Destruktor durch Gießen an void* aufgerufen werden soll.

Um dies richtig auszuführen, müssen Sie den richtigen Destruktor aufrufen. Sie müssen verschiedene Kopien des Codes generieren, die jeweils den richtigen Destruktor aufrufen. Diese Arbeit wird durch die Verwendung von Vorlagen vereinfacht.

(Um Ihren Ansatz mit einer Nicht-Template-Basisklasse zu verwenden, müssen Sie nur so vielen Maschinencode erzeugen, aber Sie müssen eine ganze Menge mehr C++ Code von Hand schreiben.)

Deshalb ist dieser Ansatz lohnt sich wirklich nicht.

+1

Ja, ich weiß, dass mein Code falsch ist. Das ist nicht wirklich wichtig. Ich zeige nur die Idee, so viel wie möglich Template-Code in einer Basisklasse zu "extrahieren". Du hast Recht für dtor/ctor, aber zum Beispiel könnte ich den malloc/free in die Basisklasse legen – benoitj

3

Nur sehr wenige Operationen auf einem Vektor sind sinnvoll, wenn Sie nicht wissen, welchen Typ die gespeicherten Elemente haben. Zum Beispiel muss die clear()-Methode, die Sie zu Ihrer Basisklasse hinzugefügt haben, die Destruktoren der Elemente aufrufen, die aus dem Vektor entfernt wurden. Daher muss sie ihren Typ kennen und muss Vorlagen erstellt werden.

Es gibt auch wirklich nicht viel können Sie mit der a void *m_rawData tun, ohne zu wissen, die Arten der Dinge darin, im Grunde alle Operationen auf es mindestens die Größe des gespeicherten Typs wissen müssen. Das einzige, was ich mir vorstellen kann, wäre, dass Sie free() es können, wenn Sie wissen, dass es keine Elemente enthält (wenn es Elemente enthält, müssen Sie ihre Destruktoren aufrufen). Das Zuweisen, Festlegen und Zugreifen auf Elemente funktioniert nicht, wenn Sie nicht wissen, wo die einzelnen Elemente beginnen und enden. Auch die Implementierung aller Methoden wäre viel sauberer und einfacher, wenn m_rawData stattdessen eine korrekt getippte T* wäre. Eine size() Methode in der Basisklasse würde nur funktionieren, wenn ihre einzige Aufgabe darin besteht, eine m_size Mitgliedsvariable zurückzugeben, aber ein Vektor muss die Größe nicht unbedingt explizit speichern (die Implementierungen, die ich kenne, tun dies nicht). Sie könnten wahrscheinlich implementieren ist, so dass die Größe explizit gespeichert wird, aber dann wieder size() ist wahrscheinlich keine Methode, die lange dauert, um zu kompilieren, auch wenn es templated ist.

Insgesamt denke ich nicht, dass es viele Methoden gibt, die in einer Basisklasse implementiert werden können. Die meisten Operationen auf einem Vektor müssen über die darin gespeicherten Elemente wissen.

0

Die kurzen davon:

Ja, dieser Ansatz wird [wahrscheinlich] Arbeit in begrenzten Anzahl spezialisierten Umständen. Ich vermute nicht, dass std::vector (oder der Rest von STL) zu diesen Umständen gehören.

Die lange davon:

Wie andere erwähnt haben (und ich stimme), außerhalb eines eingebetteten Systems, Code aufblasen ist nicht viel von einem Problem auf einer kompilierten binären.

Aber viele von uns leiden unter den Kompilierungskosten beim Erstellen von Größen mehr Code während des Kompilierungsschritts, als wenn wir kompilierte Bibliotheken zum Verknüpfen hätten (anstatt Headerdateien zu kompilieren). Fügen Sie ihm die Schwierigkeit hinzu, eine dieser Template-Header-Dateien zu ändern und das gesamte Projekt von Grund auf neu zu kompilieren. Lange kompilieren Zeiten für sad Entwickler machen :(

Es kann nicht ein großes Prozent der Entwickler beeinflussen -.. Von der Größe Ihres Unternehmens Code-Basis abhängig, und wie Sie Ihre Build-Umgebung strukturieren Steuern zweifellos wir in meiner Firma

Wie einige Antworten darauf hingewiesen haben, gibt es nicht viel zu abstrahieren von einer std::vector, die es in Ihrem Beispiel besser machen würde.Sicherlich müssen Sie in der Lage sein, einzelne Elemente zu erstellen und zu zerstören und Methoden virtual zu behindern Laufzeit-Leistung (was wichtiger als Kompilierzeit-Leistung ist) Darüber hinaus verliert der Compiler die Möglichkeit, die void*-Bibliothek für Vorlagencode zu optimieren, dies könnte zu einem größeren Ergebnis führen e Leistungsverlust.

Ich interessiere mich mehr für die komplexeren Strukturen - würde std::map Abstraktion profitieren? Was, wenn Sie den rot-schwarzen Baum (die SGI-Implementierung) herausgenommen und gegen eine rot-schwarze Baumbibliothek verbunden haben.Sie müssten (wahrscheinlich) die Elemente außerhalb der std::map speichern, so dass die Destruktoren nicht aufgerufen werden müssen, dies aber (wieder) zu einem Leistungsverlust in der Laufzeit aufgrund der Verdopplung Ihrer Indirektion führen kann.

Ich bin ziemlich sicher, dass Sie diese Methode nicht verwenden können, um die Implementierung von STL zu verbessern.

Wenn Sie die Datenstrukturen, die Sie gespeichert haben, besser gekannt haben, oder wenn Sie einen sehr speziellen Vorlagen-Typ hatten (nicht unbedingt einen Container), könnten Sie wahrscheinlich Ihre Leistung verbessern. Aber dann stellt sich die Frage: Wie oft werden Sie diesen neuen Templat-Typ verwenden, so dass der Aufwand für die Erstellung deutlich erhöht wird? Natürlich würde es helfen, Zeiten für std::vector zu kompilieren, aber vielleicht nicht für my_domain_specific_ptr_container. Wenn Sie 50% der Kompilierzeit für my_domain_specific_ptr_container speichern, wie oft müssen Sie es verwenden, um einen ausreichend hohen Build-Boost zu bemerken, um die zusätzliche Komplexität der Klasse zu rechtfertigen (und die Debug-Fähigkeit zu reduzieren).

Wenn Sie nicht bereits haben, Ihre Zeit besser ausgegeben werden können Ihre Build-Tools verteilen :)

Wenn auf der anderen Seite, können Sie dies versuchen und es funktioniert für STL-Container ... bitte Post zurück. Ich möchte einen schnelleren Build! ;)

1

Ich verstehe Ihre Vorgehensweise.

Um ehrlich zu sein habe ich es verwendet ... obwohl offensichtlich nicht für STL-Container: ihre Code ist praktisch fehlerfrei und optimiert und ich bin sehr unwahrscheinlich, eine bessere Umsetzung selbst zu finden!

Ich interessiere mich nicht viel über die Kompilierzeit: es ist ein peinlich paralleles Problem (abgesehen von Link) und distcc usw. kümmern sich um alle Probleme, die Sie sogar mit einer großen Codebasis haben können. Und ich meine groß, ich arbeite in einer Firma, die einen neuen Compiler von HP benötigt, weil die Version, die wir hatten, nicht mehr als 128Ko ... in der Befehlszeile des Linkers unterstützt hat. Und es war nur eine der Anwendungen, und es war vor ein paar Jahren, und sie haben es glücklicherweise seither in mehreren Brocken aufgeteilt.

Allerdings, so viel wie ich nicht über die Kompilierzeit, I tun kümmern viel über reduzierte Abhängigkeiten und binäre Kompatibilität. Und wenn ich selbst einen Vorlagencode schreibe, überprüfe ich, ob es möglich ist, einige Operationen außerhalb des Vorlagencodes zu berücksichtigen.

Die erste Aufgabe ist es, diejenigen Punkte zu isolieren, an denen Sie wirklich gewinnen können. Eine Codezeile zu bekommen ist keine Zeit wert, Sie wollen volle Funktionen bekommen.

Die zweite Aufgabe ist zu entscheiden, ob Sie sie inline halten wollen oder nicht. Es hängt davon ab, ob Ihnen die Leistung wichtig ist oder nicht. Der Overhead eines Funktionsaufrufs kann für Sie wichtig sein oder auch nicht.

Allerdings würde ich sicherlich keine Vererbung für den Job verwenden. Inheritance ist eine IS-A Beziehung: Es definiert eine Schnittstelle, keine Implementierung. Verwenden Sie entweder Composition oder einfach freie Funktionen, die Sie in einem Dienstprogramm-Namespace (detail wie in Boost?) Speichern.

0

Einige Implementierungen tun verwenden (eine Form von) den obigen Ansatz. Hier ist GCC

template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 
    class vector : protected _Vector_base<_Tp, _Alloc> 
    { 
    ... 
    } 

In diesem Fall ist das Ziel der Speicherverwaltung zu _Vector_base zu delegieren ist. Wenn Sie sich dafür entscheiden, Ihre Zeit damit zu verbringen, STL neu zu erfinden, folgen Sie bitte hier Ihren Ergebnissen.Vielleicht helfen Ihre Bemühungen, den alten "Code Bloat" -Rufen, die immer noch von Zeit zu Zeit zu hören sind, ein Ende zu setzen.