Eigener Thread für deletes?

Fellhuhn schrieb:

Würde aber darauf wetten das die eigene Verwaltung langsamer ist als die vom System. Und die Idee mit den Threads wird dir wohl mehr Probleme einbringen als irgend eine Form von Nutzen.

Sehr lustig. Das habe ich ja schon alles versucht, nein, man kann da nix gewinnen.
Zumindest nicht mit STL Containern, auch boost::unordered_set brint nix.
Ein erster Test hat gezeigt, das 2 Millionen deletes in einer Schleife doch schon recht lange laufen (im Sekundenbereich).

Es geht hier explizit um die deletes, und ob es sich in einem eigenen Thread lohnt.

DocShoe schrieb:

Vielleicht solltest du mal einen Blick auf boost::pool werfen.

Sorry, aber ich benötige Arrays, also new[]/delete[].
Und hier bietet boost::pool nur O(n) Performance, ist also schon beim "was ist für alloc/dealloc am besten" rausgeflogen. Da hat übrigens new[]/delete[] gewonnen.

DocShoe

Vielleicht solltest du mal einen Blick auf boost::array werfen

DocShoe schrieb:

Vielleicht solltest du mal einen Blick auf boost::array werfen

Habe ich schon erwähnt, das ich boost nicht wirklich verwenden kann (Solaris)?
Auch weiss ich nicht, was in dem Bezug mir Boost Array nutzen soll.
Wie gesagt, mir gehts hier um die Performance, und da ich viele delete[] habe, denke ich das ein eigener Thread hierfür schon lohnenswert ist. Einen Mutex brauche ich auch nicht mehr, da ich dies wohl ohne hinbekomme (Habe eine Threadimplementation welche actions abarbeiten kann).

theliquidwave

Dann probier es doch einfach, dann wirst du doch sehen ob es klappt?!

Gruß

Ein eigener Thread für deletes bringt nichts. Du solltest lieber die Anzahl der Allokationen reduzieren. Und wenn das nicht geht, schreibe eigene Allokatoren und benutze einen Memorypool.

DocShoe

Ok, dann also ernst und ausführlich

- Nein, du hast nicht erwähnt, dass du unter Solaris entwickelst und daher kein boost benutzen kannst
- boost::array hilft dir insofern, dass es C-style Arrays als Objekte kapselt und per new/delete erzeugt werden können, statt mit new[]/delete[]. Damit lassen sie sich dann auch über boost::pool erzeugen/zerstören.
- erzähl uns doch bitte etwas mehr über das Laufzeitverhalten deiner Anwendung. Brauchst du diese Objekte alle gleichzeitig oder nur einige, aber du erzeugst/zerstörst sie ständig, weil du sie in irgendeiner Form von Schleife abarbeitest.
- wie groß sind deine Objekte? Eher einige Byte oder eher mehr?
- haben deine Objekte eine konstante Größe?
- passieren im Destruktor spannende Dinge oder funktioniert dein Programm noch einwandfrei, wenn der Destruktor nicht aufgerufen wird

Vielleicht kannst du selbst eine Art Pool bauen, aus dem du Objekte anforderst und wieder zurückgibst. Dieser Pool könnte Objekte cachen statt sie sofort wieder freizugeben. Vielleicht kannst du auch Blöcke von Objekten erzeugen (sagen wir mal 100 am Stück), um damit die Anzahl der new[]/delete[] Aufrufe zu reduzieren?

DocShoe schrieb:

Ok, dann also ernst und ausführlich
- boost::array hilft dir insofern, dass es C-style Arrays als Objekte kapselt und per new/delete erzeugt werden können, statt mit new[]/delete[]. Damit lassen sie sich dann auch über boost::pool erzeugen/zerstören.
- wie groß sind deine Objekte? Eher einige Byte oder eher mehr?

Beantwortet aber nicht die Frage dieses Threads. Habe die Allokationen selber schon sehr gut durch, aber dass kann eben nicht zur Compilezeit gemacht werden, mein MemoryManager hat ein Funktion void* allocate(size_t size) bzw. deallocate(void*).
Size geht von 2-ca.528000.

DocShoe schrieb:

- erzähl uns doch bitte etwas mehr über das Laufzeitverhalten deiner Anwendung. Brauchst du diese Objekte alle gleichzeitig oder nur einige, aber du erzeugst/zerstörst sie ständig, weil du sie in irgendeiner Form von Schleife abarbeitest.

Die Objekte werden während eines Importvorgangs erstellt, insgesamt ca. 14 Millionen wovon ca. 13 Millionen auch wieder freigegeben werden.

DocShoe schrieb:

- haben deine Objekte eine konstante Größe?

Nein.

DocShoe schrieb:

- passieren im Destruktor spannende Dinge oder funktioniert dein Programm noch einwandfrei, wenn der Destruktor nicht aufgerufen wird

Zur Zeit sind es nur unsigned char arrays, welche durch den Thread gelöscht werden.
Bei Objekten würde es sich durch Konstruktoraufrufe natürlich verkomplizieren, aber wohl auch mehr performance bringen evtl.

DocShoe schrieb:

Vielleicht kannst du selbst eine Art Pool bauen, aus dem du Objekte anforderst und wieder zurückgibst. Dieser Pool könnte Objekte cachen statt sie sofort wieder freizugeben. Vielleicht kannst du auch Blöcke von Objekten erzeugen (sagen wir mal 100 am Stück), um damit die Anzahl der new[]/delete[] Aufrufe zu reduzieren?

Habe schon einen eigenen Allokator, der aber trotz einiger Optimierung immer noch schlechter ist als new[]/delete[]. Gerade weil ich ja nur unsigned char Arrays allokiere, denke ich dass hier auch nicht wirklich was zu holen wäre. Den Pool führt schon der Allokator für Windows recht gut, ausserdem linke ich noch zu tcmalloc.

pumuckl

Wenn du nur unsigned char-Arrays hat wunderst mich doch sehr, dass es performanter sein soll, dafür jedes einzelne Array new[]/delete[] aufzurufen, statt einen großen Block selber zu verwalten.

Was delete[]s in einem eigenen Thread angeht:
Ich kann mir nur bedingt vorstellen, dass das viel bringt. Natürlich kann es für den Hauptthread einen gewissen Geschwindigkeitsvorteil bringen, wenn zu deallokierender Speicher einfach schnell auf Halde geschoben wird und weitergemacht werden kann, währen im Hintergrgund jemand nach und nach die Halde abbaut.
Allerdings meine ich mal gelesen zu haben, dass das Freigeben von Speicher ziemlich performant ist, der eigentliche Flaschenhals also eher die Speicherbeschaffung ist. Und da gewinnst du so ja nichts dazu.
Probiers am Besten aus und miss nach, wieviel Zeit du dadurch gewinnst.

DocShoe

Einige Fragen haben nicht direkt etwas mit der Lösung des Problems zu tun, das ist richtig. Allerdings kann man ohne detaillierte Kenntnisse des Problems keine Lösungsansätze bzw. Optimierungen entwickeln.

Wieviele Arrays brauchst du denn tatsächlich gleichzeitig? Wenn es ein Importvorgang ist gehe ich mal davon aus, dass jeder Datensatz aus einzelnen Attributen besteht und du die Arrays zum Lesen der Attribute brauchst.
Wenn das so ist, ist die Anzahl der Attribute konstant? Oder annähernd konstant?
Wenn das so ist, vielleicht geht dann sowas (naiver Ansatz):

typedef std::vector<unsigned char> UCharVector_t;
std::deque<UCharVector_t> Pool;

while( !done )
{
   if( Pool.size() < attributes_count )
   {
      Pool.resize( attributes_count );   

      // vllt mehr Performance durch 1K Default Größe?
      Pool.resize( attributes_count, UCharVector_t( 1024 ) );   
   }

   for( unsigned int idx = 0; idx < max_attributes; ++idx )
   {
      Pool[idx].resize( attribute_length[idx] );
      read_attribute( idx, &Pool[idx].front() );
   }
}

Ohne Detailinformationen kann man nur raten, und ob dabei etwas Brauchbares herauskommt sei mal dahingestellt.

Dravere

Frage: Weiss der Threadersteller, was placement new ist?
Grundsätzlich wäre es ja möglich, dass man es nur über einem new[] und einem delete[] machen könnte. Allenfalls sogar über malloc , da es sich nur um PODs handelt, falls new[] wirklich zu langsam wäre.

Noch eine Frage: Werden die Allokationen hintereinander aufgerufen und danach alle Deallokationen hintereinander? Das wäre dann nämlich sehr einfach zu optimieren

Grüssli

pumuckl schrieb:

Wenn du nur unsigned char-Arrays hat wunderst mich doch sehr, dass es performanter sein soll, dafür jedes einzelne Array new[]/delete[] aufzurufen, statt einen großen Block selber zu verwalten.

Einen Blockallokator, welches alles in eigenen Pages hält habe ich in der Tat noch nicht. Allerdings sehe ich hier keinen gewinn, weil der Systemallokator wohl schon genau dies macht. Habe bereits einen Allokator welcher die Blöcke in einzelnen Listen verwaltet.

pumuckl schrieb:

Was delete[]s in einem eigenen Thread angeht:
Ich kann mir nur bedingt vorstellen, dass das viel bringt. Natürlich kann es für den Hauptthread einen gewissen Geschwindigkeitsvorteil bringen, wenn zu deallokierender Speicher einfach schnell auf Halde geschoben wird und weitergemacht werden kann, währen im Hintergrgund jemand nach und nach die Halde abbaut.
Allerdings meine ich mal gelesen zu haben, dass das Freigeben von Speicher ziemlich performant ist, der eigentliche Flaschenhals also eher die Speicherbeschaffung ist. Und da gewinnst du so ja nichts dazu.
Probiers am Besten aus und miss nach, wieviel Zeit du dadurch gewinnst.

Also ich habe gestern erstmal eine Messung gemacht:

const int n = 2000000, x = 500;
	std::vector<unsigned char*> buf;
	unsigned int sz  =0;
	std::cout << gettime() << std::endl;
	for(int i =0; i < n; ++i)
	{
		sz = (std::rand() % x) +5;
		buf.push_back(new unsigned char[sz]);
	}
	std::cout << gettime() << std::endl;

	for(int i =0; i < n; ++i)
		delete[] buf[i];
	std::cout << gettime() << std::endl;

Die Deleteschleife läuft immer deutlich länger, als die Newschleife.
Allerdings lässt sich damit keine Aussage für mein Programm machen, es zeigt nur das die Deletes durchaus teuer sein können.

Werde gleich ein paar Messungen machen, die Sache ist ja recht trivial in der Implementierung.

DocShoe schrieb:

Einige Fragen haben nicht direkt etwas mit der Lösung des Problems zu tun, das ist richtig. Allerdings kann man ohne detaillierte Kenntnisse des Problems keine Lösungsansätze bzw. Optimierungen entwickeln.

Wieviele Arrays brauchst du denn tatsächlich gleichzeitig? Wenn es ein Importvorgang ist gehe ich mal davon aus, dass jeder Datensatz aus einzelnen Attributen besteht und du die Arrays zum Lesen der Attribute brauchst.
Wenn das so ist, ist die Anzahl der Attribute konstant? Oder annähernd konstant?

Schön wärs
Nein, der MemoryManager der hier die Anfragen bekommt, ist für Xerces, d.h. es wird aus unterschiedlichsten XML Dateien importiert. die 14 Millionen Allokationen stammen aus einer datei mit 150 mb, bis zu 500mb sind möglich. (bzw. bis dahin unterstützt die Software dies offiziell)

DocShoe schrieb:

Wenn das so ist, vielleicht geht dann sowas (naiver Ansatz):

typedef std::vector<unsigned char> UCharVector_t;
std::deque<UCharVector_t> Pool;

while( !done )
{
   if( Pool.size() < attributes_count )
   {
      Pool.resize( attributes_count );   
 
      // vllt mehr Performance durch 1K Default Größe?
      Pool.resize( attributes_count, UCharVector_t( 1024 ) );   
   }

   for( unsigned int idx = 0; idx < max_attributes; ++idx )
   {
      Pool[idx].resize( attribute_length[idx] );
      read_attribute( idx, &Pool[idx].front() );
   }
}

Ohne Detailinformationen kann man nur raten, und ob dabei etwas Brauchbares herauskommt sei mal dahingestellt.

Sagte doch das die Blockgröße zwischen 2 Byte und ca. 528000 byte liegt.
D.h. auch, das die 528000 Byte on Block im Speicher sein müssen.
Mit Präferenz auf Blockgrößen zwischen 2 - 1000 Byte.

DocShoe

Jetzt wird´s aber mal höchste Zeit, dass du das Problem und die Umgebung exakt beschreibst.

Dravere schrieb:

Noch eine Frage: Werden die Allokationen hintereinander aufgerufen und danach alle Deallokationen hintereinander? Das wäre dann nämlich sehr einfach zu optimieren

Nee. Auch das XML Format ist nicht nur ein Importformat, sondern sehr viele. Deswegen versuche ich ja auch erstmal auf der Ebene des XML Parsers zu optimieren, und dass geht halt nur über die Schnittstellen die von Xerces habe. Den Parser kann ich nicht wechseln, weil wir das volle Featureset brauchen, und es bereits reichlich Code damit gibt.

Shade Of Mine

Wenn du XML Dateien parst dann kennst du ja das genaue Allokationsmuster und kannst diesbezüglich optimieren.

Du weisst zB dass du ka, 10.000 Tags hast, also prinzipiell mal 10.000 strings in einem stück allokieren. davon kann man dann die notwendigen attribute ableiten, etc.

weiters hast du keine deallokationen in der allokationsphase, dh du musst keine fragmentierung beachten.

domain spezifische optimierungen bringen da vermutlich am meisten...

DocShoe schrieb:

Jetzt wird´s aber mal höchste Zeit, dass du das Problem und die Umgebung exakt beschreibst.

Soll ich für dich noch mal zusammenfassen?

Es geht um die Fragestellung, ob sich ein eigener Thread für delete[] lohnt.
Ich habe die Methoden

void* alloc(size_t size);
void dealloc(void*);

Diese Allokieren unsigned chars für einen XML Parser.
Die Frage ist also, delete[] in dealloc direkt, oder erstmal die void* sammeln, um sie dann in einem Thread mittels einer Action fürs Löschen zu entsorgen.

Shade Of Mine schrieb:

Wenn du XML Dateien parst dann kennst du ja das genaue Allokationsmuster und kannst diesbezüglich optimieren.

Du weisst zB dass du ka, 10.000 Tags hast, also prinzipiell mal 10.000 strings in einem stück allokieren. davon kann man dann die notwendigen attribute ableiten, etc.

weiters hast du keine deallokationen in der allokationsphase, dh du musst keine fragmentierung beachten.

domain spezifische optimierungen bringen da vermutlich am meisten...

Ne, was da gerade jetzt wie oft kommt, hängt ja von der Datei ab. Natürlich könnte ich bestimmte Größen vorrätig halten, aber der Verwaltungsoverhead hier frisst wieder die Performance. Ich habe ja einen Allokator mit eigener Freelist, so das kein unnötiges New kommt.

Denke das ein Allokator der nur feste Blöcke allokiert, und dann aus diesen den Speicher verwaltet evtl. noch etwas bringen kann, allerdings gehts darum hier nicht.

DocShoe

Ah, jetzt habe ich´s verstanden... du hast kein Interesse daran, deinen Algorithmus zu optimieren, sondern sucht lediglich die Antwort auf die Frage, ob ein Auslagern der Speicherfreigabe in einen Thread Geschwindigkeitsvorteile bringt?

Antwort:
Ist mir egal.

DocShoe schrieb:

Ah, jetzt habe ich´s verstanden... du hast kein Interesse daran, deinen Algorithmus zu optimieren, sondern sucht lediglich die Antwort auf die Frage, ob ein Auslagern der Speicherfreigabe in einen Thread Geschwindigkeitsvorteile bringt?

Antwort:
Ist mir egal.

Ist nicht das erstemal das ich mich mit dem Problem beschäftige, und weiss auch nicht was da an Algorithmus sein soll.
Die Schnittstelle die ich gepostet habe, ist das was da ist. Innerhalb dieser Schnittstelle kannst du gerne eine bessere Sache versuchen, aber dazu habe ich schon mal einen Thread hier gehabt, einzig ein Blockallokator mit eigener Blockverwaltung wäre hier noch für mich interessant, aber darum gehts hier nicht.
Aktuell interessiert mich ob die deletes im Thread was bringen oder nicht.