✔ [C++][STL] vector::push_back() ist sehr langsam in Schleife

[Onkel Schuppig]

Hallo ihr,
ich habe große ASCII-Dateien, die nur formatierte Zahlen enthalten. Diese lese ich mit einer Schleife in einen std::vector ein, ganz simpel mit push_back().
Das ganze dauert unakzeptabel lange. Offenbar wird ständig der ganze Vektor umkopiert an eine neue Adresse.
Was kann man tun? Der Allocator könnte ruhig 20000 Elemente am Stück reservieren.
Übrigens habe ich das gleiche Problem bei std::set::insert()

Gruß OS

 

[Kachelator]

Du kannst mit meinVector.reserve( 20000 ); schon vorher einmalig genügend Platz zur Verfügung stellen. Auch wenn der vector noch gar keine Elemente enthält, arbeitet er dann schon mit einem entsprechend grossen Speicherbereich, so dass innerhalb der Schleife nicht mehr alloziiert und umkopiert werden muss. Wenn du es ausprobierst, schreib doch bitte mal, wieviel schneller es dann läuft; das würde mich interessieren.

Beim std::set kann man so leider nichts ändern, weil das (normalerweise) als Baum aufgebaut ist. Da musst du anders optimieren.

 

[uhu01]

Hy!

Im vorhinein Speicher zu reservieren sollte mit reserve funktionieren.

EDIT: Zu spät, anscheinend etwas zu lang gesucht

mfg
uhu01

 

[Onkel Schuppig]

Mein Grundaufbau ist folgender:

struct A {
  std::vector<int> vec1;
  std::vector<int> vec2;
};

using namespace std;
void f() {
  vector<A> vec_main;

  while (bedingung1) { 
    vec_main.push_back(A);   // <-- 90% der CPU-Zeit werden HIER verbraucht!
  
    while (bedingung2) {   // wird hunderttausendfach ausgeführt
      A& r = vec_main.back();
      r.vec1.push_back(zahl);
      r.vec2.push_back(nochne_zahl);
   }
  }
}

Ich habe nun aufwändige Zeitmessungen gemacht. Überraschung: Nicht die Erzeugung von A::vec1 und A::vec2 nimmt die meiste Zeit in Anspruch, sondern der Befehl vec_main.push_back(A()). Das ist umso erstaunlicher, als die äußere Schleife nur ca. 20 mal durchlaufen wird.

 

[thooomy]

mmh vielleicht liegts ja an deiner container struktur ... ?

du erstellst einen Vektor der ein Strukts aus 2 (offenbar sehr grossen) Vektoren enthält, wenn ich das richtig gelesen hab... hatte auch mal solche Sachen bei dem ich STL Container etwas überstrpapziert hab (2fach verschachtelte lists) und ähnliche probleme - versuch mal deine container zu vereinfachen (z.b. mit 2 maps die über ihre keys miteineander verkoppelt sind ? ).. was bessres fällt mir da auch nicht ein
(aber es mag ja leute geben die wissen mehr als ich.....)

 

[Onkel Schuppig]

Ich habe mal etwas mit vector::reserve() und vector::capacity() herumgespielt.
Jetzt blicke ich VOLL durch!

Wenn ich vec_main.reserve(10) mache, läuft die äußere Schleife bis zum 10. Durchlauf schnell durch.
Beim 11. push_back(A) passiert aber folgendes:
Der Vektor vec_main wird um 50% vergrößert. Das heißt, es wird ein neuer Speicherbereich von 1,5-facher Größe angefordert.
Danach wird der gesamte Inhalt des alten Bereichs in den neuen kopiert, wahrscheinlich sogar mittels hunderttausender Copy-Constructors.
Zum Schluß wird der alte Bereich mittels (wahrscheinlich hunderttausender Destruktoren) gelöscht, was auch sehr lange dauert. DAS sind die Zeit- und Speicherfresser schlechthin.

Eine Lösung habe ich auch schon: vec_main wird als "list" statt "vector" implementiert, so entfällt dieses Umkopieren im Speicher.
Habe es schon ausprobiert. Das Programm geht jetzt ab wie Schmitz Katze!

Danke für die Anregungen, Jungs!