File I/O : std::list oder std::vector oder std::deque ??????? (Performance)
-
ich würd wahrscheinlich alles in einen vector einlesen und den anschließend mit nem reverse iterator wieder rausschreiben.
davon mal ab handelt es hierbei um operationen, die ausschließlich RAM und CPU belasten. das einlesen und schreiben der datei dürfte da mindestens mit faktor 10 zu buche schlagen. also steck lieber bisschen energie in das lesen und schreiben selbst
-
hustbaer schrieb:
Ich schätze jetzt werden mich gleich wieder alle hauen, aber ich würde hier "Byte klauben" gehen.
Lies die ganze Datei in einen Puffer (std::vector<char> oder std::string - ganz egal). Dann startest du beim letzten Byte und bei jedem gefundenen Zeilenumbruch schreibst du eine Zeile raus.
Wenn du das so nicht machen willst würde ich entweder eine std::dequestd::string nehmen oder einen std::vector<boost::shared_ptrstd::string > oder einen boost::ptr_vectorstd::string.
Welchen Sinn macht ein std::vector<boost::shared_ptrstd::string >? Ein std::vectorstd::string ist in jeder hinsicht besser.
-
er spart dir das sinnlose herumkopieren des inhaltes des strings, wenn dieser nicht implizit geshared ist, was auf stl-varianten leider zutrifft. das kopieren bei der nutzung von einfachen objekten dürfte hier weit mehr leistung schlucken als der unterschied zwischen list und vector. daher bitte zeiger aufs strings verwenden.
aber zum eigentlich thema: eines noch vorne weg, im prinzip ist es völlig wurscht, welchen container du nimmst, da das leistungslimit hier wohl eher in der io liegen wird.
ansonsten würde ich hier wohl auch einen vector/deque nehmen, da beide bei der menge der einfüge operationen, die du vornehmen willst, wohl das besten zeitliche verhalten zeigen. die einfüge operationen am ende sind bei beiden amortisiert konstant und der konstante teil ist deutlich kleiner als der einer liste, da nicht jedesmal ein speicher allokiert werden muss, sondern das objekt einfach abgelegt werden kann.
ich würde den vector/deque auch nicht in jedem durchlauf neu erstellen, sondern ihn immer recyclen. damit entfällt mit großer wahrscheinlichkeit die vergrößerung in einem späteren durchlauf. nachteil der ganzen sache ist aber, dass du zwischendurch wahrscheinlich ein paar mb mehr oder minder sinnlos im speicher liegen hast.
-
ghorst schrieb:
er spart dir das sinnlose herumkopieren des inhaltes des strings, wenn dieser nicht implizit geshared ist, was auf stl-varianten leider zutrifft.
Mag für eine STL-Implementation stimmen, aber soviel ich weiß nicht zwangsweise für jede STL-Implementierung.
ghorst schrieb:
das kopieren bei der nutzung von einfachen objekten dürfte hier weit mehr leistung schlucken als der unterschied zwischen list und vector. daher bitte zeiger aufs strings verwenden...
ich würde den vector/deque auch nicht in jedem durchlauf neu erstellen, sondern ihn immer recyclen. damit entfällt mit großer wahrscheinlichkeit die vergrößerung in einem späteren durchlauf. nachteil der ganzen sache ist aber, dass du zwischendurch wahrscheinlich ein paar mb mehr oder minder sinnlos im speicher liegen hast.Zum einen sind zusätzliche new/delete auch nicht performant, zum anderen: warum sollte der String dauernt kopiert werden: Er wird einmal rein- und einmal rauskopiert in seinen Anwendungsfall, sofern der Vektor mit einer sinnvollen Größe initialisiert wurde.
Und wenn du schon unbedingt mit Stringzeigern optimieren willst, kannst du gleich auf char* Pointer wechseln.
cu André
-
asc schrieb:
Mag für eine STL-Implementation stimmen, aber soviel ich weiß nicht zwangsweise für jede STL-Implementierung.
kennst du eine mit implizitem sharing von daten?
asc schrieb:
Zum einen sind zusätzliche new/delete auch nicht performant, zum anderen: warum sollte der String dauernt kopiert werden: Er wird einmal rein- und einmal rauskopiert in seinen Anwendungsfall, sofern der Vektor mit einer sinnvollen Größe initialisiert wurde.
da dieses kopieren (einmal rein und einmal raus) die hauptarbeit des programmes, das der op bauen will, ausmacht und man sie wegoptimieren kann, sollte man es auch tun.
das es im prinzip völlig sinnlos ist, da die io eh um welten langsamer ist, schrieb ich bereits..asc schrieb:
Und wenn du schon unbedingt mit Stringzeigern optimieren willst, kannst du gleich auf char* Pointer wechseln.
kann man auch machen. ist aber von der performance reichlich irrelevant. so schlecht ist die performance der stringklasse dann doch nicht.
-
Lässt sich nicht schon beim einlesen sparen?
typedef <container_nach_wahl<std::string> > container; container cont; ifstream in(argv[1]); std::string line,buffer; while(in.good()) { for(int i=0; i < 200 && std::getline(in,line);i++) buffer = line + "\n" + buffer; cont.push_back(buffer); buffer.clear(); }Setzt natürlich voraus das Stringoperationen schneller sind als push_back + iteration.
phlox
-
dass die string-operationen schneller sind, bezweifle ich, da für diese kein amortisiert konstantes verhalten für die vergrößerung garantiert ist und wenn mich nicht alles täuscht, auch in den meisten nicht implementiert ist.
es ist in der mehrheit der fälle auch so, dass die string-daten in einem zusammenhängenden array gespeichert werden. ist zwar vom standard nicht vorgeschrieben, sorgt aber dafür das anfügen an einem string meistens sehr teuer ist.
-
zunaechst einmal vielen dank fuer eure zahlreichen antworten! habe gestern noch ein bißchen recherchiert und bin auf codeproject , denke ich, fuendig geworden:
http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp
leider gottes muss man des englischen maechtig sein um den artikel lesen zu koennen aber ich denke die meisten im forum werden damit kein problem haben!
die kurzfassung: jemand wollte offenbar die unterschiede zwischen vector und deque herausfinden und hat eine testapp geschrieben und die performance dabei gemessen. der artikel ist zwar aus 2003 aber wenn sich seither nichts an der implementation von vector oder deque geaendert hat, sollte das keine rolle spielen.
ergebniss: deque schlaegt vector beim einlesen (memory alloc) soferne vector NICHT VORHER SCHON mit reserve() eingerichtet wurde. verwendet man reserve() sind beide in etwa gleich effizient. ohne reserve: vector ~43sec deque ~27.5sec (faktor 1.5)
das interessanteste experiment war experiment3 - "reclaiming memory". es zeigt das der zeitbedarf beim freigeben des speichers exponentiell zu wachsen beginnt je mehr elemente im deque container sind (je groesser er ist) - bei ca. 700000 strings in der testsuite brauchte deque ca. 50 sec zum freischaufeln, der vector aber nur rund 1.2 sec!!!!!!!
ich denke ich werds mal mit vector<string> angehen, falls ich noch zeit und lust habe probier ich das ganze dann noch mit deque aus - auf jeden fall dank nochmals an alle!
lg
cpplumpi
-
asc schrieb:
Mag für eine STL-Implementation stimmen, aber soviel ich weiß nicht zwangsweise für jede STL-Implementierung.
Die meisten Implementierungen haben aber kein CoW! Wäre laut Standard möglich, macht aber so gut wie niemand. Ein wenig Statistik sollte man mit einbeziehen, und nicht vom minimalen Optimalfall ausgehen.
asc schrieb:
Und wenn du schon unbedingt mit Stringzeigern optimieren willst, kannst du gleich auf char* Pointer wechseln.
-
Man kann den Vector auch zuvor resizen (statt reserven) und die darin angelegten leeren Strings dann (z.B. mit getline) befüllen, schon fällt das reinkopieren weg.
-
Artchi schrieb:
asc schrieb:
Und wenn du schon unbedingt mit Stringzeigern optimieren willst, kannst du gleich auf char* Pointer wechseln.
Sorry, aber ich sehe nun mal keinen Sinn darin in einen Vector in den man jeden Wert genau einmal schreibt und liest (ggf. einen vorherigen dabei überschreibt) mit einem string-Pointer (in Kombination von new/delete) zu halten wenn man sich davor schon an der string-Implementierung aufzieht.
Und nein, ich bin absolut kein Fan von char* nur sehe ich den Sinn des stringpointers in den Zusammenhang nun wirklich nicht.
cu André
-
huch. wo habe ich mich denn an der string-implementierung hochgezogen? ich habe nur erklärt, warum man das hier nicht mit normalen stringobjekten machen sollte.
btw. du wolltest noch auf stl-implementierung verweisen, die implizites sharing betreiben.
-
Mag für eine STL-Implementation stimmen, aber soviel ich weiß nicht zwangsweise für jede STL-Implementierung.
Das gilt aus einem einfachen grund für alle mir bekannten Implementierungen:
Die einzige Möglichkeit einen std::string COW zu machen wäre wenn jeder Zugriff mit [] oder dem Dereferenzieren eines Iterators eine Kopie erzwingt (ausser natürlich wenn die String-Daten schon "exklusiv" sind).
Das Problem ist dass der Operator [] von std::string sowie der Operator * von std::string::iterator eine Referenz (nicht const!) auf ein char zurückliefern müssen. (NOTE: es ist laut Standard nicht erlaubt anstelle des char ein Proxy-Objekt zurückzugeben)
Und da die String Klasse nicht unterscheiden kann ob diese Referenz auch zum Schreiben verwendet wird oder nur zum Lesen müsste sie also davon ausgehen dass geschrieben wird, und an der Stelle den String kopieren.
Die einzig mögliche COW Optimierung würde also nur dann was bringen wenn man Strings rumkopiert die nie gelesen werden, oder wenn der String zu dem Zeitpunkt wo er gelesen wird bereits der "Exklusiv-Eigentümer" der String-Daten ist.
In diesem Fall (std::vectorstd::string vergrössern) wäre das wohl so, da das Original sofort nach dem Umkopieren des Inhaltes des std::vectorstd::string zerstört wird. Im Schnitt wird ein COW String aber vermutlich langsamer sein als ein nicht-COW String (vermutlich = ich hab's nicht ausprobiert).
Was noch dazukommt: für kleine (kurze) Strings ist COW viel langsamer als SSO. Und SSO ist wesentlich einfacher zu implementieren.
All das zusammengenommen bedeutet für mich (andere mögen es anders auslegen): std::string und COW vertragen sich einfach nicht gut, zumindest nicht in der Praxis
----
Falls und wenn im nächsten Standard move Vektoren enthalten sind sieht die Sache wieder anders aus, aber bis dahin ist ein std::vector<boost::shared_ptrstd::string > oder ein boost::ptr_vectorstd::string die beste mir bekannte Lösung.
(ptr_vector ist vermutlich besser, da der Overhead des shared_ptr wegfällt)----
Nochwas: ein boost::shared_ptr<std::string const> IST im Prinzip sowas wie ein manueller COW String
-
asc schrieb:
Und wenn du schon unbedingt mit Stringzeigern optimieren willst, kannst du gleich auf char* Pointer wechseln.
Ich gehe zwar davon aus dass das nicht an mich gerichtet war, dennoch: das hatte ich als erstes vorgeschlagen
Die anderen Vorschläge (vector + shared_ptr bzw. deque bzw. ptr_vector) hab' ich einfach gemacht weil ich *weiss* dass mit den STL Implementierungen die üblicherweise verwendet werden (MS, GCC, STLport) diese 3 sinnvolle Kandidaten sind, auf jeden Fall besser als std::vectorstd::string.
OK, std::liststd::string ist vermutlich inetwa gleich schnell, das hatte ich übersehen/vergessen (ich brauche std::list so selten dass ich oft nicht daran denke, selbst wenn random access nicht gebraucht wird). Sei hiermit hinzugefügt.
-
hustbaer schrieb:
Die anderen Vorschläge (vector + shared_ptr bzw. deque bzw. ptr_vector) hab' ich einfach gemacht weil ich *weiss* dass mit den STL Implementierungen die üblicherweise verwendet werden (MS, GCC, STLport) diese 3 sinnvolle Kandidaten sind, auf jeden Fall besser als std::vectorstd::string.
Gut, habt gewonnen. Auch wenn ich mich Frage ob in diesen Anwendungsbeispiel nicht dadurch das Strings nur einmal geschrieben und ausgelesen werden müssen ein zusätzliches new/delete performancetechnisch nicht ebenso langsam ist (Werde ich vielleich irgendwann mal testen). Sofern nicht eindeutig der Flaschenhals daran hängen wird werde ich auch immer Objekte oder Smartpointer (wie von dir angegeben) rohen Zeigern vorziehen.
Was die Implementierungen eines String angeht bin ich aber dennoch anderer Meinung. Mir ist ehrlich gesagt auch voll und ganz egal wie der String im Detail implementiert ist, ich bin und bleibe ein Anhänger des Ansatzes: Programmiere immer gegen die Schnittstelle, niemals gegen die Implementierung.
cu André
