Speicherverbrauch std::map & Membervariablen

Benja_m

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

RHBaum

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

Benja_m

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.

Benja_m

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.

Th

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

Benja_m

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

CStoll

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

Benja_m

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

CStoll

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)

RHBaum

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

Ciao ...

Benja_m

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.

RHBaum

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

Th

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

Benja_m

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

Benja_m

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

Benja_m

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

Speicherverbrauch std::map &amp; Membervariablen

Speicherverbrauch std::map & Membervariablen