C++ shrink_to_fit riskant?

[T_55]

Hallo,

kurze Frage zu shrink_to_fit
https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

Kann es sein, dass shrink_to_fit kurzfristig einen erheblichen Speicherverbrauch verursacht und so zum Risiko wird bei vectoren die viel vom RAM belegen?

Anwendung:
Mit emplace_back() nach und nach vector füllen bis unveränderbarer Zustand erreicht wird. Danach rufe ich shrink_to_fit auf.
Manchmal wird ein vector neu befüllt dann clear(). Danach rufe ich auch shrink_to_fit auf.

Da das Programm immer wieder abgeschmiert ist, habe ich mal den RAM Verlauf vom OS betrachtet und gesehen, dass es extreme Sprünge in der Speicherauslastung gibt die aber nur als ganz kurzer Sprung auftreten. Meine Vermutung wenn der RAM zu 80% ausgelastet ist durch stark befüllte vectoren ist dies vermutlich der Grund für den Absturz weil dann in dieser Sekunde der verfügbare RAM nicht mehr ausreicht.
Ich habe shrink_to_fit auskommentiert und scheinbar ist das Problem weg. Offenbar steckt hinter dem shrink_to_fit irgendwie ein swap mit sich selbst ist das korrekt? Wird dabei ggf dann kurzfristig der vector komplett kopiert also verdoppelt sich dessen Speicherauslastung? Das würde auf jeden Fall die Sache erklären.

Man sagt clear() erase() gibt den Speicher nicht unbedingt frei.
Aber auch nach einer Reihe emplace_back() oder push_back() soll mehr Speicher reserviert werden als immer nötig.
Daher galt für mich shrink_to_fit immer als Standartzeile nach großen Befüllungen oder nach dem löschen. Bisher konnte ich aber nicht feststellen, dass merklich zuviel Speicher verbraucht wird ohne shrink_to_fit.
Kann es sein, dass shrink_to_fit in Wirklichkeit eher kontraproduktiv ist und man sich wie oben eher das Risiko eines Crashs ins Boot holt?

 

[tollertyp]

If reallocation occurs, all iterators, including the past the end iterator, and all references to the elements are invalidated. If no reallocation takes place, no iterators or references are invalidated.

Ergo kann eine Neu-Allokierung von Speicher erfolgen und vermutlich in der Dimension, die gesamte Menge aufnehmen zu können.

Was wird denn in dem Vektor gespeichert? Einfache Datentypen, Zeiger oder komplexe Datenstrukturen?

 

[marcOcram]

Ich bin kein C++-Experte aber wenn ich mir Dokumentation anschaue, wird dort gesagt, dass shrink_to_fit() ggf. eine Re-Allokation durchführt.
Das führt meines Erachtens dazu, dass passender Speicher für die Anzahl der Elemente angefordert wird, kopiert wird und der vorherige Speicher freigegeben wird. Deswegen auch der Hinweis, dass alle Referenzen und Iteratoren bei einer Re-Allokation ungültig werden.

 

[Revan1710]

Beim Arbeiten mit Vektoren kommt es regelmäßig zur Re-Allokation und dadurch kurzfristig zu höherem Speicherbedarf. Also auch, wenn du einfach mit push_back ein neues Element hinzufügst kann es sein, dass an der aktuellen Speicherposition nicht mehr genügend frei ist und der ganze Vektor dann in eine andere Stelle im Speicher verschoben wird.

Ich glaube nicht, dass shrink_to_fit den Absturz versursacht. Vermutlich hast du noch einen Zeiger auf die alte Position im Speicher oder einen Iterator, die nach einer Re-Allokation ungültig geworden sind.
Ohne shrink_to_fit hast du wohl einfach Glück gehabt, dass noch keine Re-Allokation stattegefunden hat.

 

[Blublah]

Wie die Vorredner schon ausgeführt haben, ist shrink_to_fit eher copy_to_fitting (innerhalb des vectors), wo eben im ungünstigsten Fall, kurzfristig fast das doppelte an Speicher allokiert wird.

 

[benneq]

wo eben kurzfristig fast das doppelte an Speicher allokiert wird.

Im Worst Case. Aber den sollte man natürlich immer vor Augen haben.
(Im Best Case kann auch ein Vektor der Größe 0 rauskommen.)

EDIT: Hast du den kleinen Nebensatz "wo eben im ungünstigsten Fall" nachträglich dazu geschrieben, oder hat mein Gehirn es tatsächlich vollbracht, mitten im Satz 5 Wörter zu überspringen, ohne es zu merken?

 

[T_55]

Ok wenn diese Neu-Allokierung tatsächlich zu eine zusätzlichen Kopie führen kannn also eine exakte kurzfristige Verdopplung des Speicherbedarfs, dann erklärt das den Absturz. Denn das sind nicht selten 10GB+ und wenn von 36GB RAM schon 30GB voll sind ist klar das es zu knapp wird.

Was wird denn in dem Vektor gespeichert? Einfache Datentypen, Zeiger oder komplexe Datenstrukturen?

der Vector hat ein Struct mit 3 floats. Also 4+4+4 Byte

 

[tollertyp]

Und die Struktur hat dann auch nur 12 Bytes? (Kannst ja mal mit sizeof testen)
Dann dürfte man Zeigern nix sparen können...

Also eventuell müsstest du vielleicht einen für deine Ansprüche optimierten Vektor-Typen verwenden? (Nicht dass ich mich da auskennen würde)

 

[T_55]

Und die Struktur hat dann auch nur 12 Bytes? (Kannst ja mal mit sizeof testen)

Ja sizeof gibt genau 12 aus.

Grundsätzlich muss man wohl im Hinterkopf haben, dass bei den Containern da mal was vom RAM höher springt als eigentlich benötigt. Hab mich da einfach zu stark am Limit bewegt. shrink_to_fit ist daher wenn es knapp wird mit Vorsicht zu genießen. Vermutlich kann sowas auch bei emplace_back etc passieren allerdings in meinem RAM Verlauf ist nur shrink_to_fit als "Extrem" zu bezeichnen, im normalen emplace_back Verlauf ist es eigentlich nur eine ganz glatte steigende Kurve.

 

[benneq]

Grundsätzlich muss man wohl im Hinterkopf haben, dass bei den Containern da mal was vom RAM höher springt als eigentlich benötigt.

Wenn die Container immer passend wären, dann müsste bei jedem(!) push neuer Speicher angefordert werden und alle Daten rüberkopiert - weil ja nach jedem push der Vektor wieder zu klein wäre.
Je nach Implementierung werden solche Container beim Erreichen der Grenze zwischen Faktor 1,25 und 2,0 vergrößert, damit etwas Luft ist und man diesen Kopiervorgang möglichst selten durchführen muss.
Wenn du vorher schon weißt, wie viele Daten du haben wirst, kannst du ja auch direkt den Vector in passender Größe anlegen. Wobei man dann natürlich auch einfach ein normales Array nehmen kann, wenn man die Zusatzfunktionen von Vector nicht braucht

 

[BlackMark]

Wenn dein Programm crashed, solltest du einen Debugger verwenden um herauszufinden wo und warum dein Programm crashed. Wirft shrink_to_fit ein std::bad_alloc? Oder segfaultet dein Programm, weil shrink_to_fit einen Iterator invalidated?

Im Allgemeinen ist shrink_to_fit nicht kontraproduktiv, sofern du es richtig verwendest, und dir bewusst bist, dass das ein non-binding request ist. shrink_to_fit darf auch ein no-op sein, oder wie schon erklärt resizen und dadurch ca. Faktor 2 an Speicher brauchen.

Wenn möglich, solltest du aber reserve verwenden um die richtige Capacity zu reservieren. Zum einen ist das schneller, weil du dir die ganzen reallocs sparen kannst, zum anderen musst du den Vector danach nicht shrinken. Am RAM Limit zu arbeiten ist aber immer problematisch, weil in C++ ganz viele Sachen passieren können, die nicht offensichtlich sind. push_back kann resizen und braucht dadurch kurzzeitig doppelt so viel Speicher, fehlende Copy-elision ebenfalls, und das ist auch abhängig der Optimierungen des Compilers.

Gruß
BlackMark

 

[T_55]

Vorher ist nicht bekannt wie groß exakt der Container wird daher emplace_back.

Hab das shrink auch mal in ein try catch getan, da wurde aber nichts gecatched.
Mit Debuggen hab ich nicht viel Ahnung, probiere mal einen Tracepoint (qt) in der Zeile vom shrink. Das Einlesen dauert im Debug so unglaublich lange, versuche trotzdem nochmal den Fehler zu reproduzieren...

 

[BlackMark]

Hab das shrink auch mal in ein try catch getan, da wurde aber nichts gecatched.

Ist dein Programm denn gecrashed? Vielleicht fliegt die Exception ja an einer anderen Stelle, oder es ist ein Segfault. Normalerweise sollte dir deine IDE das sagen können.

Das Einlesen dauert im Debug so unglaublich lange, versuche trotzdem nochmal den Fehler zu reproduzieren...

Zum Debuggen ist nicht notwendigerweise ein Debug Build notwendig. Du kannst auch einen Release Build debuggen. So simple Sachen wie unhandled Exceptions und/oder Segfaults solltest du auch ohne Probleme mit einem Release Build finden können.

Gruß
BlackMark

 

[benneq]

Du kannst auch einen Release Build debuggen. So simple Sachen wie unhandled Exceptions und/oder Segfaults solltest du auch ohne Probleme mit einem Release Build finden können.

Oder den Klassiker benutzen: In jeder zweiten Zeile eine Konsolenausgabe einbauen, die aktuellen Variablen ausgeben und schauen wo es crasht. Klingt nicht sonderlich professionell, aber ist extrem einfach, schnell und verdammt effektiv - ganz besonders dann wenn man keinen Debugger hat (oder will... PHP hust).

 

[kuddlmuddl]

Zumindest in der main tu ich immer alles, was danach so kommt in einen try mit catch und std::cerr << e.what() << std::endl;
Das hilft zwar nur begrenzt die Stelle zu finden aber zumindest sind dadurch exceptions wenigstens ETWAS besser als segfaults

shrink_to_fit ist wohl vor allem für usecases, wo man Vectoren mal sehr stark füllt und dann aber wieder um sehr viele Elemente bereinigt.
Wenn man sich nur sorgen macht, dass ein emplace_back() für zu viele Elemente allokiert hat, dann ist das etwas ungewöhnlich glaube ich. Hab noch nie gesehen, dass jemand das aktiv einsetzt.

Hört sich nicht gut an, wenn du 30GB große Vectoren im RAM aufbaust.. kann man dir evtl irgendwie anders helfen?
Hatte mal nen relativ intelligent geschriebenen Software-Cache gesehen, der nur O(1) Ram verbraucht und ähnlich wie Hardware-Caches (Cachelines) also feste Chunks vorläd von der Platte. (Multithreaded im Hintergrund in der Nähe der Indizes, wo man read-oder write access macht)
Aber eigtl is eher die Frage: Musst du wirklich SO VIELE Daten während eines Programm-Laufs verfügbar halten? Evtl gibts für deinen Algo auch ne deutlich Speicher-sparende Alternative, weil zB die History von Ergebnisse eigtl garnicht mehr benötigt wird zukünftig. Oder sind Dinge Redundant? Und brauchst du wirklich genau die Datentypen, die du millionenfach verwendest? Zur Not kann man auch nachdenken zB uint8_t oder 16 zu nutzen, um einen relevanten Wertebereich abzudecken statt eines 32bit floats/integers. Das machts aber natürlich langsamer in der Verwendung.

 

[T_55]

Ja wie vermutet war das shrink_to_fit die Ursache bzw eher der Auslöser denn die Ursache war einfach zuwenig Ram bzw zu viele Daten. Mit etlichen Konsolenausgaben schön nummeriert ist tatsächlich mein aktueller Weg sowas aufzudecken
Wegen SO VIELE Daten, ja das ist tatsächlich viel aber kommt durch die Summe vieler die ich dann parallel verarbeite und das auch redundant. Die Lösung war bereits eingebaut, hab schon länger ein RAM Limiter der ab einer Schwelle ungenutzte alte Daten freigibt, dieser war viel zu knapp eingestellt weil ich nicht von so großen Speichersprüngen ausgegangen bin. Jetzt weiß ich ja, dass das zu den Container dazugehört und lasse bereits bei 50% also 16GB säubern. Alternative für Zukunft wäre eine PCIe SSD holen und von dort direkt durchschleifen aber aktuell sind die Datenmengen (noch) deutlich günstiger auf einer HDD aufgehoben.
Will mich bald aber auch mal zum schnelleren Laden mit binärer Speicherung beschäftigen und auch zum Speicher sparen mit Komprimierung, dafür mach ich aber die Tage mal ein neuen Thread auf.

 

[firespot]

Ein gerne übersehener Container ist std::deque. Das konkrete Verhalten bzgl. Speicheralloziation beim Vergrößern eines std::deque ist zwar implementationsabhängig, aber die Chancen sind exzellent dass in Summe weniger RAM gebraucht als wenn ein bestehender std::vector mit vielen Elementen neu alloziieren muss (sei es wegen push_back / emplace_back, oder shrink_to_fit etc.).
Zitat von https://en.cppreference.com/w/cpp/container/deque:
"The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location. On the other hand, deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++)."

std::deque bietet auch random-access an, aber im Gegensatz zum vector liegen die Elemente nicht in einem kontinuierlichen Speicherbereich (daher KEINE Kompatibilität zu C-Style arrays !)