delete beschleunigen

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

Shade Of Mine

janmerkschien schrieb:

Die liste die momentan verwendet wird benötigt 5,3 sekunden für alle delets, als release ...

Dann hast du entweder einen Messfehler, machst mehr als nur Delete oder läufst mit angehängten Debugger.

100000 Elemente zu deleten ist so schnell, dass du es kaum Messen können solltest. Wenn es länger als einen Bruchteil einer Sekunde dauert, ist irgendwas anderes das Problem.

asc

janmerkschien schrieb:

ich werde jetzt mal std::vector und std::list ausprobieren und dann mein ergebnis nochmal posten

Wenn du std::vector verwendest, solltest du diesen aber schon auf eine realistische Größe vorresservieren (Damit er nur selten umkopiert wird).

Beispiel:

std::vector<int> intvector;
intvector.reserve(50000);

janmerkschien

hier ist der code bei dem ich im release modus 5,5 sekunde brauche ...

#include "stdafx.h"
#include "windows.h"
#include "stdio.h"
#include <string>
#include <iostream>
#include "math.h"

using namespace std;

int main(int argc, char* argv[])
{
  struct Data{
  char point[128];
  long rec;
  int b;
  double b1,b2,b3;
  long L;
  char c1,c2,c3,c4;
  Data *next;
  };

  Data *first = new Data;
  Data *last = new Data;
  first=NULL;
  last = NULL;
  for(long i=0; i<99998; i++){
    if(first==NULL){
      first = new Data;
      if(first){
          first->next=NULL;
          strcpy(first->point,"bla");
          first->rec = 10;
          first->b = 0;
          first->b1 = 1;
          first->b2 = 2;
          first->b3 = 3;
          first->L = 7;
          first->c1 = 'A';
          first->c2 = 'B';
          first->c3 = 'C';
          first->c4 = 'D';
          last = first;
      }
    } else {
      Data *d = first;
      if(last==NULL)
        while(d->next) d=d->next;
      else
        d=last;
      d->next=new Data;
      if(d->next)
      {
        d->next->next=NULL;     
        strcpy(d->point,"bla");
        d->next->rec = 10;
        d->next->b = 0;
        d->next->b1 = 1;
        d->next->b2 = 2;
        d->next->b3 = 3;
        d->next->L = 7;
        d->next->c1 = 'A';
        d->next->c2 = 'B';
        d->next->c3 = 'C';
        d->next->c4 = 'D';
        last = d->next;
      }
    }
  }

	//Variablen
  LONGLONG g_Frequency, g_FirstNullCount, g_LastNullCount, g_FirstCount, g_LastCount;

  //Frequenz holen
  if (!QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency))
    printf("Performance Counter nicht vorhanden");

	double resolution = 1000000 / ((double)g_Frequency);

	printf("Frequenz des Counters:  %lld kHz\n", g_Frequency/1000);  //lld -> LONGLONG darstellung
	printf("Dadurch maximale Aufloesung: %4.5f us\n", resolution);

	//null-messung
	QueryPerformanceCounter((LARGE_INTEGER*)&g_FirstNullCount);
	QueryPerformanceCounter((LARGE_INTEGER*)&g_LastNullCount);
	double nulltime = (((double)(g_LastNullCount-g_FirstNullCount))/((double)g_Frequency)); 

	printf("Null-Zeit: %4.5f us\n", nulltime * 1000000);

	//beginn messung
	QueryPerformanceCounter((LARGE_INTEGER*)&g_FirstCount);

  ////////////DESTRUKTOR/////////////////////
  Data *d=first,*d2;
  while(d){
    d2=d->next;
    delete(d);
    d=d2;
  }

	//2. Messung
  QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);
  double dTimeDiff = (((double)(g_LastCount-g_FirstCount))/((double)g_Frequency)); 

	//Von der gemessenen Zeit die "Null-Zeit" abziehen, um genauer zu werden
	double time = (dTimeDiff - nulltime) * 1000000; //mikro-sekunden

	printf("Zeit: %4.5f us\n" ,time);

	//warten auf tastendruck
	string dummy;
	getline(cin, dummy);

	return 0;
}

@asc:
ja bin gerade bei den vector dranne aber wie kann ich den denn jetzt löschen ohne memory leaks??
delete vector; geht ja leider nicht

MFK

janmerkschien schrieb:

hier ist der code bei dem ich im release modus 5,5 sekunde brauche ...

Vielleicht solltest du das Programm mal ohne Debugger starten...

Ethon

Ich hab deinen Messcode weggelöscht und nur Aufbauen & Zerstören der Liste übrig gelassen und mit GCC kompiliert.
Die Ausführungszeit (mitsamt Prozesserstellung) beläuft sich auf gerade mal 50ms, sämtliche Optimierungen deaktiviert. (Irgendein alter AMD Phenom Quadcore)

ja bin gerade bei den vector dranne aber wie kann ich den denn jetzt löschen ohne memory leaks??
delete vector; geht ja leider nicht

Das macht der von alleine, manuell mit delete rumfuchteln tut man in C++ praktisch nie. Statt new[] und delete[] verwendet man std::vector, der selbst aufräumt. Statt delete verwendet man Smart-Pointer, zb std::shared_ptr oder std::unique_ptr.

So könnte dein Beispiel mit nem vector aussehen:

#include <cstring>
#include <vector>

int main(int argc, char* argv[])
{
    struct Data
    {
        char point[128];
        long rec;
        int b;
        double b1,b2,b3;
        long L;
        char c1,c2,c3,c4;
    };

    std::vector<Data> data(99998);
    for(long i=0; i<99998; i++)
    {
        Data cur;
        strcpy(cur.point,"bla");
        cur.rec = 10;
        cur.b = 0;
        cur.b1 = 1;
        cur.b2 = 2;
        cur.b3 = 3;
        cur.L = 7;
        cur.c1 = 'A';
        cur.c2 = 'B';
        cur.c3 = 'C';
        cur.c4 = 'D';

        data[i] = cur;
    }
}