Überzeugende Beispiele für benutzerdefinierte C ++ - Allokatoren?

176

Was sind einige wirklich gute Gründe, sich std::allocatorfür eine kundenspezifische Lösung zu entscheiden? Sind Sie auf Situationen gestoßen, in denen dies für Korrektheit, Leistung, Skalierbarkeit usw. unbedingt erforderlich war? Irgendwelche wirklich klugen Beispiele?

Benutzerdefinierte Allokatoren waren schon immer eine Funktion der Standardbibliothek, für die ich nicht viel Bedarf hatte. Ich habe mich nur gefragt, ob jemand hier auf SO einige überzeugende Beispiele liefern könnte, um ihre Existenz zu rechtfertigen.

Naaff
quelle

Antworten:

121

Wie ich hier erwähne , hat der benutzerdefinierte STL-Allokator von Intel TBB die Leistung einer Multithread-App erheblich verbessert, indem einfach eine einzelne geändert wurde

std::vector<T>

zu

std::vector<T,tbb::scalable_allocator<T> >

(Dies ist eine schnelle und bequeme Möglichkeit, den Allokator auf die Verwendung von TBBs raffinierten Thread-Private-Heaps umzustellen. Siehe Seite 7 in diesem Dokument. )

Timday
quelle
3
Danke für den zweiten Link. Die Verwendung von Allokatoren zum Implementieren von Thread-privaten Heaps ist clever. Ich finde es gut, dass dies ein gutes Beispiel dafür ist, wo benutzerdefinierte Allokatoren in einem Szenario, das nicht auf Ressourcen beschränkt ist (Einbettung oder Konsole), einen klaren Vorteil haben.
Naaff
7
Der ursprüngliche Link ist jetzt nicht mehr vorhanden, aber CiteSeer hat das PDF: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.8289
Arto Bendiken
1
Ich muss fragen: Können Sie einen solchen Vektor zuverlässig in einen anderen Thread verschieben? (Ich
vermute
@sellibitze: Da die Vektoren innerhalb von TBB-Aufgaben manipuliert und über mehrere parallele Operationen hinweg wiederverwendet wurden und es keine Garantie gibt, welcher TBB-Worker-Thread Aufgaben aufnimmt, komme ich zu dem Schluss, dass dies einwandfrei funktioniert. Beachten Sie, dass es einige historische Probleme mit der TBB-Freigabe von Dingen gab, die in einem Thread in einem anderen Thread erstellt wurden (anscheinend ein klassisches Problem mit privaten Thread-Heaps und Zuordnungs- und Freigabemustern zwischen Produzenten und Verbrauchern. TBB behauptet, dass der Allokator diese Probleme vermeidet, aber ich habe etwas anderes gesehen Vielleicht in neueren Versionen behoben.)
Timday
@ArtoBendiken: Download-Link auf Ihren Link scheint nicht gültig zu sein.
Einpoklum
81

Ein Bereich, in dem benutzerdefinierte Allokatoren nützlich sein können, ist die Spieleentwicklung, insbesondere auf Spielekonsolen, da sie nur wenig Speicher und keinen Austausch haben. Auf solchen Systemen möchten Sie sicherstellen, dass Sie die Kontrolle über jedes Subsystem haben, damit ein unkritisches System nicht den Speicher eines kritischen Systems stehlen kann. Andere Dinge wie Pool-Allokatoren können helfen, die Speicherfragmentierung zu reduzieren. Ein langes, detailliertes Papier zum Thema finden Sie unter:

EASTL - Standardvorlagenbibliothek für elektronische Künste

Grumbel
quelle
14
+1 für EASTL-Link: "Unter den Spieleentwicklern ist die grundlegendste Schwäche [der STL] das Standard-Allokator-Design, und diese Schwäche hat am meisten zur Schaffung von EASTL beigetragen."
Naaff
65

Ich arbeite an einem mmap-Allokator, mit dem Vektoren Speicher aus einer Speicherzuordnungsdatei verwenden können. Das Ziel besteht darin, Vektoren zu haben, die Speicher verwenden, die sich direkt im virtuellen Speicher befinden, der von mmap zugeordnet wird. Unser Problem besteht darin, das Lesen wirklich großer Dateien (> 10 GB) ohne Kopieraufwand in den Speicher zu verbessern. Daher benötige ich diesen benutzerdefinierten Allokator.

Bisher habe ich das Grundgerüst eines benutzerdefinierten Allokators (der von std :: allocator abgeleitet ist). Ich denke, es ist ein guter Ausgangspunkt, um eigene Allokatoren zu schreiben. Fühlen Sie sich frei, diesen Code so zu verwenden, wie Sie möchten:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Um dies zu verwenden, deklarieren Sie einen STL-Container wie folgt:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

Es kann zum Beispiel verwendet werden, um zu protokollieren, wann immer Speicher zugewiesen wird. Notwendig ist die Rebind-Struktur, andernfalls verwendet der Vektorcontainer die Zuordnungs- / Freigabemethoden der Oberklassen.

Update: Der Speicherzuordnungszuweiser ist jetzt unter https://github.com/johannesthoma/mmap_allocator verfügbar und ist LGPL. Fühlen Sie sich frei, es für Ihre Projekte zu verwenden.

Johannes Thoma
quelle
17
Nur ein Kopf hoch, abgeleitet von std :: allocator, ist nicht wirklich die idiomatische Art, Allokatoren zu schreiben. Sie sollten sich stattdessen allocator_traits ansehen, mit dem Sie ein Minimum an Funktionalität bereitstellen können, und die Merkmalsklasse liefert den Rest. Beachten Sie, dass die STL Ihren Allokator immer über allocator_traits verwendet, nicht direkt, sodass Sie nicht selbst auf allocator_traits verweisen müssen. Es gibt keinen großen Anreiz, von std :: allocator abzuleiten (obwohl dieser Code unabhängig davon ein hilfreicher Ausgangspunkt sein kann).
Nir Friedman
25

Ich arbeite mit einer MySQL-Speicher-Engine, die c ++ für ihren Code verwendet. Wir verwenden einen benutzerdefinierten Allokator, um das MySQL-Speichersystem zu verwenden, anstatt mit MySQL um Speicher zu konkurrieren. Dadurch können wir sicherstellen, dass wir den Speicher verwenden, für den der Benutzer MySQL konfiguriert hat, und nicht "extra".

Thomas Jones-Low
quelle
21

Es kann nützlich sein, benutzerdefinierte Allokatoren zu verwenden, um einen Speicherpool anstelle des Heaps zu verwenden. Das ist ein Beispiel unter vielen anderen.

In den meisten Fällen handelt es sich sicherlich um eine vorzeitige Optimierung. In bestimmten Kontexten (eingebettete Geräte, Spiele usw.) kann dies jedoch sehr nützlich sein.

Martin Cote
quelle
3
Oder wenn dieser Speicherpool gemeinsam genutzt wird.
Anthony
9

Ich habe keinen C ++ - Code mit einem benutzerdefinierten STL-Allokator geschrieben, aber ich kann mir einen in C ++ geschriebenen Webserver vorstellen, der einen benutzerdefinierten Allokator zum automatischen Löschen temporärer Daten verwendet, die für die Beantwortung einer HTTP-Anfrage erforderlich sind. Der benutzerdefinierte Allokator kann alle temporären Daten auf einmal freigeben, sobald die Antwort generiert wurde.

Ein weiterer möglicher Anwendungsfall für einen benutzerdefinierten Allokator (den ich verwendet habe) ist das Schreiben eines Komponententests, um zu beweisen, dass das Verhalten einer Funktion nicht von einem Teil ihrer Eingabe abhängt. Der benutzerdefinierte Allokator kann den Speicherbereich mit einem beliebigen Muster füllen.

pts
quelle
5
Es scheint, dass das erste Beispiel die Aufgabe des Destruktors ist, nicht des Allokators.
Michael Dorst
2
Wenn Sie sich Sorgen um Ihr Programm machen, abhängig vom anfänglichen Speicherinhalt des Heaps, werden Sie durch einen schnellen (dh über Nacht!) Lauf in valgrind auf die eine oder andere Weise informiert.
cdyson37
3
@anthropomorphic: Der Destruktor und der benutzerdefinierte Allokator würden zusammenarbeiten, der Destruktor würde zuerst ausgeführt, dann das Löschen des benutzerdefinierten Allokators, der noch nicht frei (...), sondern frei (...) aufgerufen wird später, wenn die Bearbeitung der Anfrage beendet ist. Dies kann schneller als der Standardzuweiser sein und die Adressraumfragmentierung verringern.
Punkte
8

Bei der Arbeit mit GPUs oder anderen Co-Prozessoren ist es manchmal vorteilhaft, Datenstrukturen im Hauptspeicher auf besondere Weise zuzuweisen . Diese spezielle Art der Speicherzuweisung kann auf bequeme Weise in einem benutzerdefinierten Zuweiser implementiert werden.

Der Grund, warum die benutzerdefinierte Zuweisung über die Beschleunigerlaufzeit bei der Verwendung von Beschleunigern von Vorteil sein kann, ist folgender:

  1. Durch benutzerdefinierte Zuweisung wird die Beschleunigerlaufzeit oder der Treiber über den Speicherblock informiert
  2. Darüber hinaus kann das Betriebssystem sicherstellen, dass der zugewiesene Speicherblock seitengesperrt ist (manche nennen diesen fixierten Speicher ), dh das virtuelle Speichersubsystem des Betriebssystems verschiebt oder entfernt die Seite möglicherweise nicht innerhalb oder aus dem Speicher
  3. Wenn 1. und 2. Halten und eine Datenübertragung zwischen einem seitengesperrten Speicherblock und einem Beschleuniger angefordert wird, kann die Laufzeit direkt auf die Daten im Hauptspeicher zugreifen, da sie weiß, wo sie sich befinden, und sicher sein kann, dass das Betriebssystem dies nicht getan hat verschieben / entfernen
  4. Dadurch wird eine Speicherkopie gespeichert, die bei Speicher auftreten würde, der nicht seitengesperrt zugewiesen wurde: Die Daten müssen im Hauptspeicher in einen seitengesperrten Staging-Bereich kopiert werden, von dem aus der Beschleuniger die Datenübertragung initialisieren kann (über DMA) )
Sebastian
quelle
1
... nicht zu vergessen seitenausgerichtete Speicherblöcke. Dies ist besonders nützlich, wenn Sie mit einem Treiber sprechen (dh mit FPGAs über DMA) und nicht den Aufwand und den Aufwand für die Berechnung von In-Page-Offsets für Ihre DMA-Streulisten benötigen.
Jan
7

Ich verwende hier benutzerdefinierte Allokatoren. man könnte sogar sagen , es war zu arbeiten , um andere benutzerdefinierte dynamische Speicherverwaltung.

Hintergrund: Wir haben Überladungen für malloc, calloc, free und die verschiedenen Varianten von Operator new und delete, und der Linker lässt STL diese gerne für uns verwenden. Auf diese Weise können wir Dinge wie das automatische Pooling kleiner Objekte, die Lecksuche, die Zuweisung von Zuordnungen, die freie Befüllung, die Polsterzuweisung mit Wachposten, die Ausrichtung der Cache-Zeilen für bestimmte Zuordnungen und die verzögerte Freigabe durchführen.

Das Problem ist, dass wir in einer eingebetteten Umgebung arbeiten - es ist nicht genügend Speicher vorhanden, um die Abrechnungserkennung über einen längeren Zeitraum ordnungsgemäß durchzuführen. Zumindest nicht im Standard-RAM - über benutzerdefinierte Zuweisungsfunktionen steht an anderer Stelle ein weiterer RAM-Haufen zur Verfügung.

Lösung: Schreiben Sie einen benutzerdefinierten Allokator, der den erweiterten Heap verwendet, und verwenden Sie ihn nur in den Interna der Speicherleck-Tracking-Architektur. Alles andere verwendet standardmäßig die normalen Neu- / Löschüberladungen, die das Leck-Tracking durchführen. Dies vermeidet die Verfolgung des Trackers selbst (und bietet auch ein bisschen zusätzliche Packfunktionalität, wir kennen die Größe der Trackerknoten).

Aus dem gleichen Grund verwenden wir dies auch, um Daten zur Funktionskostenprofilierung zu speichern. Das Schreiben eines Eintrags für jeden Funktionsaufruf und jede Rückgabe sowie von Thread-Schaltern kann schnell teuer werden. Der benutzerdefinierte Allokator gibt uns wieder kleinere Allokationen in einem größeren Debug-Speicherbereich.

schlanker
quelle
5

Ich verwende einen benutzerdefinierten Allokator, um die Anzahl der Allokationen / Freigaben in einem Teil meines Programms zu zählen und zu messen, wie lange es dauert. Es gibt andere Möglichkeiten, wie dies erreicht werden könnte, aber diese Methode ist für mich sehr praktisch. Es ist besonders nützlich, dass ich den benutzerdefinierten Allokator nur für eine Teilmenge meiner Container verwenden kann.

Jørgen Fogh
quelle
4

Eine wesentliche Situation: Wenn Sie Code schreiben, der über Modulgrenzen (EXE / DLL) hinweg funktionieren muss, ist es wichtig, dass Ihre Zuweisungen und Löschungen nur in einem Modul erfolgen.

Wo ich darauf gestoßen bin, war eine Plugin-Architektur unter Windows. Wenn Sie beispielsweise einen std :: string über die DLL-Grenze übergeben, ist es wichtig, dass alle Neuzuweisungen des Strings von dem Heap erfolgen, von dem er stammt, NICHT vom Heap in der DLL, der möglicherweise anders ist *.

* Es ist tatsächlich komplizierter als dies, als ob Sie dynamisch mit der CRT verknüpfen, könnte dies sowieso funktionieren. Wenn jedoch jede DLL eine statische Verbindung zur CRT hat, befinden Sie sich in einer Welt voller Schmerzen, in der ständig Fehler bei der Phantomzuweisung auftreten.

Stephen
quelle
Wenn Sie Objekte über DLL-Grenzen hinweg übergeben, sollten Sie für beide Seiten die Einstellung Multi-Threaded (Debug) DLL (/ MD (d)) verwenden. C ++ wurde nicht für die Modulunterstützung entwickelt. Alternativ können Sie alles hinter COM-Schnittstellen abschirmen und CoTaskMemAlloc verwenden. Dies ist der beste Weg, um Plugin-Schnittstellen zu verwenden, die nicht an einen bestimmten Compiler, eine bestimmte STL oder einen bestimmten Anbieter gebunden sind.
Gast128
Die alten Leute regeln dafür: Tu es nicht. Verwenden Sie keine STL-Typen in der DLL-API. Und geben Sie keine dynamische speicherfreie Verantwortung über die Grenzen der DLL-API hinweg weiter. Es gibt kein C ++ - ABI. Wenn Sie also jede DLL als C-API behandeln, vermeiden Sie eine ganze Klasse potenzieller Probleme. Natürlich auf Kosten von "c ++ beauty". Oder wie der andere Kommentar schon sagt: Verwenden Sie COM. Nur einfaches C ++ ist eine schlechte Idee.
BitTickler
3

Ein Beispiel für die Zeit, in der ich diese verwendet habe, war die Arbeit mit eingebetteten Systemen mit sehr eingeschränkten Ressourcen. Nehmen wir an, Sie haben 2k RAM frei und Ihr Programm muss einen Teil dieses Speichers verwenden. Sie müssen beispielsweise 4-5 Sequenzen an einem Ort speichern, der sich nicht auf dem Stapel befindet, und außerdem müssen Sie sehr genau darauf zugreifen können, wo diese Dinge gespeichert werden. In dieser Situation möchten Sie möglicherweise Ihren eigenen Allokator schreiben. Die Standardimplementierungen können den Speicher fragmentieren. Dies ist möglicherweise nicht akzeptabel, wenn Sie nicht über genügend Speicher verfügen und Ihr Programm nicht neu starten können.

Ein Projekt, an dem ich arbeitete, war die Verwendung von AVR-GCC auf einigen Chips mit geringer Leistung. Wir mussten 8 Sequenzen variabler Länge speichern, aber mit einem bekannten Maximum. Die Standardbibliotheksimplementierung der Speicherverwaltungist ein dünner Wrapper um malloc / free, der verfolgt, wo Elemente platziert werden sollen, indem jedem zugewiesenen Speicherblock ein Zeiger vorangestellt wird, der kurz nach dem Ende des zugewiesenen Speicherbereichs liegt. Beim Zuweisen eines neuen Speicherstücks muss der Standardzuweiser jedes der Speicherelemente durchlaufen, um den nächsten verfügbaren Block zu finden, in den die angeforderte Speichergröße passt. Auf einer Desktop-Plattform wäre dies für diese wenigen Elemente sehr schnell, aber Sie müssen bedenken, dass einige dieser Mikrocontroller im Vergleich sehr langsam und primitiv sind. Darüber hinaus war das Problem der Speicherfragmentierung ein massives Problem, das bedeutete, dass wir wirklich keine andere Wahl hatten, als einen anderen Ansatz zu wählen.

Wir haben also unseren eigenen Speicherpool implementiert . Jeder Speicherblock war groß genug, um die größte Sequenz aufzunehmen, die wir darin benötigen würden. Dadurch wurden Speicherblöcke mit fester Größe im Voraus zugewiesen und markiert, welche Speicherblöcke derzeit verwendet wurden. Wir haben dies getan, indem wir eine 8-Bit-Ganzzahl beibehalten haben, wobei jedes Bit dargestellt wurde, wenn ein bestimmter Block verwendet wurde. Wir haben hier die Speichernutzung gegen den Versuch eingetauscht, den gesamten Prozess zu beschleunigen, was in unserem Fall gerechtfertigt war, als wir diesen Mikrocontroller-Chip nahe an seine maximale Verarbeitungskapazität gebracht haben.

Es gibt eine Reihe anderer Fälle, in denen ich sehe, wie Sie Ihren eigenen benutzerdefinierten Allokator im Kontext eingebetteter Systeme schreiben, beispielsweise wenn sich der Speicher für die Sequenz nicht im Haupt-RAM befindet, wie dies auf diesen Plattformen häufig der Fall ist .

Shuttle87
quelle
3

Obligatorischer Link zu Andrei Alexandrescus CppCon 2015-Vortrag über Allokatoren:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

Das Schöne ist, dass man sich schon bei der Entwicklung Gedanken darüber macht, wie man sie verwenden würde :-)

einpoklum
quelle
2

Für den gemeinsam genutzten Speicher ist es wichtig, dass nicht nur der Containerkopf, sondern auch die darin enthaltenen Daten im gemeinsam genutzten Speicher gespeichert werden.

Der Allokator von Boost :: Interprocess ist ein gutes Beispiel. Wie Sie hier lesen können , reicht dies jedoch nicht aus, um alle gemeinsam genutzten Speicher von STL-Containern kompatibel zu machen (aufgrund unterschiedlicher Zuordnungsversätze in unterschiedlichen Prozessen können Zeiger "brechen").

ted
quelle
2

Vor einiger Zeit fand ich diese Lösung sehr nützlich für mich: Schneller C ++ 11-Allokator für STL-Container . Es beschleunigt STL-Container sowohl auf VS2017 (~ 5x) als auch auf GCC (~ 7x) leicht. Es ist ein Allokator für spezielle Zwecke, der auf dem Speicherpool basiert. Es kann nur dank des von Ihnen gewünschten Mechanismus mit STL-Containern verwendet werden.

niemand besonderes
quelle
1

Ich persönlich verwende Loki :: Allocator / SmallObject, um die Speichernutzung für kleine Objekte zu optimieren. Es zeigt eine gute Effizienz und zufriedenstellende Leistung, wenn Sie mit moderaten Mengen wirklich kleiner Objekte (1 bis 256 Byte) arbeiten müssen. Es kann bis zu 30-mal effizienter sein als die Standardzuweisung von Neuem / Löschen in C ++, wenn wir über das Zuweisen moderater Mengen kleiner Objekte mit vielen verschiedenen Größen sprechen. Es gibt auch eine VC-spezifische Lösung namens "QuickHeap", die die bestmögliche Leistung bietet (Zuordnungs- und Freigabevorgänge lesen und schreiben einfach die Adresse des Blocks, der dem Heap zugewiesen / zurückgegeben wird, bzw. in bis zu 99 Fällen. (9)% - hängt von den Einstellungen und der Initialisierung ab), kostet jedoch einen erheblichen Overhead - es werden zwei Zeiger pro Extent und ein zusätzlicher für jeden neuen Speicherblock benötigt. Es'

Das Problem bei der Standardimplementierung von C ++ new / delete ist, dass es normalerweise nur ein Wrapper für die Zuweisung von C malloc / free ist und für größere Speicherblöcke wie 1024+ Bytes gut funktioniert. Es hat einen bemerkenswerten Overhead in Bezug auf Leistung und manchmal zusätzlichen Speicher, der auch für die Zuordnung verwendet wird. In den meisten Fällen werden benutzerdefinierte Zuweiser so implementiert, dass die Leistung maximiert und / oder der zusätzliche Speicherbedarf für die Zuweisung kleiner Objekte (≤ 1024 Byte) minimiert wird.

Fraktale Multiversität
quelle
1

In einer Grafiksimulation habe ich benutzerdefinierte Allokatoren gesehen, für die verwendet wurde

  1. Ausrichtungsbeschränkungen, std::allocatordie nicht direkt unterstützt wurden.
  2. Minimierung der Fragmentierung durch Verwendung separater Pools für kurzlebige (nur diesen Rahmen) und langlebige Zuordnungen.
Adrian McCarthy
quelle