3. Speicherverbrauch std::map & Membervariablen

Speicherverbrauch std::map & Membervariablen

  • 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
  • B

    CStoll schrieb:

    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.

    Also, da muss ich mich dann wieder als doof outen. Ich nutze eclipse mit CDT. Wenn ich da auf die Definition einer deque klicke mit Strg gedrückt, dann leitet der mich weiter a eine Datei /usr/include/g++/bitsstl_deque.h
    In dieser Datei habe ich keine explizite Angabe gefunden, wieviel Speicher denn nun reserviert wird. Aber das ganze ist mir auch irgendwie eine Nummer zu heavy zum Durchsteigen. Sieht schon ziemlich krass aus 🙂

    0
  • B

    Th schrieb:

    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ß).

    Okay, dann erklär ich kurz, wieso deque (wird aber kompliziert :))

    Ich bekomme sequenziell eine große Menge von ints. Über diese gehe ich mit einem Fenster konstanter Länge drüber. Das sieht dann so aus:

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

void addInt(const int & a) {
    if (_deq.size() >= MAXSIZE) {
        _deq.pop_front();
    }
    _deq.push_back(a);
...

    Jetzt suche ich alle möglichen Sequenzen innerhalb dieser deque.
    Wenn in der also 1,2,3,4,5 drinsteht, dann erzeuge ich mit folgende neue Zahlenketten daraus:

    1,2     1,2,3     1,2,3,4     1,2,3,4,5
2,3     2,3,4     2,3,4,5
3,4     3,4,5
4,5

    Das sieht so aus:

    ... // Fortsetzung addInt()

deque<int> tdeque(11);
unsigned int pos; // pos = starting position for small interval that has to be saved

for (unsigned int i = 2; ( (i <= MAXSIZE) && (i <= _deq.size())); i++) {
    // i == size of small interval
    tdeque.clear();
    tdeque.resize(11);
    if (_deq.size() < MAXSIZE) { // check if _deq is not big enough (thats the case at beginning of program)
        pos = _deq.size() -i;
    } else {
        pos = MAXSIZE -i;
    }
    for (unsigned int j = 0; j < i; j++) {
        tdeque.push_back(_deq.at(pos+j));
    } // for
    _slidingWindowMap[tdeque]++; // if tdeque is present, inc its counter, otherwise insert it with counter set to 1
} // for

    Und diese deques (1,2 2,3 etc (sind in tdeque)) will ich in ihrer Häufigkeit zählen.

    Ich hoffe, ich habe jetzt im Code hierdrüber keine Fehler eingebaut. Ist so aus meinem Prog übernommen.

    Jetzt, wo ich das abtippe und drüber nachdenke, kann ich aber auch nicht mehr sagen, wieso ich da eigentlich deques abspeichere. Da brauch ich die Fähigkeit mit pop_front ja gar nicht...
    Hätte also auch ein Vector ausgereicht...
    Naja, gut, wenn man selbst mal über seinen Code nachdenkt 🙂

    Th schrieb:

    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...

    Gern. benja a t gmx. net

    0
  • B

    Soo, wie vermutet liegt es an dem Konstrukt

    map<deque<int>, int>

    das habe ich ersetzt duch

    map<vector<int>, int>

    und der Verbrauch von Arbeitsspeicher ist jetzt in Regionen, die ich überschauen und nachvollziehen kann.

    Mein Problem ist also gelöst. Danke nochmal an CStoll, Th und die anderen netten Helfer !!

    0
Anmelden zum Antworten