3. Speicherverbrauch std::map & Membervariablen

Speicherverbrauch std::map & Membervariablen

  • B

    Hi
    Bitte den Sinn mal außer Acht lassen; ist nur als Beispiel zu verstehen.

    class.h

    deque<int> _deq;
    map<deque<int>,int> _map;

    class.cpp

    void func(int a, int b, int c) {
    _deq.clear();
    _deq.push_back(a);
    _deq.push_back(b);
    _deq.push_back(a);
    _deq.push_back(c);
    map<deque<int>,int>::iterator it;
    it = _map.find(_deq);
    if (it == _map.end()) {
        _map.insert(make_pair(_deq, 1));
    } else {
        it->second +=1;
    }
}

void dest() {
    map<deque<int>,int>::iterator it = _map.begin();
    for (; it != _map.end(); it++) {
        if (it->second < 10)
            _map.erase(it);
    }
}

    Durch die Funktion func() wird in der Membervariablen _map eine Struktur aufgebaut in der gezählt wird, wie oft eine deque von ints vorkommt. Wenn sie noch nicht vorhanden ist, wiest sie eingefügt, ansonsten wird der zähler erhöht.

    Irgendwann ist die _map gefüllt und die Funktion dest() soll alle Elemente von _map löschen, die weniger als 10 Mal vorkommen.

    Meine Frage:
    Wird der Speicherplatz, den die Elemente verbraucht haben, sofort nach dem erase wieder freigegeben oder bleibt er solange belegt, bis der Destruktor von "class" ausgerufen wird (weil dann ja erst deren Membervariable _map gelöscht wird) ?

    Meinungen ?
    Dankeschön !

    0
  • C

    Afaik wird der Speicherplatz sofort an den Allocator der map zurückgegeben, wenn du erase() aufrufst. Allerdings kann es sein, daß dieser ihn erstmal zwischenlagert (und beim nächsten insert() die vorreservierten Speicherblöcke verwendet).

    Btw, dein Code dürfte zur Laufzeit abschmieren - erase() macht den Iterator ungültig, den du zum Löschen freigegeben hast, das heißt, anschließend darfst du ihn nicht mehr verwenden (und auch nicht inkrementieren). Sicherer ist es so:

    for (; it != _map.end();)
{
  if (it->second < 10)
    _map.erase(it++);
  else
    ++it;
}

    Und auch beim Einfügen läuft etwas nicht rund - end() darf nicht dereferenziert werden (und selbst wenn, dürfte it->first nicht den richtigen Schlüsselwert haben). Davon daß man in einer map<int,int> nur nach int-Werten suchen kann und nicht nach deque<int>'s, will ich gar nicht mal reden.

    0
  • B

    CStoll schrieb:

    Afaik wird der Speicherplatz sofort an den Allocator der map zurückgegeben, wenn du erase() aufrufst. Allerdings kann es sein, daß dieser ihn erstmal zwischenlagert (und beim nächsten insert() die vorreservierten Speicherblöcke verwendet).

    Okay, das würde erklären, wieso der Prozess nach dem Aufruf von dest() noch genausoviel Speicher alloquiert hat (laut linux "top") wie vorher. Natürlich sieht man das nur, wenn die Datenstrukturen entsprechen groß sind - und das sind sie bei mir. Schade. Denn mein Programm braucht ziemlich viel Speicher und ich hoffte, durch die Löschung von "unnötigem Ballast" mehr freien Speicher zu erhalten.

    CStoll schrieb:

    Btw, dein Code dürfte zur Laufzeit abschmieren - erase() macht den Iterator ungültig, den du zum Löschen freigegeben hast, das heißt, anschließend darfst du ihn nicht mehr verwenden (und auch nicht inkrementieren).

    Genau so habe ich meine STL-Referenz auch verstanden. Witzigerweise funktioniert es trotzdem. Aber ich werds nochmal ändern. War mir auch zu unsicher so.

    CStoll schrieb:

    Und auch beim Einfügen läuft etwas nicht rund - end() darf nicht dereferenziert werden (und selbst wenn, dürfte it->first nicht den richtigen Schlüsselwert haben).

    Du hast recht, auch da war ein Fehler im "Vereinfachen" unterlaufen. Wird korrigiert...

    CStoll schrieb:

    Davon daß man in einer map<int,int> nur nach int-Werten suchen kann und nicht nach deque<int>'s, will ich gar nicht mal reden.

    Das war natürlcih n Denkfehler, in meinem Programm isses richtig und oben hab ichs korrigiert.

    Danke !

    0
  • B

    so, ich habs jetzt (hoffentlich) ganz oben so korrigiert, wie es eigentlich sein müsste. den beitrag hierdrüber hab ich auch editiert weswegen ich darauf an dieser stelle nochmal hinweise ...

    0
  • C

    Benja_m schrieb:

    CStoll schrieb:

    Afaik wird der Speicherplatz sofort an den Allocator der map zurückgegeben, wenn du erase() aufrufst. Allerdings kann es sein, daß dieser ihn erstmal zwischenlagert (und beim nächsten insert() die vorreservierten Speicherblöcke verwendet).

    Okay, das würde erklären, wieso der Prozess nach dem Aufruf von dest() noch genausoviel Speicher alloquiert hat (laut linux "top") wie vorher. Natürlich sieht man das nur, wenn die Datenstrukturen entsprechen groß sind - und das sind sie bei mir. Schade. Denn mein Programm braucht ziemlich viel Speicher und ich hoffte, durch die Löschung von "unnötigem Ballast" mehr freien Speicher zu erhalten.

    Da solltest du dich mal nach systemspezifischen Funktionen umsehen, mit denen du den unbenutzten Speicher komplett wieder entsorgen kannst - dafür gibt es bestimmt nichts im ANSI-Standard.

    CStoll schrieb:

    Btw, dein Code dürfte zur Laufzeit abschmieren - erase() macht den Iterator ungültig, den du zum Löschen freigegeben hast, das heißt, anschließend darfst du ihn nicht mehr verwenden (und auch nicht inkrementieren).

    Genau so habe ich meine STL-Referenz auch verstanden. Witzigerweise funktioniert es trotzdem. Aber ich werds nochmal ändern. War mir auch zu unsicher so.

    Das nennt sich dann Glück (undefiniertes Verhalten bedeutet, daß sich der Compiler aussuchen darf, wie er reagiert - offenbar hat deiner das gelöschte Element nur als ungültig markiert und die Pointer von den Nachbarn passend umgebogen).

    PS: Das Einfügen und mitzählen kannst du dir übrigens etwas vereinfachen:

    _map[_deq]++;

    (anstelle der kompletten find() und if()-Konstruktion)

    PPS: Wenn du _deq in der Funktion soweiso jedes Mal löschst und neu auffüllst, wäre wohl eine lokale Variable günstiger.

    0
  • B

    CStoll schrieb:

    PS: Das Einfügen und mitzählen kannst du dir übrigens etwas vereinfachen:

    _map[_deq]++;

    (anstelle der kompletten find() und if()-Konstruktion)

    "Der Indexoperatir [] gibt eine Referenz auf den mit dem Schlüssel assoziierten Wert zurück." -> Wenn der Schlüssel da ist, wird bei "map[schlüssel]++" also das gemacht, was sonst it->second +=1 macht ?

    CStoll schrieb:

    PPS: Wenn du _deq in der Funktion soweiso jedes Mal löschst und neu auffüllst, wäre wohl eine lokale Variable günstiger.

    [/quote]
    Auch wahr, wenn die Variable nicht auch anderswo gelesen werden würde 😉

    0
  • C

    Benja_m schrieb:

    "Der Indexoperatir [] gibt eine Referenz auf den mit dem Schlüssel assoziierten Wert zurück." -> Wenn der Schlüssel da ist, wird bei "map[schlüssel]++" also das gemacht, was sonst it->second +=1 macht ?

    Ja, aber was noch wichtiger ist: Wenn der Schlüssel noch nicht exisitert, wird er angelegt (mit 0 als Wert) - und anschließend inkrementiert.

    0
  • B

    wie geil is das denn ? 🙂

    danke 😉

    allerdings behebt das mein problem mit dem speicherverbrauch noch nicht.
    da muss ich aber nochmal genau schauen was das nun ist und wie ich das beheben kann...

    0
  • R

    da muss ich aber nochmal genau schauen was das nun ist und wie ich das beheben kann...

    dann wirst du dich sicher ueber die Impl deiner STL freuen ^^

    Die STL benutzt fuer ihre container eigene allokatoren, der holt also speicher fuer die objecte die in ne map vector ... reinwirst nicht mit nem blanken new, sondern allokiert grosszugieger speicher und konstruiert deine objecte auf den vorher allokierten speicher ....

    d.h.u.a.

    - wenn du nen element aus ner map/set loeschst, wird das object ungueltig, der speicher nur theoretisch frei, das BS bekommt davon nicht unbedingt was mit, weil der allokator noch drueberliegt. erst wenn der den speicher wieder freigibt, was er sicherlich nich jedesmal machen wird, wuerde das BS was davon mitbekommen.

    - wenn du in ner map 1 element einfuegst, muss der allokator nicht zwangslaeufig genau 1*sizeof(Element) anfordern, sondern eher etwas mehr, dafuer das bei jedem insert ned unbedingt tun ...

    Das tut er um die unendlich vielen news und deletes zu minimieren.

    der allokator laesst sich aber ueberschreiben, der iss per template param auf ne default impl festgelegt.

    Ciao ...

    0
  • B

    ich meinte eher, welche meiner zahlreichen datenstrukturen denn am meisten elemente hat.
    daraus kann ich dann (hoffentlich) ableiten, wo der ganze speicher verbraten wird 🙂

    muss ich mir mal paar debug-ausgaben ins prog basteln.

    0
  • B

    Okay, ich kann jetzt folgendes feststellen bei mir:

    map<deque<int>, int> _map;

    Diese Map enthält NUR deques mit 2 bis 10 Einträgen. Größere gibt es nicht. Und der zweite Int-Wert ist der Zähler, wie oft die deque schon vorkam.

    Wenn ich das hinzufügen zu dieser map auskommentiere, dann ist mein Speicherverbrauch des Gesamtprogramms bei knapp 2 MB.

    Diese Map belegt bei 221592 Einträgen (sie enthält also 221592 deques und 221592 ints) allerdings stattliche 130 MB RAM.
    Mit 403483 Einträgen belegt sie 235 MB RAM.*

    Ich stelle mich mal dumm:

    221592 Einträge * 10 int (MaxLen deque) * 4 (sizeof(int)) = 8863680 Byte ~ 8,5 MB
221592 Einträge * 4 (sizeof(int)) = 886368 Byte ~ 0,8 MB

403483 Einträge * 10 int * 4 = 16139320 ~ 15,4 MB
403483 Einträge * 4 = 1613932 ~ 1,5 MB

    Zuzüglich Verwaltung. Die deque muss ja wissen, wie groß sie ist usw...
    Meinetwegen Faktor 2 (was bestimmt schon zu hoch angesetzt ist).

    Dann käme für Fall 1 ein Overhead von ~111 MB (=130 - 2*8,5 -2*0,8) dabei raus. Für Fall 2 ein Overhead von 202 MB (=235 - 2*15,4 - 2*1,1).

    Das trau ich der STL und C++ nicht zu 😉
    Also muss ich einen Denkfehler haben.

    Wo ? Ich finde ihn nicht 😞

    * Dieser Wert wird mir von "top" unter Linux angezeigt als Wert für den beanspruchten virtuellen Adressraum.

    0
  • T

    Ein paar Bytes mehr mußt du schon einrechnen:

    - jede Map benötigt für jeden Eintrag mind. 2 Zeiger (left + right)
    - der Standard-Container für deque ist vector, d.h. ein vector hat eine Kapazität, die immer größer/gleich der aktuellen Größe ist, d.h. bei 2-10 Werten werden z.B. 16 oder mehr reserviert (ruf mal die Methode capacity() vom vector (bzw. deque) auf)

    Wenn die Zeiger bei dir 4 (evtl. sogar 8 bei 64Bit-System?) groß sind,
    so sind mindestens
    4 (left)
    4 (right)
    deque:
    4 (front)
    4 (back)
    vector:
    16 * 4 + 4 (size)
    int:
    4
    --------
    88 Bytes

    88 * 221592 = 19,5 MB

    zu veranschlagen...

    Bei Kapazität von 32 (statt 16) und 8 Byte pro Zeiger kommt man dann schon auf
    304 Bytes pro Eintrag, d.h. 304 * 221592 = 67 MB

    Aber auf 130 MB komme ich auch nicht...

    0
  • B

    deque hat kein capacity(). deren größe (bzw reservierter speicherplatz) würde mich allerdings schon interessieren...

    sizeof(int) ist bei mir 4. 32Bit System -> Zeiger sind auch 4Byte

    0
  • C

    Th schrieb:

    - der Standard-Container für deque ist vector, d.h. ein vector hat eine Kapazität, die immer größer/gleich der aktuellen Größe ist, d.h. bei 2-10 Werten werden z.B. 16 oder mehr reserviert (ruf mal die Methode capacity() vom vector (bzw. deque) auf)

    Das ist (sorry) Käse - deque hat eine ganz eigene Implementation, die völlig unabhängig von vector sein dürfte. Allerdings kannst du trotzdem davon ausgehen, daß sie sich den Speicher in größeren Blöcken besorgt (wie groß, kannst du nicht beeinflussen - aber du solltest dich mal durch den Header <deque> durcharbeiten, da solltest du auch die genaue Arbeitsweise der Klasse verstehen ;)).

    0
  • B

    Hast du denn eine Idee, wo der Speicher verbraucht wird ?
    Ich bin da ratlos 😞

    0
  • C

    Wie gesagt, schau dir mal den Header <deque> an - irgenwo dort drinn dürfte stehen, wie groß die Speicherblöcke sind, die eine Deque jeweils am Stück anfordert.

    Btw, wenn du weißt, wie groß deine Felder (maximal) werden, könntest du auch eine Array-Klasse mit konstanter Größe verwenden:

    template<typename T,size_t N>
class Array
{
private:
  T data[N];
public:
  T& operator[](size_t i) {return data[i];}
  ...
};

    (entweder selber schreiben oder etwas warten - im dritten Teil meiner STL-Serie kommt so eine Klasse vor)

    0
  • R

    Mal ne ganz andere (naive) Frage, wie misst du denn den Speicherverbrauch deines Progs ?

    Ciao ...

    0
  • B

    RHBaum schrieb:

    Mal ne ganz andere (naive) Frage, wie misst du denn den Speicherverbrauch deines Progs ?

    Ich arbeite unter Linux. Da gibts auf der Konsole bash ein Tool names top.
    Das zeigt dir diverse Daten zu laufenden Prozessen an. Unter anderem auch, wieviel Speicher reserviert ist.

    0
  • R

    Bin in Linux nich ganz so fit ... deswegen solltest dich da mal naeher erkundigen wie die speicherverwaltung da funzt ...

    top zeigt dir gleub ich den gesamtspeicherverbrauch deines prozesses an ...
    zum cashen und optimieren von prozessen zieht dein BS aber immer mehr speicher noch hinzu ... die festpladde generell wird ja auch gecacht, iss nur die Frage ob das dann im Prozessraum deines Progs laeuft ....

    zum testen wuerd ich mal die container zwar anlegen, aber beim befuellen statt dem anhaengen das erste lelement immer ueberschreiben, so dass die container nie gross werden, und dann mal den speicherverbrauch messen um nen vergleichswert zu haben ...

    Bessere und genauere infos bekommst aber mit speziellen tools zur optimierung / kontrolle des speichers ... valgrind z.b. vielleicht solltest das mal ausprobieren ...

    Ciao ...

    0
  • T

    @CStoll: Stimmt, hatte mich mit 'queue' vertan ...

    Aber die Frage ist sowieso, ob hierfür eine deque benutzt werden sollte (da diese nur zusätzliche Vorteile beim Anfügen an die erste Position bringt - gegenüber einem vector).

    Und stimme dir zu: wenn die Größe von vornherein feststeht, dann einfach ein konstantes Array aufbauen (ist schneller, da nicht immer wieder reallokiert werden muß).

    Habe mal bei der MSVC Implementation nachgeschaut:
    die deque verwendet intern auch wieder eine map...

    P.S: Ich habe auch eine eigene Array-Klasse mit maximaler Größe (bzw. 2, da eine die max. Größe als Template-Parameter nimmt, die andere als Parameter im Konstruktor).
    Bei Bedarf verschicke ich sie gerne...

    0
Anmelden zum Antworten