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

[knivil]

Du hast ein sehr spezifisches Problem (naemlich deins), das du mit einem sehr spezifischen Programm (naemlich deins) loest. Nun hast du etwas rumgespielt mit verschiedenen Sachen (z.B. Pointerarithmetik) und bist auf Performanceunterschiede gestossen. Daraus leitest du jetzt allgemeine Aussagen ab. Leider kennen wir weder dein Problem noch dein Programm. Auch wissen wir nicht, ob du schon verschiedenen Compileroptionen (Release/Debug, -O3, -mmmx ...) ausprobiert hast oder gar welchen Compiler du benutzt. Daraus folgt: Alles ist moeglich. Wenn Performance ein Problem ist, dann nutze einen Profiler!

Meine Persoenliche Erfahrung ist, dass unordered sets etwa genauso performant wie normale sets in C++ sind. Bei Hashtables wuerde ich also eine andere Implementation nutzen (gibt genug im Netz). Das ist sehr speziell ...

[frühreife optimierung]

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.
   1.1) Kann das sein? Hat jemand ähnliches bemerkt?

der unterschied ist besonders groß wenn man im debug-mode kompiliert, weil bei deiner pointer-arithmetik vermutlich weniger sanity checks gemacht werden. falls du das noch nicht berücksichtigt hast, könnte das den unterschied zwischen beiden vorgehensweisen noch erheblich verringern.

[afaiko]

Herzlichen Dank für eure ersten Antworten.
So wie ich Dravere jetzt verstehe ist boost also eine erweiterung der STL. Um allerdings auf der sicheren Seite zu stehen was Performance angeht sollte ich (man) wohl eher auf "reine Pointerarithmetik" gehen. Mir ist natürlich klar, daß es sicher an einzelnen stellen vielleicht nur sehr sehr wenig ausmacht, vielleicht so wenig dass man es überhuapt nicht merkt und sagt man sollte eher profilen um die bottlenecks zu sehen. Allerdings habe ich vor auf richtig intensive Problemstrukturen loszugehen die im HPC Bereich angesiedelt sind und damit extrem lange dauern werden.
Deswegen auch mein Gedanke: Erst informieren - dann coden.

[afaiko]

Nur damit jetzt kein durcheinander entsteht.

Erst informieren - dann coden

heißt nur dass ich an was neuem ähnlichen schreibe...
Und als flags benutzte ich immer unterm gcc O3 bis jetzt. Auch auf den Intercompiler bin ich losgegangen.

[Dravere]

afaiko schrieb:

Um allerdings auf der sicheren Seite zu stehen was Performance angeht sollte ich (man) wohl eher auf "reine Pointerarithmetik" gehen.

Nein, das hast du falsch verstanden. Deshalb hatte ich immer "unter Umständen" hinzugeschrieben. So pauschal kann und darf man das nicht sagen.
Performance gewinnt man auch durch die sinnvolle Allokation und Verwaltung der Ressourcen. Ich würde mich nicht darauf verlassen, dass du als Entwickler dass immer besser machst als die Standardbibliothek. Es gilt hier wirklich ganz genau zu prüfen, was wo und wie schneller ist. Am besten entwickelst du zuerst mit der Standardbibliothek und womöglich auch mit Boost und klärst im Nachhinein, wo es Probleme gibt und optimierst diese dann entsprechend.

Übrigens möchte ich hier noch etwas korrigieren. STL != Standardbibliothek. Die STL von 1998, bzw. etwas davor, wurde zum Teil in die Standardbibliothek reingenommen. Die STL an sich hat sich allerdings weiterentwickelt, während der Teil, welche von der STL in die Standardbibliothek übernommen wurde, gleich blieb. Das sind also unabhängige Bibliotheken. Zudem hat die Standardbibliothek mehr Funktionalitäten als die STL.

Grüssli

[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...