wake-up-neo.net

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

Was sind einige wirklich gute Gründe, um std::allocator für eine individuelle Lösung? Haben Sie Situationen erlebt, in denen dies für Korrektheit, Leistung, Skalierbarkeit usw. unbedingt erforderlich war? Irgendwelche wirklich klugen Beispiele?

Benutzerdefinierte Zuweiser waren schon immer ein Feature der Standardbibliothek, für das ich nicht viel gebraucht habe. Ich habe mich nur gefragt, ob jemand hier auf SO) überzeugende Beispiele liefern könnte, um ihre Existenz zu rechtfertigen.

164
Naaff

Wie ich hier erwähne, konnte ich feststellen, dass der benutzerdefinierte STL-Allokator von Intel TBB die Leistung einer Multithread-App durch einfaches Ändern einer einzelnen deutlich verbessert

std::vector<T>

zu

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

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

111
timday

Ein Bereich, in dem benutzerdefinierte Zuweiser nützlich sein können, ist die Spieleentwicklung, insbesondere auf Spielekonsolen, da sie nur wenig Arbeitsspeicher und keinen Swap 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. Sie finden ein langes, detailliertes Papier zum Thema unter:

EASTL - Electronic Arts Standard Vorlagenbibliothek

77
Grumbel

Ich arbeite an einem MMAP-Allokator, mit dem Vektoren Speicher aus einer Memory-Mapped-Datei verwenden können. Das Ziel besteht darin, Vektoren zu haben, die Speicher verwenden, der sich direkt im virtuellen Speicher befindet, der durch mmap abgebildet wird. Unser Problem besteht darin, das Lesen von wirklich großen Dateien (> 10 GB) in den Speicher ohne zusätzlichen Kopieraufwand zu verbessern. Daher benötige ich diesen benutzerdefinierten Zuweiser.

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

#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() { }
        };
}

Deklarieren Sie dazu einen AWL-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. Was erforderlich ist, ist die Rebind-Struktur, ansonsten verwendet der Vektorcontainer die Zuordnungs-/Freigabemethoden für Superklassen.

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

60
Johannes Thoma

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

24

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

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

18
Martin Cote

Ich habe keinen C++ - Code mit einem benutzerdefinierten STL-Zuweiser geschrieben, aber ich kann mir einen in C++ geschriebenen Webserver vorstellen, der einen benutzerdefinierten Zuweiser zum automatischen Löschen von temporären Daten verwendet, die zum Beantworten 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.

6
pts

Bei der Arbeit mit GPUs oder anderen Coprozessoren ist es manchmal vorteilhaft, Datenstrukturen im Hauptspeicher auf spezielle Weise zuzuweisen. Diese spezielle Weise der Speicherzuweisung kann auf bequeme Weise in einem benutzerdefinierten Allokator implementiert werden.

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

  1. durch benutzerdefinierte Zuweisung wird die Laufzeit des Beschleunigers oder der Treiber über den Speicherblock benachrichtigt
  2. darüber hinaus kann das Betriebssystem sicherstellen, dass der zugewiesene Speicherblock seitengesperrt ist (manche nennen dies festgehaltener Speicher), dh, das Subsystem für den virtuellen Speicher des Betriebssystems kann den nicht verschieben oder entfernen Seite innerhalb oder aus dem Speicher
  3. wenn 1. und 2. gedrückt halten und eine Datenübertragung zwischen einem seitengesperrten Speicherblock und einem Beschleuniger angefordert wird, kann die Laufzeitumgebung 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 verschiebe/entferne es
  4. dies spart eine Speicherkopie, die bei nicht seitengesperrtem Speicher auftreten würde: Die Daten müssen im Hauptspeicher in einen seitengesperrten Staging-Bereich kopiert werden, mit dem der Beschleuniger die Datenübertragung initialisieren kann (über DMA) )
6
Sebastian

Ich verwende hier benutzerdefinierte Zuweiser. Man könnte sogar sagen, es sollte funktionieren m 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 automatisches Sammeln kleiner Objekte, Lecksuche, Zuweisen von Füllen, freies Füllen, Auffüllen von Wachposten, Cache-Zeilen-Ausrichtung für bestimmte Zuweisungen und verzögertes freies Füllen ausführen.

Das Problem ist, dass wir in einer eingebetteten Umgebung arbeiten - es ist nicht genügend Speicher verfügbar, um die Leckerkennungsberechnung über einen längeren Zeitraum ordnungsgemäß durchzuführen. Zumindest nicht im Standard RAM - es gibt einen weiteren Haufen von RAM durch benutzerdefinierte Zuweisungsfunktionen an anderer Stelle.

Lösung: Schreiben Sie einen benutzerdefinierten Allokator, der den erweiterten Heap verwendet, und verwenden Sie ihn nur in den Interna der Speicherleckverfolgungsarchitektur ... Alles andere erfolgt standardmäßig mit den normalen neuen/Löschüberladungen, die die Leckverfolgung durchführen. Dies vermeidet das Tracking des Trackers selbst (und bietet ein bisschen zusätzliche Packungsfunktionalität, da wir die Größe der Trackerknoten kennen).

Aus dem gleichen Grund verwenden wir diese Funktion auch, um Daten zur Funktionskostenprofilerstellung zu speichern. Das Schreiben eines Eintrags für jeden Funktionsaufruf und jede Rückkehr sowie Thread-Schalter können schnell teuer werden. Der benutzerdefinierte Allokator gibt uns wieder kleinere Allokationen in einem größeren Debug-Speicherbereich.

5
leander

Ich verwende einen benutzerdefinierten Zuweiser, um die Anzahl der Zuweisungen/Freigabezuweisungen 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.

4
Jørgen Fogh

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

Wo ich darauf stieß, war eine Plugin-Architektur unter Windows. Wenn Sie beispielsweise einen std :: string über die DLL - Grenze übergeben, müssen alle Neuzuordnungen des Strings auf dem Heap erfolgen, von dem er stammt, NICHT auf dem Heap im DLL die unterschiedlich sein kann *.

* Es ist komplizierter als dies tatsächlich, als ob Sie dynamisch mit dem CRT verknüpfen, könnte dies trotzdem funktionieren. Aber wenn jede DLL eine statische Verknüpfung zu dem CRT hat, zu dem Sie unterwegs sind eine Welt des Schmerzes, in der ständig Phantomzuweisungsfehler auftreten.

4
Stephen

Ein Beispiel für die Zeit, in der ich diese verwendet habe, war die Arbeit mit sehr ressourcenbeschränkten eingebetteten Systemen. 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 Sie müssen außerdem einen sehr präzisen Zugriff darauf haben, wo diese Dinge gespeichert werden. In diesem Fall 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 mit einem bekannten Maximum speichern. Die Standard-Bibliotheksimplementierung der Speicherverwaltung ist ein dünner Wrapper um malloc/free, der festhält, wo Elemente platziert werden sollen, indem jedem zugewiesenen Speicherblock ein Zeiger vorangestellt wird, der auf das Ende des zugewiesenen Blocks verweist Stück Erinnerung. Beim Zuweisen eines neuen Speicherbereichs muss der Standardzuweiser über jeden Speicherbereich gehen, 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 benötigen würden. Dadurch wurden im Voraus Speicherblöcke mit fester Größe 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 auf die Speichernutzung verzichtet, um den gesamten Prozess zu beschleunigen, was in unserem Fall gerechtfertigt war, als wir diesen Mikrocontroller-Chip in die Nähe seiner maximalen Verarbeitungskapazität gebracht haben.

Es gibt eine Reihe anderer Fälle, in denen ich sehe, wie ich im Kontext eingebetteter Systeme Ihren eigenen benutzerdefinierten Allokator schreibe, zum Beispiel, wenn der Speicher für die Sequenz nicht im Hauptspeicher ist, wie dies häufig auf diesen Plattformen der Fall ist =.

3
shuttle87

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

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

Das Schöne daran ist, dass man sich schon beim Erdenken Gedanken darüber macht, wie man sie verwenden würde :-)

3
einpoklum

Für den gemeinsamen Speicher ist es wichtig, dass nicht nur der Kopf des Containers, sondern auch die darin enthaltenen Daten im gemeinsamen Speicher gespeichert werden.

Der Allokator von Boost :: Interprocess ist ein gutes Beispiel. Wie Sie jedoch lesen können, reicht hier nicht aus, um alle STL-Container mit dem gemeinsam genutzten Speicher kompatibel zu machen (aufgrund unterschiedlicher Mapping-Offsets in verschiedenen Prozessen können Zeiger "brechen").

2
ted

Vor einiger Zeit fand ich diese Lösung sehr nützlich für mich: Fast C++ 11 Allokator für AWL-Container . Es beschleunigt leicht STL-Container auf VS2017 (~ 5x) sowie auf GCC (~ 7x). 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.

2
no one special

In einer Grafiksimulation wurden benutzerdefinierte Allokatoren für verwendet

  1. Ausrichtungseinschränkungen, die std::allocator hat nicht direkt unterstützt.
  2. Minimierung der Fragmentierung durch Verwendung separater Pools für kurzlebige (nur dieser Frame) und langlebige Zuweisungen.
1
Adrian McCarthy

Ich persönlich nutze 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 Standard-Neu/Löschen-Zuweisung in C++, wenn es darum geht, moderate Mengen kleiner Objekte in vielen verschiedenen Größen zuzuweisen. Es gibt auch eine VC-spezifische Lösung namens "QuickHeap", die die bestmögliche Leistung bietet (Zuweisungs- und Freigabevorgänge lesen und schreiben Sie einfach die Adresse des Blocks, der dem Heap zugewiesen/zurückgegeben wird, in bis zu 99 Fällen. (9)% der Fälle - hängt von den Einstellungen und der Initialisierung ab), ist jedoch mit einem erheblichen Mehraufwand verbunden - es werden zwei Zeiger pro Bereich und ein zusätzlicher Zeiger für jeden neuen Speicherblock benötigt. Dies ist eine schnellstmögliche Lösung für die Arbeit mit einer großen Anzahl von Objekten (10 000 ++), die erstellt und gelöscht werden, wenn Sie keine große Anzahl von Objektgrößen benötigen (es wird ein individueller Pool für jede Objektgröße von 1 bis 1023 Byte erstellt) In der aktuellen Implementierung verringern Initialisierungskosten möglicherweise die allgemeine Leistungssteigerung. Sie können jedoch einige Dummy-Objekte zuweisen/freigeben, bevor die Anwendung in ihre leistungskritische (n) Phase (n) eintritt.

Das Problem bei der standardmäßigen Implementierung von C++ für Neu/Löschen ist, dass es sich normalerweise nur um einen Wrapper für die Zuweisung von C malloc/free handelt und für größere Speicherblöcke wie mehr als 1024 Byte geeignet ist. Es hat einen beachtlichen Overhead in Bezug auf die Leistung und manchmal auch zusätzlichen Speicher, der 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 Speicher für die Zuweisung kleiner Objekte (≤ 1024 Byte) minimiert wird.