liste memory leak

Hi, ich setzte mich zur Zeit mit Listen auseinander und versuche, beim Löschen den Speicher wieder freizugeben.

Ich habe mit vielen Beispielen vergleichen und finde den Fehler nicht.

Oder ist es normal, dass im Taskmanager die Speicherauslastung des Prozesses nach dem Löschen nicht sinkt

So lautet mein Code:

// Items hinzufügen

	node* new_item;

	while(size > listsize)
	{
		new_item = new node;
		new_item->next = head;
		head = new_item; // Neues Element zum Kopf der Liste machen
		listsize++;
	}

        // Items löschen

	while(size < listsize)
	{
		node* del_item = head;
		head = del_item->next;
		delete del_item;
		listsize--;
	}

volkard

Alle wieder wegmachen geht doch so, oder?

// Items hinzufügen

	node* new_item;

	while(size > listsize)
	{
		new_item = new node;
		new_item->next = head;
		head = new_item; // Neues Element zum Kopf der Liste machen
		listsize++;
	}

        // Items löschen

	while(0 < listsize)
	{
		node* del_item = head;
		head = del_item->next;
		delete del_item;
		listsize--;
	}

unskilled

daniel1984 schrieb:

Oder ist es normal, dass im Taskmanager die Speicherauslastung des Prozesses nach dem Löschen nicht sinkt

japp - es lohnt sich nicht, nach dem freigeben jedes einzelnen wortes, dem OS den speicher dafür wiederzugeben...

bb

@Volkard: Ja, das stimmt. Die Listengröße soll jedoch dynamisch angepasst werden. Ohne Zusammenhang mit dem Rest ist das aus meinem Code-snippet natürlich nicht erkennbar.

@unskilled: Liegt es daran, dass es eine Struct-Liste ist? Beim löschen von dynamischen int Arrays zB wird neben dem Prozess die Speicherauslastung exakt auf den ursprünglichen Wert reduziert.

volkard

Der Speicher wird gelöscht. Dein Code sieht auch gut aus. Vermutlich würde er allein gehen.
Vielleicht ist es sowas:

node* new_item;

    while(size > listsize1)
    {
        for(int i=0;i<1000;++i)
        {
           new_item = new node;
           new_item->next = head1;
           head1 = new_item; // Neues Element zum Kopf der Liste machen
           listsize1++;
        }

        new_item = new node;
        new_item->next = head2;
        head2 = new_item; // Neues Element zum Kopf der Liste machen
        listsize2++;
    }

        // Items löschen

    while(0 < listsize1)
    {
        node* del_item = head1;
        head1 = del_item->next;
        delete del_item;
        listsize1--;
    }

Hier werden je 1000 Knoten in die Liste1 gestopft und einer in die Liste2. Da kannst Du dann fein 10 Millionen Knoten in Liste1 tun (nebenbei 10000 in Liste2).
Dann kannst Du alle Knoten aus Liste1 löschen aber trotzdem bleiben auf jeder 64k großen Speicherseite, die man sich vom Betriebssystem geholt hat, ein oder zwei Knoten aus Liste2 leben. Damit kann die ganze Speicherseite nicht freigegeben werden.

unskilled

daniel1984 schrieb:

@unskilled: Liegt es daran, dass es eine Struct-Liste ist? Beim löschen von dynamischen int Arrays zB wird neben dem Prozess die Speicherauslastung exakt auf den ursprünglichen Wert reduziert.

Nein - es sollte einzig und allein von der größe und "fragmentierung"(kein plan, ob man das hier auch so nennen kann) des speichers liegen...
Allerdings ist natürlich nirgendwo festgeschrieben, dass das wirklich so sein muss, wie ich es dir gerade erzähle...

bb

ich sollte erwähnen, dass an "size" immer ein Wert übergeben wird.

Die Elemente werden tatsächlich entfernt, nur der Speicherverbrauch sinkt nicht. Das ist nicht so gut, da die Liste ständig geresized wird und das mit nicht wenigen Knoten

unskilled

daniel1984 schrieb:

ich sollte erwähnen, dass an "size" immer ein Wert übergeben wird.

Die Elemente werden tatsächlich entfernt, nur der Speicherverbrauch sinkt nicht. Das ist nicht so gut, da die Liste ständig geresized wird und das mit nicht wenigen Knoten

das sollte aber kein problem sein - ich würd mal vermuten, dass das programm den freigegebenen speicher wieder nutzt, den es dem OS noch nicht "zurückgegeben hat"...
btw: programmierst du die liste nur als übung, oder kennst du std::list (ne fertig programmierte Liste) nicht? Evtl solltest du auch ne ganz andere Datenstruktur nehmen - kommt immer darauf an, was dein Programm machen soll...

bb

unskilled schrieb:

das sollte aber kein problem sein - ich würd mal vermuten, dass das programm den freigegebenen speicher wieder nutzt, den es dem OS noch nicht "zurückgegeben hat"...
btw: programmierst du die liste nur als übung, oder kennst du std::list (ne fertig programmierte Liste) nicht? Evtl solltest du auch ne ganz andere Datenstruktur nehmen - kommt immer darauf an, was dein Programm machen soll...

bb

ich konnte gerade zusätzliche 10 mb im speicher anstauen (die liste wird per regler geresized, ich werds gleich mal in einen loop einbauen)

Ich hatte vorher eine std::list verwendet, aber irgendwie war sie zu langsam. Ich arbeite an einem Spiel in DirectX. Dann habe ich mir die Liste aus einem Partikelsystem angesehen, welche viel mehr Knoten verwaltet. Dann habe ich diese Struktur eingebaut, und die Performance ist wesentlich besser geworden!

Als Beispiel:

Eine std::list mit 50 Objekten wird 50 mal pro Frame durchlaufen.

Das selbe mit der Struct Liste gibt sage und schreibe 35 FPS mehr (Habe es gerade nochmal getestet, da ich es auch kaum glauben kann).

Dann noch eine einfache std::list sort() Funktion 50 mal in dem Loop und die Performance sinkt um 95%

Alleine das Einfügen in die Liste hat bei 50 x 50 Objekten pro Frame etwa 60 FPS gekostet.

Nun habe ich in meinem Projekt einige std listen und vektoren und werde wahrscheinlich auf eine Eigenschöpfung umsteigen.

Die Arbeit mit den std Listen und Vektoren war allerdings wesentlich komfortabler

unskilled

hmm..
1. hört sich das nach debug mode an
2. so, als ob du noch nie was von std::deque gehört hast

wenn du wenige einfügeoperationen hast, dann gibts auch noch std::vector

es gibt da auch so ne schöne container_choice.png:
http://images.google.de/images?hl=de&um=1&sa=1&q=cpp+container+choice&aq=f&oq=&start=0

bb

Oh mein Gott, du hast Recht

Im Release Modus sind die std listen mindestens genauso schnell!

Ich habe den release modus total vergessen.. hatte anfangs auch nie so einen deutlichen Unterschied gemacht.

Im Release Modus läuft alles mit 100 FPS mehr

Danke dir für den Hinweis

Der kleine Ausflug in die Welt der Listen war letztendlich aber ganz lehrreich.

Kann man den std::listen und vektoren denn irgendwie mitteilen, dass sie nie debugged werden sollen? Ich brauche die Debuginformationen der Listen nicht, jedoch die des restlichen Programms. Wäre nämlich praktisch, wenn die Listen im Debugmodus auch so schnell wären.

drakon

Du kannst das über die defines lösen:

#define _HAS_ITERATOR_DEBUGGING 0

Und dann die Header inkludieren. Bin jetzt nicht sicher, ob noch andere defines nötig sind.

unskilled

daniel1984 schrieb:

Kann man den std::listen und vektoren denn irgendwie mitteilen, dass sie nie debugged werden sollen? Ich brauche die Debuginformationen der Listen nicht, jedoch die des restlichen Programms. Wäre nämlich praktisch, wenn die Listen im Debugmodus auch so schnell wären.

Ich kenn keine Möglichkeit - sicher, dass es an den listen liegt?
ich denke, es gibt andere dinge, die viel mehr asserts ausführen, als ne liste... hört sich auch so an, als ob du immernoch die falsche datenstruktur verwendest wofür ist die Liste denn nun genau da? Welche operationen werden darauf ausgeführt? Wie oft?

btw: was is das problem, wenn du im debugmode halt nur 40FPS hast?

bb

unskilled

drakon schrieb:

Du kannst das über die defines lösen:
#define _HAS_ITERATOR_DEBUGGING 0
Und dann die Header inkludieren. Bin jetzt nicht sicher, ob noch andere defines nötig sind.

das sollte es jz nicht so extrem langsam machen!? aber wenn wir schon mal dabei sind:
#define _SECURE_SCL 0
wird auch noch paar prozent(promille^^) ausmachen

allerdings würd ichs so machen:

#define _SECURE_SCL 0
#undef _DEBUG

#define NDEBUG //aber nur, falls du alle asserts deaktivieren möchtest...

allerdings müsstest du dir sicher sein, dass das vor dem ersten vector/list/...-include kommt...

bb

drakon

Kommt auf die Anforderung an, was alles ausgeschaltet werden kann. Aber mir ist das ganze auch ein wenig Suspekt. - Ist ja egal, wenn es im Debug Mode langsamer ist..
Allerdings kenne ich das, dass sich mit dem Overhead, der sich ergibt kaum noch etwas Debuggen lässt, wenn es so lange dauert..

Danke euch!

Nützlich im Fall, wenn das das Spiel im Debugmodus unspielbar werden sollte.

@unskilled:

Ich wollte mir gerade dein Diagramm genauer ansehen. Wahrscheinlich habe ich wirklich die Falsche Struktur.

Um es kurz zusammenzufassen: Meine Spielobjekte werden in Vektoren gespeichert. Die Anzahl der Objekte ändert sich selten. Die Vektoren werden aber dauernd durchlaufen.

Die Liste, um die es ging, führt jedes Objekt mit sich und speichert soll darin speichern, welche Objekte in der Nähe liegen. Ich arbeite an sowas wie Schwarmverhalten. Da nicht immer gleich viele Objekte in direkter Nähe sind, kann die Listengröße variabel sein. Die Liste sollte außerdem nach der Distanz zu den Objekte sortiert werden Welche Datenstruktur würde am besten passen?

Die deque scheint es zu sein, laut dem Diagramm!

Ist mir noch völlig unbekannt und wird jetzt genauer unter die Lupe genommen

unskilled

Und Distanz ist ein float oder ein int? Gibt es eine maximal-Zahl an Objekten in der Nähe? kannst du die zumindest abschätzen? wie groß sind die objekte, die du speicherst? also was sagt sizeof(instanz_eines_objektes)?

Distanz ist ganzzahlig: würde ich vll multi_map nehmen (wenn du alle objekte durchgehst, ist das hier allerdings schon wieder ne all zu dolle^^)
vll auch ne priority_queue, allerdings hab ich die noch nie verwendet und weiß demzufolge auch relativ wenig über sie und wie man sie "missbrauchen" kann
wenn das beides nich besser ist, dann würd ich deque und list mal vergleichen...

bb

camper

Ist das also eine Liste aus Zeigern? Höchstwahrscheinlich ist hier vector am effizientesten - Einfügen außer am Ende ist zwar etwas teurer - aber wenn diese vectoren nur eine vielleicht zweistellige ANzahl an Elementen haben, ist das immer noch kaum wesentlich teurer als etwa list, bei dem wir für jedes Element eine gegebenenfalls teuere Allokation (kann man u.a. durch optimierte Allokator verbessern) durchführen müssen. Dafür ist dann alles andere weitaus einfacher zu optimieren, zudem ist der Speicherverbrauch deutlich geringer.