Ich verwende eine benutzerdefinierte Heap-Implementierung in einem meiner Projekte. Es besteht aus zwei Hauptteilen:Heap optimiert für (aber nicht beschränkt auf) single-threaded Verwendung
Feste Größe Block Heap. I.e. Ein Heap, der nur Blöcke einer bestimmten Größe zuweist. Er ordnet größere Speicherblöcke (entweder virtuelle Speicherseiten oder von einem anderen Heap) zu und teilt sie dann in atomare Zuordnungseinheiten auf.
Es führt die Zuweisung/Freigabe schnell (in O (1)) und es gibt keinen Speicherverbrauch Overhead, nicht berücksichtigt Dinge durch den externen Heap auferlegt.
Globaler Allzweck-Heap. Es besteht aus Eimern der oben genannten (festen Größe) Haufen. WRT die angeforderte Zuordnungsgröße wählt sie den entsprechenden Bucket und führt die Zuordnung über sie durch.
Da die gesamte Anwendung (schwer) Multi-Threaded ist - der globale Heap sperrt den entsprechenden Bucket während seiner Operation.
Hinweis: Im Gegensatz zu den herkömmlichen Heaps benötigt dieser Heap die Zuweisungsgröße nicht nur für die Zuweisung, sondern auch für die Freigabe. Dies ermöglicht es, den geeigneten Bucket ohne Suchen oder zusätzlichen Speicheraufwand zu identifizieren (z. B. Speichern der Blockgröße vor dem zugewiesenen Block). Obwohl etwas weniger bequem, ist das in meinem Fall in Ordnung. Da die "Bucket-Konfiguration" zur Kompilierungszeit bekannt ist (implementiert über C++ Template Voodoo), wird darüber hinaus der geeignete Bucket zur Kompilierungszeit bestimmt.
Bis jetzt sieht alles (und funktioniert) gut aus.
Vor kurzem arbeitete ich an einem Algorithmus, der Heap-Operationen stark ausführt und natürlich erheblich von der Heap-Leistung betroffen ist. Profiling ergab, dass seine Leistung erheblich durch die Verriegelung beeinflusst wird. Das heißt, der Heap selbst arbeitet sehr schnell (die typische Zuweisung umfasst nur ein paar Dereferenzierungsanweisungen), aber da die gesamte Anwendung Multi-Threading ist, wird der entsprechende Bucket durch den kritischen Abschnitt geschützt, der auf verblockten Anweisungen angewiesen ist sind viel schwerer.
Ich habe dies inzwischen behoben, indem ich diesem Algorithmus einen eigenen dedizierten Heap gebe, der nicht durch einen kritischen Abschnitt geschützt ist. Dies führt jedoch zu mehreren Problemen/Einschränkungen auf Codeebene. So wie die Notwendigkeit, die Kontextinformationen tief innerhalb des Stapels zu übertragen, wo auch immer der Heap erforderlich sein mag. Man kann TLS auch verwenden, um dies zu vermeiden, aber dies kann in meinem speziellen Fall zu Problemen beim Wiedereintritt führen.
Das lässt mich fragen: Gibt es eine bekannte Technik zur Optimierung des Heap für (aber nicht beschränkt auf) Singlethread-Nutzung?
EDIT:
Besonderer Dank geht an @Voo für die Annahme, die tcmalloc Google Check-out.
Es scheint ähnlich zu funktionieren, was ich mehr oder weniger (zumindest für kleine Objekte) getan habe. Aber sie lösen auch das genaue Problem, das ich habe, indem ich pro-thread caching behalte.
Ich dachte auch in diese Richtung, aber ich dachte über die Aufrechterhaltung per-Thread Heaps. Dann ist es etwas schwierig, einen Speicherblock freizugeben, der von dem zu einem anderen Thread gehörenden Heap zugewiesen wurde: Man sollte ihn in eine Art gesperrter Warteschlange einfügen, und dieser andere Thread sollte benachrichtigt werden und die ausstehenden Zuordnungen asynchron freigeben. Asynchronous Deallocation kann Probleme verursachen: Wenn dieser Thread aus irgendeinem Grund beschäftigt ist (z. B. führt eine aggressive Berechnungen) - tatsächlich tritt keine Speicherfreigabe auf. Plus in Multi-Threaded-Szenario sind die Kosten der Aufhebung der Zuordnung erheblich höher.
OTOH die Idee mit Caching scheint viel einfacher und effizienter. Ich werde versuchen, es auszuarbeiten.
Vielen Dank.
P. S .:
Tat Googles tcmalloc ist groß. Ich glaube, es ist ziemlich ähnlich wie das, was ich gemacht habe (zumindest fester Teil).
Aber, um pedantisch zu sein, gibt es eine Sache, wo mein Haufen überlegen ist. Nach Angaben von Doctors führt tcmalloc einen Overhead von ungefähr 1% (asymptotisch) ein, während mein Overhead 0,0061% beträgt. Es ist 4/64K um genau zu sein.
:)
Dies erinnert meine Tests ich vor Jahren getan haben. Der häufig verwendete "schlechte" Standardmechanismus benötigt mehr als 100 Mal eine gute "benutzerdefinierte" Implementierung. –
Ich würde gerne sehen, was Sie getan haben, wenn schneller als der Standard-Speicherzuordner. Da die meisten Standardimplementierungen bereits tun, was Sie vorgeben (und vieles mehr). Ich finde die O (1) Behauptung neugierig, besonders wenn Sie keinen Overhead beanspruchen (ich bin mir sicher, dass Sie einen schönen Pfennig verdienen werden, wenn Ihr Patent dafür durchgeht). –
Die gesamte Bucket-Idee ist im Grunde Googles tcmalloc (obwohl dies ein allgemeiner Allokator ist, muss er dynamisch entscheiden, welcher Bucket verwendet werden soll). tcmalloc verwendet lokalen Thread-Speicher, um genau Ihr Problem zu vermeiden, und reserviert nur selten aus dem allgemeinen Heap und vermeidet daher Sperren. – Voo