File I/O : std::list oder std::vector oder std::deque ??????? (Performance)
-
Hi Leute,
vielleicht koennt ihr mir bei meiner generellen Problemstellung weiterhelfen - bin alles andere als ein STL Profi. Ich moechte aus einer Datei den Inhalt einlesen und invers wieder wegschreiben. Und zwar fuer eine ganze Menge an Files (~45 MB pro File, ca 70 in einem Schub nacheinander umschreiben)! Deshalb sollte die Implementierung einigermassen durchdacht sein. Also strings einlesen (getline) wobei die strings in der Laenge unterschiedlich sind (zwischen ca 30 und 50 Zeichen pro Zeile) und in einen Container reinpacken.Die Frage die sich mir stellt: welchen Container soll ich nehmen, welcher ist optimal ?
Soll ich LIST nehmen ? da koennte ich sofort die eingelesenen Strings immer am Anfang einfuegen und hab so von Haus aus schon eine richtig sortierte Liste die ich nur noch ausgeben muss so wie ist. Wie alloziert LIST eigentlich speicher ? Wie vector ? wie deque ? (zusammenhaengend/fragmentiert)
Oder VECTOR ? alloziert aber brutal speicher (nicht linear), soferne man nicht mit reserve() gleich von Anfang an rangeht - ansonsten kopiert vector ja rum wie bloed wenns 'zu klein wird'. Wenn ich reserve() richtig verstehe alloziert man damit aber Speicher für den Typ und nicht raw bytes. Wie soll ich also reserve in diesem Zusammenhang fuer strings verwenden, wenn ich nicht weiss wie lange die einzelnen strings sind bzw wieviele bytes ich ueberhaupt brauche? Ist das Durchsteppen mit einem reverse iterator langsamer als die normale bei list copy(.begin .end,outfile) ?
Bei DEQUE koennt ich auch am Anfang einfuegen , bei tests scheint aber angeblich zutage getreten sein dass die deallokation brutal lange dauern kann (speicherblock nicht zusammenhaengend) - bei mir wichtig da ich ja viele files bearbeite und der Speicher dauernd angefordert und wieder freigeschaufelt werden soll (naechstes file).
Beim Wegschreiben: copy(.begin .end) verwenden oder mit einem eigenen Iterator durchsteppen ?
Schon mal jemand mit etwas ähnlichem konfrontiert gewesen und hat ein wenig rumprobiert wies am effektivsten zu implementieren ist ? Waere fuer euere Hilfe wirklich dankbar!
greets,
cpplumpi
-
Kommt darauf an, was du möchtest. std::vector würd ich aber nehmen
-
Wenn man nach ISO-C++-Standard-Spezifikation geht, sollte man immer erst mal std::vector nehmen. Das ist erstmal der beste Kompromiss für einen Start in eine neue Zuk... äh egal. Jedenfalls sollte man (wenn man noch keine Idee hat!) sich die Performance seines Programms anschauen. Vielleicht reicht ja vector voll und ganz aus??? Wenn es nicht zufriedenstellend ist, kann man sich anschauen, was das eigene Programm macht unud mit Daten umgeht. Und dann kann man immer noch z.B. auf einen anderen Container-Typ umsteigen.
Zu deiner Anforderung: Du willst also im Prinzip die Daten rückwerts rausschreiben? Die einfachste programmatische Lösung wäre, einen Reverse-Iterator zu benutzen. Der macht das meines wissens: rückwerts iterieren. als anstatt begin und end, nimmst du rbegin und rend. Da brauchst du nichts an deinen Daten manipulieren.
list kannst du für dein Vorhaben vergessen, weil list für jedes element zwei Pointer braucht... also auf einem gängigen System pro Element zus. 64 bits. Denn die Daten sind nicht seuenziell!!! Und schneller kann man da auch nicht iterieren, ist sogar langsamer als ein vector.
deque ist einfach 2x vector, einer vorne, einer hinten. Ist nur komfortabler zu handhaben.
Übrigens, 45 MB sind nicht gerade wenig Daten. Bin der Meinung, das man bei der Datenmenge mit "Wartezeit" rechnen muß. Und vector und deque ist und bleibt bei sequenziellen Daten immer noch am schnellsten.
-
Würde auch zu vector raten.
Allerdings sollte man austesten, welche art der iteration die bessere ist (v<T>::iterator vs. v<T>::reverse_iterator vs. index[]).
Am kritischsten wird aber wohl das auslesen der Daten sein, das kostet einfach Zeit.
-
Ich würde einfach den gesamten Dateiinhalt in einen String schreiben (vorher mit reserve() soviel Speicher reservieren, wie die Datei groß ist) und dann mittels des reverse-iterators die Daten wieder rausschreiben.
Edit:
Oder sollen nur die Zeilen umgedreht werden?
Dann brauchst du natürlich einen Container und ich würde dann zu std::vector raten (und auch hier mittels reserve() vorher Speicher allozieren - die erwartete max. Größe kennst du ja: 45MB/30 = 1.5MB).
-
nach Lektüre einen Kurzartikels von Herb Sutter (LINK) rate ich eher zum deque, hat gegen vector beim Iterieren keine nennenswerten Performancenachteile, dafür beim Einfügen eher Vorteile, wenn man beim vector kein reserve() macht. Des weiteren kann man bei größeren Dateien die deque wie eine Art Puffer verwenden: hinten bissl was reinpushen, vorne rauspoppen, so dass man nicht die ganze Datei auf einmal einlesen muss. Ist vor allem dann nett wenn man garnicht alles braucht, so spart man sich das, ne 100.000 Zeilen Datei einzulesen wenn man nach Zeile 300 eigentlich hat was man braucht
-
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.
-
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.
