delete beschleunigen

cooky451

delete ist halt einfach super langsam. Hat mich auch immer gewundert, aber es ist so. Da hilft auch keine std::list. Der vector muss delete nur ein Mal aufrufen, und der ist in den meisten Fällen eh zu bevorzugen. Aber wenn du die Liste wirklich brauchst, bleibt dir wohl nur ein eigener allocator oder Ähnliches.

janmerkschien

Ok danke für die sehr schellen Antworten
Ich werde mir dann einmal anschauen was ein allocator ist ....

Ethon

janmerkschien schrieb:

Ich werde mir dann einmal anschauen was ein allocator ist ....

Wieso das und nicht einfach std::vector benutzen? Der ist nämlich in vielen Gebieten einer linked List hoffnungslos überlegen.

dibada

Es läuft darauf hinaus, dass du die "operator new" und "operator delete" Methoden deiner Klasse überschreibst.

Wenn Du den delete Operator erstmal leer läßt, kannst Du auch schön sehen, ob dort die Zeit bleibt, oder ob es immer noch langsam ist. Das produziert natürlich massig Memoryleaks, aber zum Testen ist das ja egal.

Wenn das erfolgreich war müsstest Du den Speicher für Deine Objekte selber verwalten. Typischerweise fordert man gleich Speicher für viele Objekte an und verwaltet diese dann selber. Aber da kann man natürlich auch auf fertige Lösungen zurückgreifen...

janmerkschien

wenn ich vector benutze würde das an der ganzen sache nix ändern ....
es würde trotzdem für jede struktur im vector ein delete aufgerufen und so würde der zeitaufwand der selbe bleiben ^^
(wenn ich das richtig verstanden habe)

@dibada: wo könnte ich denn solche fertigen Lösungen finden ??

LordJaxom

Nein, vector allokiert am Stück und Du musst ja keine Zeiger im vector speichern. Es würde zwar für jeden Eintrag der Destruktor durchlaufen (der in diesem Fall aber eh nichts macht, da es ein POD ist), aber nur einmal delete aufgerufen.

Du darfst aber grundsätzlich auch nochmal drüber nachdenken oder nachfragen, wenn Dir hier drei erfahrene Leute sagen, dass das ein oder andere für Dich besser geeignet ist

EDIT:

janmerkschien schrieb:

@dibada: wo könnte ich denn solche fertigen Lösungen finden ??

Das meinst Du jetzt nicht ernst?

Bashar

Mal unabhängig davon, dass man das ganze anders viel besser machen kann: Es kann eigentlich nicht sein, dass 30000mal delete 5-6 Sekunden dauert. delete ist vielleicht langsam, aber nicht so langsam. Das muss also irgendeine andere Ursache haben.

krümelkacker

janmerkschien schrieb:

wenn ich vector benutze würde das an der ganzen sache nix ändern ....
es würde trotzdem für jede struktur im vector ein delete aufgerufen und so würde der zeitaufwand der selbe bleiben ^^
(wenn ich das richtig verstanden habe)

Nein, hast Du nicht.

Ethon

janmerkschien schrieb:

wenn ich vector benutze würde das an der ganzen sache nix ändern ....
es würde trotzdem für jede struktur im vector ein delete aufgerufen und so würde der zeitaufwand der selbe bleiben ^^
(wenn ich das richtig verstanden habe)

Eben nicht!
std::vector ist ein toller Wrapper um

new DataItem[xyz];

, der dem manuellen Speicher verwalten auf jeden Fall vorzuziehen ist.

std::vector besorgt nur einmal Speicher für ALLE Elemente, ist halt ein Array. Wenn der Vektor voll ist, alloziert er mehr Speicher (ca doppelt so viel) und kopiert in den neuen Bereich.

Wenn du die Anzahl der Objekte abschätzen kannst, hast du mit einem std::vector genau 1 new und 1 delete. Wenn du mit einem leeren vector startest und immer anhängst, hast du um den Dreh log(n) + x Allocations/Deletes (Der Vektor muss wachsen).

janmerkschien

@bashar :
also es sind 72660 strukturen und keine 30000 ...
und es sind auch nicht 5-6 sekunden sondern nur 2-3s
ich hatte noch nicht so genau gemessen als ich den Beitrag verfasst hatte sorry

@Ethon:
der vector würde dann immer wieder eine Struktur dazu bekommen also insgesamt 72660 mal ...
und dann hätte ich ja wieder 72660 Allocations/Deletes oder?

TyRoXx

janmerkschien schrieb:

der vector würde dann immer wieder eine Struktur dazu bekommen also insgesamt 72660 mal ...
und dann hätte ich ja wieder 72660 Allocations/Deletes oder?

Ne, immer noch nicht.

Ethon schrieb:

Eben nicht!
std::vector ist ein toller Wrapper um
new DataItem[xyz];

Toll ja, aber nicht einmal vector verwendet intern new[] .

janmerkschien

Ethon schrieb:

Wenn du die Anzahl der Objekte abschätzen kannst, hast du mit einem std::vector genau 1 new und 1 delete. Wenn du mit einem leeren vector startest und immer anhängst, hast du um den Dreh log(n) + x Allocations/Deletes (Der Vektor muss wachsen).

den satz verstehe ich so das pro liste die angehängt wird eine Allocation und ein Delete hinzu kommt.

Ethon

Toll ja, aber nicht einmal vector verwendet intern new[].

Der std::vector verwendet per default std::allocator und der new[].
Also doch.

den satz verstehe ich so das pro liste die angehängt wird eine Allocation und ein Delete hinzu kommt.

Okay, dann langsam. Stell dir vor der Vektor hat am Anfang Platz für 20 Elemente. Dann muss die nächsten 20x Anfügen kein new aufgerufen werden. Ab 20 muss neuer Speicher her. Also besorgt der Vektor beispielsweise Speicher für 60 Elemente und entfernt den alten Speicher per delete. Bis die 60 voll sind muss wieder kein new aufgerufen werden, dann wieder 1x new + 1x delete. Wenn der Vektor seinen Wertebereich verlässt und der Destruktor aufgerufen wird, ist noch 1 delete fällig. Das wars.

janmerkschien

danke für deine geduld mit mir Ethon

TyRoXx

Ethon schrieb:

Toll ja, aber nicht einmal vector verwendet intern new[].

Der std::vector verwendet per default std::allocator und der new[].
Also doch.

Wo steht das? Ist dir klar, dass das nicht funktionieren kann?
allocator<T>::allocate liefern einem ein Stück Speicher für n Elemente, angefordert mit ::operator new . Konstruktoren werden dann mit placement new bzw. allocator<T>::construct aufgerufen.

SeppJ

TyRoXx schrieb:

Ethon schrieb:

Toll ja, aber nicht einmal vector verwendet intern new[].

Der std::vector verwendet per default std::allocator und der new[].
Also doch.

Wo steht das? Ist dir klar, dass das nicht funktionieren kann?
allocator<T>::allocate liefern einem ein Stück Speicher für n Elemente, angefordert mit ::operator new . Konstruktoren werden dann mit placement new bzw. allocator<T>::construct aufgerufen.

Da new[] das auch so macht, sollte man es vielleicht so forumlieren: Der Standardallocator macht das gleiche wie new[], auch wenn es technisch kein Wrapper um new[] ist.

hustbaer

Nur mal so, weil ich vor nicht all zu langer Zeit ne kleine Allocator Benchmark gebastelt habe: auf meinem PC hier (Core2 Duo mit 2,13 GHz, Windows XP SP3) schaffe ich so 3~10 Mio. Allocations + Deallocations pro Sekunde.

cooky451

@hustbaer
Stimmt, das dauert bei mir auch "nur" ~1.2 Sekunden:

#include <ctime>
#include <list>
#include <iostream>

int main()
{
	auto t = std::clock();
	{
		std::list<int> l;
		for (auto i = 5000000; i--; )
			l.push_back(i);
		auto elapsed = (std::clock() - t) / static_cast<double>(CLOCKS_PER_SEC);
		std::cout << "Elapsed alloc: " << elapsed << '\n';
	}
	auto elapsed = (std::clock() - t) / static_cast<double>(CLOCKS_PER_SEC);
	std::cout << "Elapsed dealloc: " << elapsed << '\n';
}

Insofern könnte der TE mal schreiben was er da bei sich veranstaltet.

SeppJ

cooky451 schrieb:

Insofern könnte der TE mal schreiben was er da bei sich veranstaltet.

Debugbuild? Wenn man alle Aktionen auf ihre Richtigkeit prüft (ok, das macht auch eine optimierte (De-)Allokation noch) und noch tolle Heapguards einbaut und diese auf Überschreiben prüft, dann dauert das ganz schön lange.

asc

Ich habe es mal mit dem Visual C++ 2010 versucht.

Aus der IDE brauch es bei mir tatsächlich, ungeachtet vom Release oder Debug ca. 2-3 Sekunden mit seiner Datenstruktur. Von der Konsole aus braucht das Release 0,025 Sekunden (und das Debug doppelt so lange).

Sprich: Für eine Zeitmessung sollte man scheinbar neuerdings auch die IDE verlassen.