Eigener Thread für deletes?

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.

pumuckl

delete schrieb:

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

delete schrieb:

[...], aber darum gehts hier nicht.
Aktuell interessiert mich ob die deletes im Thread was bringen oder nicht.

Da die Performance von delete[] sehr Systemabhängig sein dürfte kann man das wohl nicht allgemein beantworten, ob das auslagern was bringt. Wenn die Sache aber so trivial zu messen ist wunderts mich bei der inzwischen doch recht langen (und einigermaßen fruchtlosen) Diskussion, warum du es dann nicht schon längst gemessen hast.

pumuckl schrieb:

delete schrieb:

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

delete schrieb:

[...], aber darum gehts hier nicht.
Aktuell interessiert mich ob die deletes im Thread was bringen oder nicht.

Da die Performance von delete[] sehr Systemabhängig sein dürfte kann man das wohl nicht allgemein beantworten, ob das auslagern was bringt. Wenn die Sache aber so trivial zu messen ist wunderts mich bei der inzwischen doch recht langen (und einigermaßen fruchtlosen) Diskussion, warum du es dann nicht schon längst gemessen hast.

Ich bin dabei, habe aber kein extra test der das einfach ermöglichen würde, sondern muss jedesmal den Import starten. Vorher natürlich noch das Projekt bauen etc.
Ist einiges an Overhead und Zeitaufwand, aber bringt wohl das beste Ergebnis.

volkard

delete schrieb:

Ich frage mich jetzt, ob es sich lohnt, hier einen Thread für die deletes auf zu machen.

Dadurch bist Du verpflichtet, zu synchronisieren. Waren glaub ich 20 Takte pro delete. Denken wir uns einen Buddy-Allokator und davor einen Small-Object-Allokator für ein paar Größen, dann sind 20 Takte verdammt viel.
Also falls Du threadlokalen Speicher für die Small-Object-Listen nehmen kannst, riecht es danach, als sollte der Thread, der Speicher anlegt, ihn auch wieder freigeben.
Ich nehme an, Dein delete ist anders und Du mußt messen.
Ich habe leider noch keine Strategie für den I7 mit 12 Threads, die speichersparsam und schnell ist.

volkard schrieb:

delete schrieb:

Ich frage mich jetzt, ob es sich lohnt, hier einen Thread für die deletes auf zu machen.

Dadurch bist Du verpflichtet, zu synchronisieren. Waren glaub ich 20 Takte pro delete. Denken wir uns einen Buddy-Allokator und davor einen Small-Object-Allokator für ein paar Größen, dann sind 20 Takte verdammt viel.
Also falls Du threadlokalen Speicher für die Small-Object-Listen nehmen kannst, riecht es danach, als sollte der Thread, der Speicher anlegt, ihn auch wieder freigeben.
Ich nehme an, Dein delete ist anders und Du mußt messen.
Ich habe leider noch keine Strategie für den I7 mit 12 Threads, die speichersparsam und schnell ist.

Eigentlich müsste ich doch wenn ich in Thread A new[] mache, doch in Thread B delete[] machen können.
Synchronisieren muss ich zur Zeit afaik nicht. Ich habe eine Actionklasse, welche einen Block mit pointer bekommt, den löscht sie dann im Thread:

bs::actions::Deleter<void*,10000>* del = new bs::actions::Deleter<void*,10000>(delblock,delcount);
thread->addAction(*del);//ja, das ist so, blödes interface

thread löscht dann die Action ebenfalls.

So, die Tests haben jetzt ein etwas unerwartetes Ergebnis gebracht:

Durch Seiteneffekte ist eine genaue Aussage nicht möglich.

Weil die Anwendung unter Solaris wie unter XP läuft, verwenden wir fürs Threading eine pthread Library, von welcher ich die Actions auch ableite.
Hier kommt dann auch direkt ein Problem zu tragen, da der Import von Javaausgestartet wird, tut der Prozess bei bestimmten Bedingungen sobald der Thread läuft solange nix, bis die Javaanwendung beendet wird. Das lässt sich mit Sleep und ähnlichem umgehen, falls aber schon ein 2. Thread in der Import.exe läuft, hilft auch das nix.

Habe das aber mal so abgeändert das es einen nur den Hauptthread und den Deletethread gibt.
Jetzt kommt es zu einem anderen Problem: der Hauptthread schickt immerwieder Dinge an die DB, soll ja da rein Importiert werden. Solange tut der Importprozess dann relativ wenig, bis das die DB fertig ist. es wechseln sich während dem Import also Aktivitätsfenster von ca. 5 sek mit Wartezeiten auf die db ab (40-60 sek). Nur in diesen 5 sek kann offensichtlich der Thread löschen, und das ist zu wenig, der Speicherverbrauch der Anwendung ist etwas höher als sonst also.

Ich muss also herausfinden, wieso der gesamte Prozess immer diese Wartefenster hat, und wie ich Threads parallel dazu laufen lassen kann.

Als weiteres Ergebnis habe ich gesehen, das ein DeleteThread auch in anderen Kontexten des Programmes Sinn ergeben kann, da es u.a. ein ptrlist<T*> Konstrukt gibt, was eine Methode zum Löschen hat, auch hier ließe sich der Thread also füttern.