STL-Performance & Boost lib -> ja oder nein?

[tntnet]

Dravere schrieb:

afaiko schrieb:

1. Ich habe in vielen Tests gemerkt dass wenn ich z.B. die STL container und z.B. iteratoren und andere STL-Konstrukte verwende mein Code langsamer wird als wenn ich reine Arrays mit reiner "Pointer-Arithmetik" schreibe.

Kommt ganz darauf an, was für STL Konstrukte du verwendet hast. Reine ForwardIteratoren werden ganz sicher langsamer sein, als Pointer-Arithmetik. RandomAccessIteratoren könnten dagegen gleich schnell sein.
Allerdings ist klar, dass du durch reine "Pointer-Arithmetik" unter Umständen Performance gewinnen kannst. Dafür hast du auch viel mehr Fehlermöglichkeiten und bist unter Umständen auch unflexibler.

Quatsch.

Reine forward iteratoren werden verwendet, so sie algorithmisch Sinn machen. Beispielsweise bei einer std::list. Das ist eine einfach verkettete Liste. Ob ich die nun händisch mit Zeigern programmiere oder ein fertiges Template nehme macht normalerweise keinen Unterschied. "Normalerweise" deshalb, weil es denkbar ist, dass ich bei einem speziellen Problem von der reinen Lehre einer einfach verketteten Liste abweichen kann und dadurch spezifische Optimierungen implementieren kann.

Und ob die STL schneller oder langsamer als reine Zeigerarithmetik ist lässt sich so nicht beantworten, da es "die" STL nicht gibt. Es ist eine Spezifikation. Die konkrete Implementierung kann schneller oder langsamer sein, als eine konkrete Implementierung mit Zeigern.

Häufig sind Iteratoren sogar Zeiger. Und wenn ich meinen Zeiger über einen typedef definiere, wird er nicht langsamer.

[volkard]

afaiko schrieb:

1. Ich habe in vielen Tests gemerkt dass wenn ich z.B. die STL container und z.B. iteratoren und andere STL-Konstrukte verwende mein Code langsamer wird als wenn ich reine Arrays mit reiner "Pointer-Arithmetik" schreibe.

waren alle compileroptimierungen angeschaltet? falls sie aus waren, muß die stl langsamer sein, weil funktionsaufrufe drin sind.

afaiko schrieb:

1.1) Kann das sein? Hat jemand ähnliches bemerkt?

ja, aber eigentlich nur bei sachen wie new-vermeiden durch array auf dem stack und schnelles 2d-array mit compilezeitkonstanter zweierpotenz als breite. naja, vector<bool> hat glaub ich kein schnelles findNextFalse, die bäume haben evtl unnütze aufwärtszeiger, strings haben evtl unnützes cow oder small-string-optimization. nehmen wir mal die bäume. gewohnlich avl-baume. auf jeden fall höhenbalancierte bäume. wenn ich zufällig daten habe, die bestimmt zufällig verteilt sind, kann ich auch nen schnelleren unbalancierten baum nehmen. wenn abfragen habe, die clusterartige häufungen haben, kann ich nen spreizbaum nehmen.

afaiko schrieb:

2.1) Kann es also sein dass "C-lastiges C++" unter richtiger Verwendung schneller wäre als die Verwendung der STL?

auf gar keinen fall c-lastig. die stl ist schnell. in einzelfällen kann man sich container handoptimieren und schneller sein. die sind aber dann ordentliches c++ mit vielen sehr kleinen funktionen, oft mit templategefrickel, sehr selten mit inline-assembler und immer mit klassen. handoptimiertes c++ kann schneller sein als stl-lastiges c++. und ist sehr oft schneller als c-lastiges c++, weil man die erfolgreichsten optimierungen in hübsche klassen später noch einbauen kann und die algorithmen klarer und wartbarer, optimierfreundlicher vor sich hat.

also machs eigentlich nur selber, wenn du weißt, warum dert stl-code bei dir nicht voll angemessen ist.

[pumuckl]

afaiko schrieb:

Hallo,

im Prinzip habe ich 2 Fragen die aber auf die Performance gehen.

Mein Hintergrund:
ich schreibe an einem numerischen code der möglichst performant (hinsichtliche Zeit) sein soll. Priorität liegt also auf Laufzeit aber sollte nicht gerade Speicherfressend sein. Also Prio 1 = Laufzeit, Prio 2 = Speicher.

1. Ich habe in vielen Tests gemerkt dass wenn ich z.B. die STL container und z.B. iteratoren und andere STL-Konstrukte verwende mein Code langsamer wird als wenn ich reine Arrays mit reiner "Pointer-Arithmetik" schreibe.
   1.1) Kann das sein? Hat jemand ähnliches bemerkt?
   2.1) Kann es also sein dass "C-lastiges C++" unter richtiger Verwendung schneller wäre als die Verwendung der STL?

"C-lastiges C++" unter der richtigen Verwendung wird auf jeden Fall schneller sein als STL unter suboptimaler Verwendung Die STL unter der richtigen Verwendung andererseits wird nicht besonders langsamer sein als C-lastiges C++.

2. Ich stolpere immer wieder über die boost-libs. Nun weiß ich dass da eine Menge Leute dran sitzen. Und boost ist so wie ich bis jetzt weiß die vorimplementierung für eine neue C++ Version.
   2.1) Blödsinn oder stimmt das?

Eher Blödsinn. Die boost-Bibliotheken bauen rein auf C++98 auf, können also nicht für sich beanspruchen, eine Vorimplementierung oder was auch immer von C++0x zu sein. Allerdings werden ein paar der Bibliotheken (aber bei weitem nicht alle) in den neuen Standard übernommen. Genauer gesagt in die neue Standardbibliothek. Steht aber auch auf der boost-Seite.

2.3) Was ist denn aber dann der Sinn der boost-libs? Schneller zu sein als die gewöhnlihce STL?

nein. Die Boost-libs sollen die STL nicht ersetzen sondern ergänzen. Steht aber auch auf der boost-Seite.

2.4) Kann man die boost-libs auch verwenden indem man nur header includiert? Also nicht zwinged immer gegen die lib linken muss beim kompilieren?

Ja, die meisten libs sind "header only". Steht aber auch auf der boost-Seite.

[afaiko]

hmm...ich bin jetzt im zwiespalt bzw. durcheinander...ob stl+divere libs (z.B. boost) oder alles selber über pointer zu schreiben...

[Shade Of Mine]

afaiko schrieb:

hmm...ich bin jetzt im zwiespalt bzw. durcheinander...ob stl+divere libs (z.B. boost) oder alles selber über pointer zu schreiben...

STL

Die Frage stellt sich garnicht.

Denn wenn du feststellen solltest dass das Performance Problem wirklich die Datenstrukturen der STL sind, dann schreib dir halt passendere (und du kannst den Client Code gleich lassen).

idR sind performance Probleme mit der STL aber nur Einstellungen am Compiler - zB weil mit Debug Code kompiliert wurde oder sonstige Sicherheitschecks gemacht werden.

[afaiko]

naja....einfach nur gleich STL machen ist ja nicht so - stelle dir vor ich merke dass meine Container bzw. das iterieren auf meinen containern oder sonstwas langsam wäre nachdem ich alles gecodet und geprofiled habe. Und jetzt im gesamten code meine datenstrukturen zu ändern nur weil mein container zu langsam ist bzw. die methoden die darauf laufen das wäre doch blödsinn oder?

Allerdings bleibt einem ja nix anderes übrig...man weiß ja im vornherein nicht was einen erwartet...

[Nexus]

Ich würde dir raten, ein bisschen herumzuexperimentieren, bevor du dich an ein grosses Projekt wagst und möglicherweise viel Aufwand für nichts hast.

Teste unterschiedliche STL-Container mit allen Optimierungen im Release-Modus, ohne irgendeine Laufzeitumgebung zu starten. Benutze einen Profiler wie AMD CodeAnalyst, um herauszufinden, wo die Schwachpunke liegen. Wenn es drin liegt, kannst du auch mehrere STL-Implementierungen vergleichen. Aber grundsätzlich bist du mit der Standard Template Library wohl auf der besseren Seite. Falls sie sich doch plötzlich als langsam erweisen sollte, kannst du die Container auch leicht ersetzen, was umgekehrt nur möglich ist, sofern du dich genau an die Schnittstelle hältst.

Wenn du selbst etwas programmierst, würde ich das nicht C-mässig machen. Vielleicht intern schon etwas Low-Level, damit gewisse Optimierungen möglich sind, aber nach aussen schön gekapselt und generisch durch Templates, sodass du das auch sauber anwenden kannst.

[volkard]

afaiko schrieb:

naja....einfach nur gleich STL machen ist ja nicht so - stelle dir vor ich merke dass meine Container bzw. das iterieren auf meinen containern oder sonstwas langsam wäre nachdem ich alles gecodet und geprofiled habe. Und jetzt im gesamten code meine datenstrukturen zu ändern nur weil mein container zu langsam ist bzw. die methoden die darauf laufen das wäre doch blödsinn oder?

doch, das ist völlig ok.
allerdings mußt du den code von anfang an so bauen, daß du die datenstrukturen auch später mit überschaubarem aufwand austauschen kannst. das kannste auch als maß nehmen, ob du die funktionalitäten richtug trennst. wenn du nachher nix austauschen kannst, ist liskov sehr traurig.

[Nexus]

afaiko schrieb:

Und jetzt im gesamten code meine datenstrukturen zu ändern nur weil mein container zu langsam ist bzw. die methoden die darauf laufen das wäre doch blödsinn oder?

Ich würde so was machen:

#include <map>
typedef std::map<MyClass> ClassMap;

// verwende im Projekt das Typedef

Nun kommst du nach ernsthaftem Profiling zu dem Schluss, dass eine eigene Implementierung schneller ist. Da du ein weiser Programmierer bist, hat deine eigene Containerklasse ein STL-konformes Interface. Nun musst du im Code genau zwei Zeilen abändern, nämlich:

#include <SuperMap.hpp>
typedef SuperMap<MyClass> ClassMap;

// verwende im Projekt das Typedef

Praktisch, oder? Du musst dir auf diese Weise keine Gedanken machen. Programmier zuerst mit der STL, allfällige Anpassungen sind dann später leicht realisierbar.

[afaiko]

ok...das ist interessant. ich denke darüber nach und danke euch schonmal für eure erfahrungswerte/Ideen.

[maximAL]

[quote="tntnet"]

Dravere schrieb:

Beispielsweise bei einer std::list. Das ist eine einfach verkettete Liste.

Ist sie nicht

[unskilled]

afaiko schrieb:

naja....einfach nur gleich STL machen ist ja nicht so - stelle dir vor ich merke dass meine Container bzw. das iterieren auf meinen containern oder sonstwas langsam wäre nachdem ich alles gecodet und geprofiled habe. Und jetzt im gesamten code meine datenstrukturen zu ändern nur weil mein container zu langsam ist bzw. die methoden die darauf laufen das wäre doch blödsinn oder?

Allerdings bleibt einem ja nix anderes übrig...man weiß ja im vornherein nicht was einen erwartet...

was machst du denn, dass du dann alles umschreiben musst?
normalerweise sollte die schnittstelle schon gleich sein (iterator / op[] / ... - und das kannst du auch selbst ganz einfach machen - selbst mit nem c-array, das du nur einfach in ner klasse wrappst...

wenn du das richtig machst, musst du später nur ein typedef und das include ändern...

bb

edit: sry, hatte davor net aktualisiert -.-

[Nexus]

Im neuen Standard soll es std::forward_list geben, die im Gegensatz zu std::list einfach verkettet ist.

Ich muss sagen, bis jetzt habe ich noch fast nie die Funktialität einer doppelten Verkettung benötigt...

[Shade Of Mine]

Nexus schrieb:

Ich muss sagen, bis jetzt habe ich noch fast nie die Funktialität einer doppelten Verkettung benötigt...

dh du hast fast noch nie Elemente aus der mitte einer Liste entnommen?

[Nexus]

Shade Of Mine schrieb:

dh du hast fast noch nie Elemente aus der mitte einer Liste entnommen?

Hmm doch, stimmt. Ich hatte das meistens nur beim Vorwärts-Iterieren, und dann gar nicht mehr dran gedacht, dass beim Entfernen das vorherige Element wieder neu verknüpft werden müsste. War wohl etwas voreilig, mein Einwand...

[Dravere]

tntnet schrieb:

Quatsch.

Reine forward iteratoren werden verwendet, so sie algorithmisch Sinn machen. Beispielsweise bei einer std::list. Das ist eine einfach verkettete Liste. Ob ich die nun händisch mit Zeigern programmiere oder ein fertiges Template nehme macht normalerweise keinen Unterschied.

1. Nein, es ist keine einfach verkettete Liste.
2. Der OP redete nicht davon, dass er eine Liste selber implementiert, sondern im Vergleich zu Pointer Arithmetik. Also geht es hier um Arrays und Speicher, welcher an einem Stück ist. Natürlich kommt es wieder auf die Umstände an, also was man macht, aber deshalb habe ich ja auch "unter Umständen" hingeschrieben.

tntnet schrieb:

"Normalerweise" deshalb, weil es denkbar ist, dass ich bei einem speziellen Problem von der reinen Lehre einer einfach verketteten Liste abweichen kann und dadurch spezifische Optimierungen implementieren kann.

Was ich im übrigen auch gesagt habe. Nur habe ich es mit unter Umständen ausgedrückt und später nochmal explizit darauf hingewiesen.

tntnet schrieb:

Häufig sind Iteratoren sogar Zeiger. Und wenn ich meinen Zeiger über einen typedef definiere, wird er nicht langsamer.

Kann man so auch nicht stehen lassen. Dies ist nur bedingt der Fall und zwar nur bei Random Access Iteratoren. Deshalb habe ich auch geschrieben, dass die Random Access Iteratoren gleich schnell sein könnten.

Lies also zuerst meinen Beitrag richtig, bevor du ihn einfach als Quatsch deklarierst.

@afaiko,
Zuerst die Funktionalitäten aufbauen. Optimieren tut man meistens erst am Schluss.

Grüssli

[afaiko]

auf dem stack und schnelles 2d-array mit compilezeitkonstanter zweierpotenz als breite

Was meint volkard eigentlich mit diesem sub-satz?

[Chris++ 0]

afaiko schrieb:

auf dem stack und schnelles 2d-array mit compilezeitkonstanter zweierpotenz als breite

Was meint volkard eigentlich mit diesem sub-satz?

Statisches Array mit festen grenzen.

int array[2][4];

[afaiko]

und warum 2er Potenz? Bringt das speed oder wie?

[volkard]

ich meinte tr1::array http://beans.seartipy.com/2006/12/10/getting-started-with-c-tr1-libraries/

oder

class FastArray2d<typename Data,size_t sizey,size_t sizex>
{
   std::vector<Data> dara;
   static const size_t realsizey=MetaCalcNectPowerOfTwo<sizey>::result;
   public:
...
   Data& get(size_t x,size_t y)
   {
      return data[y*realsizey+x];
   }
};

das spart den mul-befehl im assemblercode und machts mit shift und add.