boost::pool performance/alternative gesucht

[pool]

Also, bin jetzt mit meiner kleinen Implementierung durch, momentan verwalte ich dass ganze in 3 Containern:

typedef std::set<void*> ptrcontainer;//enthält die void* jeweils einer größe
	typedef std::map<size_t,ptrcontainer > Alloclist;// 2 listen, alloc und freelist
	typedef std::multimap<void*,size_t> Memlist;//eine liste aller allokierten pointer

In alloc landet alles was allokiert wird, bei dealloc landet der Inhalt dann in freelist. Frage mich hier ob es da noch eine effektivere Lösung gibt, das set ist schon mal um einiges besser als vector
Memlist brauche ich zur Zeit um schnell die Größe eines Pointers zu bekommen.

[Maxi]

pumuckl schrieb:

Maxi schrieb:

ich glaube im Buch von Alexandrescu (Modern C++ Design) war beschrieben, wie man einen Allocator für viele kleine Allokationen schreibt.

[urlhttp://www.drdobbs.com/cpp/184402039;jsessionid=TQIXAVFJCDBYVQE1GHOSKHWATMY32JVN]hier[/url] lässt sich Alexandrescu darüber aus, dass genau dieses Kapitel weniger zu seinen Glanzleistungen gehört, darüber kommt man dann auch auf meinen Link

Das wusste ich natürlich nicht Ich fand das Buch ziemlich gut und daher dachte ich auch, der Allokator sei gut. Aber wieder was gelernt

[pool]

Frage mich gerade, was bei der Freelist als container für die void* am besten ist:
vector, deque oder doch set.
Momentan mit set ist es schon recht gut, für die allocliste ergibt dies auch sinn.
Die Freeliste aber verwaltet ja nur eine liste mit pointern. Evtl. auch eien list oder slist?

[hustbaer]

pool schrieb:

pumuckl schrieb:

schau mal hier, vielleicht ist das was für dich:

http://www.hoard.org/

Ich verwende schon tcmalloc von google, schreibe jetzt erstmal einen DummyArray Allokator, welcher nur eine einfache freelist hat. Jeweils nach ArrayGröße in STL Containern dann verwaltet.

Hast du dir die Implementierung von tcmalloc mal angesehen? Ich denke nicht dass du mit einem selbstgebackenen Allokator gegenüger tcmalloc viel wirst rausholen können.
Die ganzen Tricks wie eigene Freelisten pro Allokationsgrösse etc. sind da alle schon drinnen...

[xor]

Oh... das ist aber ein sehr sehr interessantes Thema, dass ihr da angeht ... und ich lese es mit Spannung

Da möchte ich nur ganz am Rande einwerfen, dass ich mir schon länger die Frage stelle, warum der C / C++ Standard nur sehr wenige Speicher-Funktionen zur Verfügung stellt und man einem malloc überhaupt keine weiteren Parameter für eine effizientere Nutzung offenlegt.

Dabei stieß ich zumindest unter Windows auf die Heap-APIs mit denen man an ein paar Schrauben drehen kann. Zumindest kann man mit mehreren Heaps bei deaktivierter Zugriffsserialisierung sicher unnötige Locks vermeiden und Low-Fragmentation-Settings haben ja bereits ein Logik für bessere Verteilung von großen und kleinen Speicherblöcken kernelseitig eingebaut.

Aber das ganze ist natürlich hochgradig systemabhängig und kann sicher einen auf den Bedarf optimierten Allokator nicht ersetzen. Unter POSIX kenne ich überhaupt keine detailierteren Standard-APIs.
Ich find's eben nur schade, das DIE Performance-Sprache C++ gerade bei Heap-Operationen nicht wenigstens ein paar Features des Systems verallgemeinert zur Verfügung stellt. Schließlich wird ja sowieso jede Speicheranfordung nochmals vom System/Kernel gemanged.

mfG XOR

[unskilled]

und man einem malloc überhaupt keine weiteren Parameter für eine effizientere Nutzung offenlegt.

das stimmt so nicht ganz...
da in c++ ohnehin das allocator-konzept (hauptsächlich durch den standard bedingt) genutzt wird/werden sollte, schreibt man sich halt extra allokatoren und dort hat allocate noch nen optionalen void-pointer als "hint" - da kann man sich also was ausdenken und es wird auch überall mit jedem allocator funktionieren - manche(fast alle) werden das ignorieren, aber dein eigener z.bsp. wohl eher nicht ;o)

bb

[pool]

hustbaer schrieb:

pool schrieb:

pumuckl schrieb:

schau mal hier, vielleicht ist das was für dich:

http://www.hoard.org/

Ich verwende schon tcmalloc von google, schreibe jetzt erstmal einen DummyArray Allokator, welcher nur eine einfache freelist hat. Jeweils nach ArrayGröße in STL Containern dann verwaltet.

Hast du dir die Implementierung von tcmalloc mal angesehen? Ich denke nicht dass du mit einem selbstgebackenen Allokator gegenüger tcmalloc viel wirst rausholen können.
Die ganzen Tricks wie eigene Freelisten pro Allokationsgrösse etc. sind da alle schon drinnen...

Naja, unter Windows wirds schwierig, ich versuche es halt einfach.
Der Hauptcode liegt in DLLs, welche MT gelinkt werden, d.h. da kann TCMalloc sowieso nicht viel ausrichten. (Wir nutzen auch JNI mit den DLLs, daher auch keine Möglichkeit dagegen in der DLL zu linken).
Ich versuche halt wenigstens die Allokationen welche ich über den MemoryManager beinflussen kann so optimal wie möglich hinzubekommen.

[pool]

Kennst VS eigentlich slist nicht? Bzw. ist slist überhaupt standard?
Habe gerade die Freelist als list implementiert, tut aber in der Geschwindigkeit nicht viel(eigentlich garnichts gegenüber set).

Noch eine Frage, würde es evtl. was bringen die Allokierungen in einen Producer Thread zu verlagern, so das die Freelisten immer zu x Blöcken aufgefüllt werden?
Würde für den Speicherverbrauch sicher nicht das beste sein, aber evtl. den Importthread beschleunigen.

[pool]

So, einen Vorteil den so ein custom Allocator hat, ist ja das man sich Statistiken mit generieren kann:

Verwendete Blockgrößen: 431 (1-524288  sizeof(XMLCh))
Insgesamt 14624472 Allokierungen
Davon 430162 durch new[] und 14194310 aus der Freelist.

Der Großteil der Allokierungen spielt sich in den Größen 1-100 ab, darüber gibt es dann immer mehr werte die nur einmal allokiert werden.

Frage mich jetzt ob sich für die knapp 400000 new[] Aufrufe ein eigener Thread lohnen würde, der einen Teil davon schon mal für die Freeliste vorallokiert.
Somit würde der Hauptthread damit nicht mehr belastet. Allerdings wäre dies auch komplex, da ich ja einen Wert benötige, was wie oft allokiert werden sollte.

Die Zahlen stammen übrigens aus dem Import einer 150 mb XML Datei, bis zu 500 mb sind möglich.

[xor]

Hi @pool,

Sorry dass ich da etwas abseits nachfrage, aber: Wird bei deinen new-Aufrufen nur die Ausführung langsamer oder bläht sich einfach der Speicher auf, was zu permanentem Paging auf dem System führt? Ich habe da nämlich ein vergleichbares Problem und bin derzeit bemüht die Anzahl der Allokationen zu reduzieren, weil bei diesem Projekt einige XML und CSV files gelesen und in recht üppige Objekt-Strukturen übertragen werden obwohl für die finale Auswertung dann immer nur ein Bruchteil dieser Daten benötigt werden. Im Einzelfall wirkt sich das Programm nicht so extrem aus, nur auf einem Server, der noch ein paar andere Aufgaben hat kommt es dann gelegentlich zum Festplatten-glühen.
Deshalb experimentiere ich an vielen Stellen herum, um den Speicherbedarf zu reduzieren. Mich interessiert da vor allem, ob eine intensive Benutzung von mem-pools nicht relativ viel Overhead und Speicherfragmentierung erzeugt, die dann eben auf Kosten des Paging gehen. (Anmerkung: Besagtes Programm zeichnet sich durch viele news aus, die erst am Programm-Ende deleted werden - das ist aber nicht (nur) auf meinem Mist gewachsen... )

Läßt sich da ein Trend ablesen zwischen den von new angeforderten Bytes und dem tatsächlich verwendetem Speicher?
Ich hatte nämlich den Vermutung, dass viel Overhead zusammenkommen, wenn jeder std::vector oder std::string immer um 50% über-allokiert und ich dann 5000 vectoren oder strings mit jeweils geringem Inhalt (-> XML nodes) anlege.
Wachsen da pool-listen für viele kleine Allokationen nicht übermäßig an?

lg XOR

das stimmt so nicht ganz...
da in c++ ohnehin das allocator-konzept (hauptsächlich durch den standard bedingt) genutzt wird/werden sollte, schreibt man sich halt extra allokatoren und dort hat allocate noch nen optionalen void-pointer als "hint" - da kann man sich also was ausdenken und es wird auch überall mit jedem allocator funktionieren - manche(fast alle) werden das ignorieren, aber dein eigener z.bsp. wohl eher nicht ;o)

Ja, ist schon richtigt ... aber dann darf sich der Programmierer abmühen eine Lösung für Windows, Linux und co selbst zu finden und zu supporten. Ich gestehe aber, dass ich mir nicht anmaßen möchte so eine system-nahe "mallocex" Funktion plattform-übergreifend zu planen und zu implementieren ... Änderungen am C/C++ wurden und werden ja immer sehr heftig diskutiert Also bleiben wir bei den bekannten libs!

[pool]

xor schrieb:

Sorry dass ich da etwas abseits nachfrage, aber: Wird bei deinen new-Aufrufen nur die Ausführung langsamer oder bläht sich einfach der Speicher auf, was zu permanentem Paging auf dem System führt? Ich habe da nämlich ein vergleichbares Problem und bin derzeit bemüht die Anzahl der Allokationen zu reduzieren, weil bei diesem Projekt einige XML und CSV files gelesen und in recht üppige Objekt-Strukturen übertragen werden obwohl für die finale Auswertung dann immer nur ein Bruchteil dieser Daten benötigt werden. Im Einzelfall wirkt sich das Programm nicht so extrem aus, nur auf einem Server, der noch ein paar andere Aufgaben hat kommt es dann gelegentlich zum Festplatten-glühen.

Also der Speicherverbrauch ist jetzt nicht großartig mehr, aber auch nicht weniger. Der Speichermanager von Windows scheint schon recht effizient zu sein, das Upgrade auf Xerces 3.1 hat da schon mehr gebracht.

Mir gings hier eben auch darum, das ich selber Statistiken bekomme, was wie allokiert wird, denn erst dann kann man sehen, wo es evtl. Baustellen für die Optimierung gibt. Wenn das jetzt auch noch besser oder schneller wäre ein netter nebeneffekt, aber hustbaer hat da schon recht, tcmalloc und auch der native Windows Allokator sind schon recht gut.

Deshalb experimentiere ich an vielen Stellen herum, um den Speicherbedarf zu reduzieren. Mich interessiert da vor allem, ob eine intensive Benutzung von mem-pools nicht relativ viel Overhead und Speicherfragmentierung erzeugt, die dann eben auf Kosten des Paging gehen. (Anmerkung: Besagtes Programm zeichnet sich durch viele news aus, die erst am Programm-Ende deleted werden - das ist aber nicht (nur) auf meinem Mist gewachsen... )

Kann ich nicht beantworten, die Applikation tut noch zu viel sachen, als das ich da ein gesamt Bild hätte. Denke mittlerweile das die Hauptbaustelle die Schnittstelle zur DB ist, das Programm zu Optimieren über die Allokierungen ist dagegen wohl mit tcmalloc und ähnlichen Alternativen effektiver.
Da ich aber das DLL Problem habe, und somit sowieso einen MemoryManager brauchte, um diesen an Xerces zu übergeben, habe ich auch gleich noch einen Allokator gebaut, auch um weitere Möglichkeiten auszuloten (z.b. das New in einem eigenen Thread zu machen).

Läßt sich da ein Trend ablesen zwischen den von new angeforderten Bytes und dem tatsächlich verwendetem Speicher?
Ich hatte nämlich den Vermutung, dass viel Overhead zusammenkommen, wenn jeder std::vector oder std::string immer um 50% über-allokiert und ich dann 5000 vectoren oder strings mit jeweils geringem Inhalt (-> XML nodes) anlege.
Wachsen da pool-listen für viele kleine Allokationen nicht übermäßig an?

STL wird hier nicht viel verwendet, wie gesagt, das ist alles eine Xerces Geschichte, und Xerces hat für vieles eine eigene Api. Auch z.b. einen StringPool, Xerces ist also schon selber recht performant.

[cool-]

RapidXml

[Shade Of Mine]

Die ganzen Allokationen kann man killen indem man die XML Datei in den Speicher mapt und dann nur nocopy-strings darauf fährt, also keine neuen allokationen machst sondern direkt den auf den gemapten daten arbeitet.

rapidxml, wie mein vorredner erwähnt hat, macht das zB genauso.

generell ist dieses dauernde kopieren meistens unnötig. strings kann man, wenn es ums parsen von dateien geht, super als nocopy-strings fahren und erst wenn die datei geschlossen wird, sprich das parsen fertig ist, erst dann eine kopie der daten ziehen.

(nocopy string ist für mich eine string klasse die nur aus 2 zeigern besteht: auf begin und end der zeichenkette und den speicher selber aber nicht besitzt)

[pool]

Shade Of Mine schrieb:

Die ganzen Allokationen kann man killen indem man die XML Datei in den Speicher mapt und dann nur nocopy-strings darauf fährt, also keine neuen allokationen machst sondern direkt den auf den gemapten daten arbeitet.

rapidxml, wie mein vorredner erwähnt hat, macht das zB genauso.

Also jetzt wirds offtopic, XML Parser sind noch mal ein eigenes Thema.
Und gerade da kann rapidXML eine Lösung wie Xerces nicht ersetzen, fehlende Valdierung, Namespacesupport, SAX etc. All das kann Rapid zur Zeit nicht.

[xor]

@pool

Danke für deine ausführlichen Infos :), da sieht man was ein vollständiger XML parser leisten muss. Ich hab da ja nur so einen primitiven selbstgebauten mini-parser der nur einfache Tags auslesen kann, weil die zu verarbeitenden Daten auch nur einfachste Strukturen aus einem uralten Fremdprogramm sind. Ist natürlich was ganz was anderes wenn man weitere Komponenten einsetzt und XML auch richtiges XML ist (http://www.virtualdub.org/blog/pivot/entry.php?id=251)

Zu den Listen: Ich bin da kein Experte aber ev. möchtest du ja weitere Container einsetzen.
vector ist ja nur ein einfaches Array bei dem Zugriffe schnell aber suchen, einfügen und löschen langsamer sind.
set und map müssten binäre Bäume sein.
Da kann dir vielleicht eine Hashtable mit einer guten Hashfunktion helfen [O(1)] mittels boost::hash und unordered_set. Das ist wieder das Schöne an C++ - man kann gerne mal einen Container durch einen anderen tauschen und ein paar Tests machen, ob es besser wird

lg XOR

PS: @Shade Of Mine: Zumindest der XML-Parser setzt bereits String-Verweise statt Kopien ein ... aber ... Hmm ... die Files in den Speicher zu mappen ... könnte das mein Gral sein ... probier ich mal ... ist sicher effizienter als alle Files einzeln zu öffnen und in den Speicher zu kopieren.

[pool]

Also unordered_map und unordered_set hat jetzt wirklich noch mal was gebracht, wenn auch wenig.
Problem ist aber, das ich auch Solaris8 als Plattform habe, und boost wohl mit so einem alten Compiler nicht baut. Wäre nämlich auch im Programm selber nett wenn man das nutzen könnte, da gibt es einige Klassen welche von einer std::list<T*> erben.
Das könnte man Prima durch ein Multiset ersetzen.

Und zu den Containern: Vector ist wegen seines Kopierverhaltens und Speicherverbrauch hier keine Alternative. std::list ist besser, aber std::set ist da mit dem binären Baum einfach schneller.

[Shade Of Mine]

pool schrieb:

Also jetzt wirds offtopic, XML Parser sind noch mal ein eigenes Thema.
Und gerade da kann rapidXML eine Lösung wie Xerces nicht ersetzen, fehlende Valdierung, Namespacesupport, SAX etc. All das kann Rapid zur Zeit nicht.

Man muss immer ein trade-off zwischen features und performance machen. aber nocopy strings sind ein super weg um zuviele allokationen zu vermeiden. das alleine ist zB kein grund keine validierung, ns support, etc. zu haben...

[pool]

Shade Of Mine schrieb:

pool schrieb:

Also jetzt wirds offtopic, XML Parser sind noch mal ein eigenes Thema.
Und gerade da kann rapidXML eine Lösung wie Xerces nicht ersetzen, fehlende Valdierung, Namespacesupport, SAX etc. All das kann Rapid zur Zeit nicht.

Man muss immer ein trade-off zwischen features und performance machen. aber nocopy strings sind ein super weg um zuviele allokationen zu vermeiden. das alleine ist zB kein grund keine validierung, ns support, etc. zu haben...

Ja, mag ja sein. Aber 500 mb lassen sich so halt nicht wirklich parsen. Das ist zu Speicherintensiv.

Und rapidxml mit xerces zu vergleichen ist Äpfel mit Birnen zu gleichen.
Mein Problem ist ja, das wir bereits Xerces nutzen, und die Features benötigen.
Aber wie gesagt, das ist dann auch wieder Offtopic.

Interessant wäre ein Parser welcher das Speicherverhalten und andere Dinge über eine Strategy einstellbar machen würde. Der Parsingteil ließe sich zb. mit boost::spirit machen, aber support von DTD, Schema, Namespaces ist alles andere als Trivial.