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

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.

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. )

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

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.

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".

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.

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.

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) )

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.

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.

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.

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 .

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 :-)

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").

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.

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.

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.