Warum welche Container und Algorithmen in der STL langsam ist

Man hört hier immer wieder, dass die Datenstrukturen und Algorithmen in der STL (resp. ihrer gängigen Implementierungen) enorm optimiert sind und es so gut wie unmöglich ist, bei diesen noch Performance rauszuholen.

Das ist falsch.

Hier Kommentare zu den Containern in der STL und allen nicht trivialen Algorithmen, die man mit ≤3 Zeilen Code selber geschrieben hätte:

Container:

vector : Ziemlich gut. Langsam kleinen Grössen, es fehlt ein small_vector in der STL. Man macht ihn besser nicht sehr gross, da es dann Schwierigkeiten gibt, zusammenhängenden Speicher zu finden. Der Wachsfaktor soll nicht immer ideal sein (nach manchen Quellen besser *1.5 statt *3), hab ich aber nie getestet.
deque : Grundsätzlich toller Container, aber die Block-Grösse ist oft zu klein bzw. nicht anpassbar, daher für Arenas ungeeignet.
list : Hat ihre Existenzberechtigung mit C++11 verloren (slice nicht O(1)).
forward_list : Kann man nichts falsch machen. Es fehlt nur eine intrusive Variante.
set/multiset/map/multimap : Das Interface (persistente Iteratoren) kommt mit einem Preis, die Container sind sehr langsam. Es gibt schnellere Alternativen: https://code.google.com/p/cpp-btree/
unordered_set/unordered_multiset/unordered_map/unordered_multimap : Ähnliches Problem hier. Schneller: https://code.google.com/p/sparsehash/
stack/queue : Eigentlich nur eine std::deque. Ich verstehe die Namenswahl der Funktionen push/back/front nicht und verwende die deque lieber direkt.
priority_queue : Gibt viele Datenstrukturen, die asymptotisch besser sind. Einige sind auch in der Praxis schneller: Link zu einem Vergleich.

Ausgewählte Algorithmen:

search : Triviale Implementierung in O(n*m). Mit wenigen Annahmen an den Typen gibt es O(n+m) Algorithmen. Boost hat da was.
sort : Zu generisch. Für ints etc. ist Radix-Sort besser (ab einer gewissen Anzahl Elemente). Für Strings z.B. Burstsort.
nth_element : Leider keine Garantie für O(n) im Standard, oft schlecht implementiert.
lower_bound/upper_bound/binary_search : Verwenden Binäre Suche, was schlecht gecached wird. Link

Sonstiges:

hash<> : Aktuell einfach nur broken.
iostreams: Langsam by Design
string: SSO ist gut, aber manchmal will man COW.

(Motivation dieses Posts: Warum verwendet ueberhaupt noch irgendjemand C?)

cooky451

dinosaur schrieb:

Man hört hier immer wieder, dass die Datenstrukturen und Algorithmen in der STL (resp. ihrer gängigen Implementierungen) enorm optimiert sind und es so gut wie unmöglich ist, bei diesen noch Performance rauszuholen.

Tut man das? Ich glaube der Wortlaut war eher: Wenn man danach fragen muss ist es höchstwahrscheinlich mehr als ausreichend.

dinosaur schrieb:

(Motivation dieses Posts: Warum verwendet ueberhaupt noch irgendjemand C?)

Wo ist da überhaupt der Zusammenhang, es ist ja nicht so als wäre der Kram in der C-Standardbibliothek irgendwie schneller implementiert. (Wie auch, das meiste gibt es gar nicht.)

Wenn eben ein Großteil der Performance an einer Datenstruktur hängt und man das schnell haben will, muss man sich was Spezielle(re)s raussuchen oder es selbst implementieren, das bleibt aber in keiner Sprache aus.

Die STL hat den Anspruch im allgemeinen Fall gut zu sein. Sobald du spezifische Details kennst geht es meistens besser.
Insbesondere im Link von binary_search steht Kram wie "Ich habe statische sets und auf meinem Rechner mit 16GB RAM und dieser Elementgröße ...". Das ist völlig out of scope für die STL.
Zu COW gibt es einen alten Artikel von Herb Sutter wo er das mal Benchmarkt und feststellt, dass es nichts bringt (bin zu faul ihn zu suchen). COW macht extrem Probleme in Verbindung mit threadsafety.

Nexus

Nicht nur performance-, sondern auch funktionalitätsmässig reicht die STL natürlich nicht für alles aus. Ist aber auch nicht ihr Anspruch, wie nwp3 sagt, kommt man im allgemeinen Fall recht weit. Boost.Container hat ansonsten schon mal recht viel Nützliches (z.B. flat_map und stable_vector ), und natürlich gibts etliche weitere Bibliotheken.

Was ist das Problem mit std::hash ?

Übrigens, IO-Streams sind nicht Teil der STL. STL != Standardbibliothek.

TNA

Wenn es darum geht zu beurteilen wie optimiert Datenstrukturen und Algorithmen in der STL sind muss man erst mal sagen welche Implementierung. Da gibt es viele und die setzen oft unterschiedliche Schwerpunkte bei der Optimierung.

Auch immer bedenken: Der meiste Code ist überhaupt nicht leistungskritisch, da zählen eher Aspekte wie Korrektheit und Wartbarkeit.

Mechanics

TNA schrieb:

Auch immer bedenken: Der meiste Code ist überhaupt nicht leistungskritisch, da zählen eher Aspekte wie Korrektheit und Wartbarkeit.

Naja, für mich zählt die Wartbarkeit von einem std::vector aber nicht. Als Benutzer wären mir Korrektheit und Performance wichtiger. Wenn z.B. Microsoft etwas mehr Aufwand hätte, den Code von STL Containern zu warten, wär mir das lieber, als weniger Aufwand für Microsoft und dafür langsamerer Code.

TNA

Mechanics schrieb:

Naja, für mich zählt die Wartbarkeit von einem std::vector aber nicht. Als Benutzer wären mir Korrektheit und Performance wichtiger. Wenn z.B. Microsoft etwas mehr Aufwand hätte, den Code von STL Containern zu warten, wär mir das lieber, als weniger Aufwand für Microsoft und dafür langsamerer Code.

Mit Wartbarkeit meinte ich eigentlich, das andere Leute eher den Code verstehen den man geschrieben hat, wenn er Standardcontainer und Algorithmen verwendet.