delete beschleunigen

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.

hustbaer

asc schrieb:

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

Naja, das ist schon länger so.
Bzw. es geht glaube ich primär darum dass kein Debugger auf dem Prozess draufhängt.

Bashar

The Windows Heap Is Slow When Launched from the Debugger

janmerkschien

also ich schildere jetzt mal meine Sicht ...
Das Programm, welches ich am Optimieren bin, ist im produktiven Einsatz.
Und bei 72660 Strukturen dauert es noch nicht zulange die ganzen delets auszuführen.
aber es werden immer mehr Strukturen die nachher eine Tabelle ergeben.
Und um dem Problem vorzubeugen das es nachher wirklich im Release Modus 5 Sekunden dauert die ganzen delets auszuführen soll ich den Prozess beschleunige.

pumuckl

Dann schau dir die Tips nochmal an und informier dich vor allem wie die vorgeschlagenen Lösungen (std::vector, std::list, allokatoren) funktionieren, d.h. was sie intern machen. Du hast ein paarmal was geschrieben von mehrfachen deletes in einem vector und von deinen listen in einem vector - das legt nahe, dass du die Standardbibliothek noch nicht kennst. Schon allein die Tatsache, dass bei euch in offenbar produktivem Code noch handgestrickte Listen verwendet werden, deutet darauf hin, dass ihr entweder C und kein C++ programmiert (was bei new/delete aber nicht der Fall sein kann), oder aber dass euer Code irgendwann anfang der 90er stehengeblieben ist. 1998 ist C++ standardisiert worden inklusive std::vector und std::list, und schon vorher gab es viele Bibliotheken die Listen und Vektoren enthalten haben.
Ich weiß dass das jetzt hart klingt, aber leider ist es tatsächlich so. Leider bleiben nicht nur viele Profs/Lehrer, sondern auch eine Menge Firmen auf alten Wissensständen stehen und bekommen Probleme wie deins, deren Lösungen schon seit Jahrzehnten direkt vor der Tür liegen.

asc

janmerkschien schrieb:

also ich schildere jetzt mal meine Sicht ...
Das Programm, welches ich am Optimieren bin, ist im produktiven Einsatz.
Und bei 72660 Strukturen dauert es noch nicht zulange die ganzen delets auszuführen.
aber es werden immer mehr Strukturen die nachher eine Tabelle ergeben.

Bei den nachgemessenen Zeiten, die noch nicht einmal im Sekundenbruchteil liegen (Wie gesagt, außerhalb der IDE im Releasemodus bei mir etwa 0,025 Sekunden), und die sich in etwa linear verhalten, dürfte es erst bei einer wesentlichen Vergrößerung überhaupt eine wesentlich messbare Zeit ergeben. Es sei den der Zielrechner ist sehr langsam (z.B. Embedded-Umfeld).

Schneller sollte es gehen wenn man eine passendere Datenstruktur wählt (Selbst ein std::vector sollte bei ungefähr abschätzbarer, und vorreservierter Größe wesentlich besser als eine verkettete Liste sein, sofern nicht regelmäßig eingefügt werden muss).

janmerkschien schrieb:

Und um dem Problem vorzubeugen das es nachher wirklich im Release Modus 5 Sekunden dauert die ganzen delets auszuführen soll ich den Prozess beschleunige.

Keiner von uns kam auch nur in die Nähe, von bereits gesagter Einschränkung mit dem Test aus der IDE mal abgesehen. Hier deutet sich entweder ein massiver Messfehler an, oder das wesentlich mehr Logik als nur die delete ausgeführt werden. Oder aber du solltest und mal die groben Eckdaten der Zielplattform nennen, wenn diese wesentlich schlechter als "normale" Desktops sind.

janmerkschien

ich habe mir jetzt ein kleines Testprogramm geschrieben um den Sachverhalt zu testen ^^
ich teste jetzt mit 99998 strukturen.
Die liste die momentan verwendet wird benötigt 5,3 sekunden für alle delets, als release ...
ich werde jetzt mal std::vector und std::list ausprobieren und dann mein ergebnis nochmal posten