Ist die STD von C++ performant?
-
oder soll man lieber selber bauen?
-
Du redest Quark. Wie schnell fährt die Straßenverkehrsordnung? Oder sollte man lieber selber zum TÜV?
-
Es gibt verschiedene Implementierungen der STD und trotzdem kann der eigene Code performanter sein. Also ist es kein Quark.
Die Frage ist eher, wie wahrscheinlich das ist, dass man besseren Code schreibt als die diversen Implementierungen an der Progger sitzen, mit denen du nie mithalten können wirst.
-
Frage vom Freitag schrieb:
Es gibt verschiedene Implementierungen der STD und trotzdem kann der eigene Code performanter sein. Also ist es kein Quark.
Es ist Quark, denn du hast nach keiner konkreten Implementierung gefragt. Hugo Hackers erste C++-Implementierung hat ganz andere Performance als die spezielle Gamingimplementierung von EA hinter der tausend Mannjahre Entwicklung stecken. C++ definiert nur eine Schnittstelle, keine Implementierung.
Außerdem solltest du mal im Wörterbuch nachschlagen, wofür "STD" steht.
Die Frage ist eher, wie wahrscheinlich das ist, dass man besseren Code schreibt als die diversen Implementierungen an der Progger sitzen, mit denen du nie mithalten können wirst.
Die Frage beantwortet sich doch von selber.
-
SeppJ schrieb:
Frage vom Freitag schrieb:
Es gibt verschiedene Implementierungen der STD und trotzdem kann der eigene Code performanter sein. Also ist es kein Quark.
Es ist Quark, denn du hast nach keiner konkreten Implementierung gefragt.
Weil ich davon ausgehe, dass die Leute hier weit genug denken und nicht alles 1:1 vorgekaut haben müssen.
Hugo Hackers erste C++-Implementierung hat ganz andere Performance als die spezielle Gamingimplementierung von EA hinter der tausend Mannjahre Entwicklung stecken. C++ definiert nur eine Schnittstelle, keine Implementierung.
Von wo willst du wissen, das EA ihre eigene STD implementiert?
Ich würde mal davon ausgehen, die kaufen bei Compilerbauern ein. Vielleicht z.B. bei Intel.
Das gesparte Geld kann man dann nämlich in die 3d Engines stecken.
-
Frage vom Freitag schrieb:
Von wo willst du wissen, das EA ihre eigene STD implementiert?
Weil das eine super-bekannte Implementierung der STL ist, die oft beworben wird? Ich hätte jedenfalls gedacht, dass jemand, der von anderen Leuten verlangt
dass die Leute hier weit genug denken und nicht alles 1:1 vorgekaut haben müssen.
so weit mitdenken kann.
-
Frage vom Freitag schrieb:
Weil ich davon ausgehe, dass die Leute hier weit genug denken und nicht alles 1:1 vorgekaut haben müssen.
Mit anderen Worten: Du bist zu faul dafür, deshalb sollen Andere das Denken für dich übernehmen.
-
Die STL schreibt einige Garantien/Verwendungsmöglichkeiten vor die man meist nicht braucht, und die eine performante Implementierung (verglichen mit guten Implementierungen von API-Definitionen mit wesentlich weniger Garantien/Verwendungsmöglichkeiten) quasi unmöglich machen.
z.B. ist weder std::map noch std::unordered_map wirklich performant implementierbar. Also nicht wenn man einfach nur ne Map braucht wo man
- Key/Value Paare einfügen, nachgucken und wieder rauslöschen kann
- Mit unbestimmter Reihenfolge über alle Einträge iterieren kann
und sonst nix.Wenn man sowas braucht, muss man es anderswo suchen, oder ggf. selbst implementieren.
Ist natürlich nur ein Beispiel unter vielen.
---
Davon abgesehen kann man aber vermutlich sagen: Wenn du das fragen musst solltest du lieber die fertige STL deiner Toolchain verwenden. Die Chancen dass du es insgesamt besser hinbekommst (was Performance und Verbuggtheit angeht) sind in dem Fall eher gering.
-
SeppJ schrieb:
Außerdem solltest du mal im Wörterbuch nachschlagen, wofür "STD" steht.
Als ich mal vor Jahren in Thailand war sah ich eine Werbung für eine STD clinic.
-
hustbaer schrieb:
Die STL schreibt einige Garantien/Verwendungsmöglichkeiten vor die man meist nicht braucht, und die eine performante Implementierung (verglichen mit guten Implementierungen von API-Definitionen mit wesentlich weniger Garantien/Verwendungsmöglichkeiten) quasi unmöglich machen.
z.B. ist weder std::map noch std::unordered_map wirklich performant implementierbar. Also nicht wenn man einfach nur ne Map braucht wo man
- Key/Value Paare einfügen, nachgucken und wieder rauslöschen kann
- Mit unbestimmter Reihenfolge über alle Einträge iterieren kann
und sonst nix.Wenn man sowas braucht, muss man es anderswo suchen, oder ggf. selbst implementieren.
Ist natürlich nur ein Beispiel unter vielen.
---
Davon abgesehen kann man aber vermutlich sagen: Wenn du das fragen musst solltest du lieber die fertige STL deiner Toolchain verwenden. Die Chancen dass du es insgesamt besser hinbekommst (was Performance und Verbuggtheit angeht) sind in dem Fall eher gering.
Danke, für die erste brauchbare Antwort in diesem Thread.
-
z.B. ist weder std::map noch std::unordered_map wirklich performant implementierbar.
gerade std::map ist mit der Implementierung als Rot-Schwarz-Baum durchaus performant.
O(log(N)) für Einfügen sowie Suchen - was will man mehr?
Eine Alternative ist natürlich eine Hash Tabelle, wo du (wenn wir mal Kollisionen vernachlässigen) in O(1) suchen und einfügen kannst. Dafür braucht du halt mehr Speicher.
Bin mit std::map bis jetzt gut gefahren. Und klar, es gibt ein paar Schlaumeier die tatsächlich was eigenes in unserer Firma programmiert haben. std::map ist trotzdem um den Faktor 100 schneller. Soll heißen: so einfach ist es nicht, da was eigenes zu stricken, das die STL schlägt.Ansonsten sehe ich wenig Alternativen. Oder was fällt dir konkret für den typischen Anwendungsfall mit den Key-Value Paaren ein?
-
Frage vom Freitag schrieb:
oder soll man lieber selber bauen?
um auch auf die Ausgangsfrage einzugehen:
STL ist durchaus ok - man muss halt sinnvoll damit umgehen. Speicher neu anfordern und umkopieren der Daten ist "teuer". Das ist eines der wichtigsten Dinge die man bedenken muss, den daraus ergeben sich einige Folgerungen:
+ STL Objekte wann immer möglich per const& an Funkionen übergeben
+ bei std::vector wenn möglich bereits am Anfang die Größe festlegen statt tausende Male hintereinander push_back aufzurufen
+ nicht unnötig viele Kopien von std::string machen. Es wird dafür tatsächlich jedes Mal Speicher angefordert und kopiert.Ansonsten sei gesagt, dass STL so ausgelegt ist, das man problemlos eigene Container definieren kann. Wenn man ein paar Methoden implementiert, so kann man trotzdem viele der STL Algorithmen darauf anwenden.
Abschließend möchte ich dir als Anfänger aber STL ans Herz legen. Ich habe schon so oft mit selbst gebauten, "total tollen" Containern und Klassen arbeiten müssen. Ich kann daher sagen, dass es in fast 99% der Fälle keinen Sinn macht, irgendwas aus der STL nachzubauen, ganz einfach weil die STL Implementierung besser als die Eigenimplementierung ist!
-
gdfggdgdg schrieb:
Ansonsten sehe ich wenig Alternativen. Oder was fällt dir konkret für den typischen Anwendungsfall mit den Key-Value Paaren ein?
Sortierter
std::vector, besonders bei überproportional mehr Abfragen als Manipulationen.Auch könnte mir vorstellen, dass eine gute B-Baum-Implementierung für grössere Dictionaries etwas cache-freundlicher ist, als ein klassicher Rot-Schwarz-Baum.
Ansonsten erinnere ich mich auch noch vage an ein paar Papers über "cache-oblivious dictionaries", die auf Skip-Listen basierten.
Es gibt also durchaus Alternativen - ob die besser sind, hängt sicher von Anwendungsfall und Implementierung ab. Richtig eingesetzt, haben sie aber durchaus das Potential die meist
sehr allgemein gehaltenen Implemetierungen der Standardcontainer zu schlagen, selbst wenn man die von hustbaer erwähnten Garantien der Standardcontainer außen vor lässt.
Trotzdem sollte man "per Default" erstmal auf die Mittel der Standardbibliothek zurückgreifen, und eine solche spezielle Datenstruktur erst dann verwenden, wenn man spezifische
Performanceanforderungen hat und die Standardcontainer als Problem identifiziert hat: Alles selbst stricken ist nämlich nicht sehr produktiv, und hat oft auch keine gute Erfolgsquote
-
gdfggdgdg schrieb:
(...) Oder was fällt dir konkret für den typischen Anwendungsfall mit den Key-Value Paaren ein?
std::map ist für viele Anwendungfälle nicht optimal weil für jedes Key-Value Paar ein eigener Speicherblock angefordert wird, und die Blöcke dann mit Zeigern verkettet werden. Das heisst Overhead durch dauerndes Anfordern/Freigeben von Blöcken und Overhead durch Zeiger Verfolgen. Und meist schlechte Cache-Locality.
Natürlich steht im Standard nix davon dass man das so machen muss, aber die Garantien des Standards, z.B. was Stabilität von Iteratoren und Adressen angeht, machen eine andere Implementierung quasi unmöglich. (Davon abgesehen wird vom Standard soweit ich weiss auch nicht vorgeschrieben dass man nen Red-Black Tree verwenden muss. Es ist bloss sehr üblich es so zu machen.)
Das selbe gilt im Prinzip für std::unordered_map. Hier gibt's zwar einen kompakten Hash-Table, aber die Elemente liegen immer noch in einzeln angeforderten Blöcken. Die dann typischerweise zu Listen verkettet werden, eine pro Bucket des Hash-Table.
Gute, fertige Alternative kann ich jetzt keine empfehlen. Aber mit nem kompakten Hash-Table, der Hashes, Keys und Values direkt im Table speichert, kann man für bestimmte Anwendungsfälle relativ leicht schneller sein als std::map.
-
Frage vom Freitag schrieb:
Es gibt verschiedene Implementierungen der STD und trotzdem kann der eigene Code performanter sein. Also ist es kein Quark.
Die Frage ist eher, wie wahrscheinlich das ist, dass man besseren Code schreibt als die diversen Implementierungen an der Progger sitzen, mit denen du nie mithalten können wirst.
Jemand, der das Wort "Progger" benutzt sollte, wenn überhaupt, einfach glücklich sein mit der Standardimplementierung und seine Zeit nicht damit verschwenden zu versuchen etwas besser zu implementieren.
