Memory Pool Allokatoren von Jonathan Müller

Nachdem ich einige Artikel rund um das Speichermanagement in C++ geschrieben habe, bin ich sehr froh, Jonathan Müller für einen Gastartikel zu seiner Implementierung der memory Bibliothek in diesem Blog gewinnen zu können. Er wird die Konzepte rund um sein Design erklären. Jonathan ist als Experte zum Speichermangement in der C++-Community weltweit bekannt, sodass er in der 59 Episode Gast des cppcast war und seine Bibiothek den Zuhörern vorstellen konnte.

Die Motivation

Zuerst einmal stellt sich mir die Frage, warum Jonathan eine Bibliothek zum Speichermanagement in C++ geschrieben hat? Diese Frage beantwortet er direkt auf seinem github Projekt memory:

"The C++ STL allocator model has various flaws. For example, they are fixed to a certain type, because they are almost necessarily required to be templates. So you can't easily share a single allocator for multiple types. In addition, you can only get a copy from the containers and not the original allocator object. At least with C++11 they are allowed to be stateful and so can be made object not instance based. But still, the model has many flaws. Over the course of the years many solutions have been proposed. for example EASTL. This library is another. But instead of trying to change the STL, it works with the current implementation."

Das ist aber nur ein Teil der Antwort. Noch vielversprechender finde ich seine bewusst provokanten These zur Performance seiner Bibliothek, die er in vier sehr lesenswerten Artikeln begründet: How I have beaten Boost.Pool. Insbesondere seine Erläuterungen zu den verschiedenen Optimierungsstrategien der Speicherallokation liefern sehr viel Hintergrundwissen und besitzen einen deutlich allgemeineren Fokus.

Nun aber endlich zu Jonathan's Artikel.

Memory Pool Allokator

Ein Memory Pool Allokator ist ein universal einsetzbarer und schneller Pool Allokator -> und schneller Allokator. Er fordert nur große Speicherblöcke an und unterteilt sie in gleich große Stücke. Alle freien Stücke werden in einer sogenannten free list  gespeichert. Allokation entfernt einfach das erste Stück aus der free list und gibt es zurück,  Freigabe fügt es wieder ein.  Das ist recht schnell, kann jedoch nur Stücke einer festen Größe verwenden, ansonsten hat man wieder Fragmentierungsprobleme und mitunter langsame Suchen nach dem am besten passenden Stück.

Ich werde nun zeigen wie man die Pool Implementierung meiner memory Bibliothek  für eigene Allokationen nutzt.

memory ist eine Bibliothek, die verschiedene Allokatoren implementiert und die benötigte Infrastruktur um sie problemlos nutzen zu können zur Verfügung stellt. Sie ist aktuell noch in Version 0.x und somit noch in der Entwicklung.

Der memory pool

Hat man meine Bibliothek installiert kann man einen Memory Pool ganz einfach nutzen.

#include <foonathan/memory/memory_pool.hpp>
#include <foonathan/memory/namespace_alias.hpp> // (1)

int main()
{
    memory::memory_pool<> pool(16, 4096); // (2)
    void* node = pool.allocate_node(); // (3)
    // ...
    pool.deallocate_node(node); // (4)
} 

Nachdem man die benötigten Header-Dateien in (1) inkludiert hat (namespace_alias.hpp stellt automatisch ein Alias für den sonst recht langen Namespace-Namen foonathan::memory zur Verfügung), kann man in (2) direkt den Memory Pool erstellen. Der Konstruktor hat zwei Parameter: der erste ist die Größe jedes Blocks in der free list, die sogenannte node size. Der zweite Parameter ist die Größe des großen Speicherblocks, der unterteilt wird, hier sind das 4KiB.

Von dem Pool kann man nun kleine Speicherblöcke, sogenannte nodes anfordern (3) und wieder freigeben (4). Jeder node ist dabei so groß wie im Konstruktor angegeben - hier also 16 Bytes.
Selbstverständlich wird mit der Freigabe des großen Speicherblocks im Destruktor des Pools automatisch auch alle nodes freigegeben - auch wenn kein Aufruf von deallocate_node() erfolgt ist.

Nun ist es jedoch recht mühsam den Pool so manuell zu verwenden. Da hilft jedoch das Konzept des RawAllocator, die grundlegende Abstraktion der Bibliothek.

Der RawAllocator

In einem vorherigen Teil wurde das Allocator Konzept vorgestellt, mit dem man die Speicheranforderung der STL Container anpassen kann. Nun ist das Allocator Konzept nicht gerade einfach und außerdem koppelt er die Erstellung der Objekte mit der Anforderung für den Speicher. Die meiste Zeit braucht man das nicht, man will einfach nur anpassen, wie der Speicher verwaltet wird. Für diese Fälle ist der RawAllocator gedacht.

Ein RawAllocator hat folgendes Interface:

struct raw_allocator
{
    using is_stateful = std::integral_constant<bool, Value>; // optional, default ist std::is_empty

    void* allocate_node(std::size_t size, std::size_t alignment); // verlangt, alloziert Speicher
    void deallocate_node(void *node, std::size_t size, std::size_t alignment) noexcept; // verlangt, gibt Speicher frei

    void* allocate_array(std::size_t count, std::size_t size, std::size_t alignment); // optional, default ruft allocate_node() auf
    void deallocate_array(void *ptr, std::size_t count, std::size_t size, std::size_t alignment) noexcept; // optional, default ruft deallocate_node() auf

    std::size_t max_node_size() const; // optional, default gibt maximalen Wert zurück
    std::size_t max_array_size() const; // optional, default gibt max_node_size() zurück
    std::size_t max_alignment() const; // optional, default gibt maximales Alginment zurück, d.h. alignof(std::max_align_t)
}

Dieses Interface ähnelt sehr dem der neuen std::pmr::memory_resource, nur, dass es nicht über Vererbung implementiert wird. Der RawAllocator ist somit Bestandteil des Typs bei default und kann nur optional type erased werden - über die Verwendung der any_allocator_reference Klasse.

Das meiste des Interfaces ist optional und muss nur in besonderen Fällen selber implementiert werden.  Der memory_pool ist nun ebenfalls ein RawAllocator, obwohl er das Interface nicht implementiert. Das ist möglich, da jeglicher Zugriff über die memory::allocator_traits passiert, die der memory_pool spezialisiert hat.

Um nun RawAllocator in STL Container zu nutzen gibt es den Adapter std_allocator, der ein RawAllocator nimmt und ihm die Schnittstelle eines Allocator gibt. Da Allocator kopierbar sein müssen, RawAllocator jedoch nicht, nimmt er den RawAllocator nur per Referenz.

Da Memory Pools Probleme mit Array Anforderung haben, was allerdings z.B. std::vector macht, sind sie ideal für die node based containers, hier ein Beispiel:

#include <set>

#include <foonathan/memory/container.hpp>
#include <foonathan/memory/memory_pool.hpp>
#include <foonathan/memory/namespace_alias.hpp>

int main()
{
    memory::memory_pool<> pool(memory::set_node_size<int>::value, 4096); // (1)
    memory::set<int, decltype(pool)> set(pool); // (2)
    set.insert(3);
    // ...
} 

Wir erstellen wie gehabt unseren Pool in (1). Die übergebene node size ist genau der Wert, der für ein std::set<int> benötigt wird.  Diesen verwenden wir nun für ein set in (2).  Der Typ des Container ist jedoch memory::set. Das ist nicht etwa eine Neu-Implementierung von std::set, sondern einfach ein template alias, in diesem Fall für std::set<int, std::less<int>, memory::std_allocator<int, decltype(pool)>> - also ein std::set<int>, was den Pool durch den std_allocator verwendet. Der aufgerufene Konstruktor ist auch der reguläre Allokator Konstruktor von std::set. Wir nutzen aus, dass der memory::std_allocator implizit von dem RawAllocator erstellt werden kann.

Nun können wir das set ganz normal verwenden, alle Allokation geht dabei über unseren Pool.

Anpassung der Pool internen Allokationen

Wie anfangs angesprochen, fordert der Pool einen großen Speicherblock an und unterteilt ihn in kleinere Stücke. Standardmäßig nutzt er dazu memory::heap_allocator, das ist ein RawAllocator, der an OS spezifische Funktionen weiterleitet, z.B. HeapAlloc() unter Windows.
Jedoch kann man diesen internen Allokator über ein Template Argument anpassen.

Eine Kombination von Allokatoren ist besonders nützlich. Sagen wir, wir wollen einen std::vector haben, der nicht auf dem Heap, sondern auf dem Stack liegt.
Einfach: Wir nehmen std::array oder ein C-Array.

Wie sieht es aber aus, wenn wir ein std::set auf dem Stack haben wollen?

#include <set>

#include <foonathan/memory/container.hpp>
#include <foonathan/memory/memory_pool.hpp>
#include <foonathan/memory/namespace_alias.hpp>
#include <foonathan/memory/static_allocator.hpp>

int main()
{
    memory::static_allocator_storage<4096u> storage; // (1)

    using static_pool = memory::memory_pool<memory::node_pool, memory::static_allocator>; // (2)
    static_pool pool(memory::set_node_size<int>::value, 4096, storage); // (3)

    memory::set<int, decltype(pool)> set(pool);
    set.insert(3);
    // ...
} 

Wir kombinieren unseren memory_pool mit dem static_allocator für die interne Speicheranforderung. Wie heap_allocator kann man auch den RawAllocator static_allocator selber verwenden, nützlicher ist er allerdings im Zusammenhang mit memory_pool.
Die Allokatoren von memory können sehr gut miteinander kombiniert werden um verschiedene Strategien zu bewerkstelligen.

Zunächst erstellen wir in (1) unseren Speicher, den der static_allocator für die Speicheranforderung nutzt. Ein Alias in (2) definiert unseren neuen Pool Typen. memory::memory_pool hat zwei Template Parameter. Der erste ist der Typ des Pools und man kann ihn so für verschiedene Anforderungen einstellen. Der Standardwert ist memory::node_pool und das sollte man meistens auch nehmen. Der zweite Parameter ist der Typ des internen Allokators.  Hier nehmen wir unseren memory::static_allocator.  In (3) konstruieren wir dann den Pool, diesmal müssen wir ihm allerdings auch den storage übergeben, den der memory::static_allocator verlangt.

Dann können wir nach wie vor unser set erstellen und haben ein set dessen Speicher komplett auf dem Stack liegt.

Der interne Allokator ist eigentlich ein BlockAllocator, kein RawAllocator,  da man damit auch kontrollieren kann wie groß die nächsten Blöcke werden,  wenn der erste Block keinen Speicher mehr hat. Template-Magie sorgt aber dafür, dass man auch einfach RawAllocator übergeben kann,  die dann automatisch zu einem BlockAllocator werden.

Mehrere Pools

Der memory_pool kann nur Speicher für eine bestimmte Größe verwalten.
Braucht man mehrere Größen muss man entweder die node size auf die maximale Größe setzen und bei den kleineren Größen Platz verschwenden oder man nimmt mehrere Pools und wählt den passendsten aus.

Diese zweite Alternative ist automatisiert in der memory::memory_pool_collection.  Diese Klasse verwaltet mehrere Pools und wählt den richtigen Pool aus. Es ist wieder ein Template mit drei Parametern. Der erste ist der Typ des Pools, er sollte meistens memory::node_pool sein. Der zweite ist die Verteilungsstrategie. Sie kann entweder memory::identity_buckets - ein Pool für jede Größe - oder memory::log2_buckets - ein Pool für jede Zweierpotenz sein. Der dritte ist wie beim regulären Pool, der Allokator, der für den internen Speicher genutzt wird.
Zu beachten ist, dass sich alle Pools den noch ungenutzten Speicher teilen und erst bei Bedarf nimmt sich jeder Pool einen gleichmäßigen Anteil.

Die Verwendung ist sehr ähnlich wie beim regulären memory_pool, weshalb ich mir ein Beispiel schenke.
Zu beachten ist, dass die node size im Konstruktor nun die maximale Größe hat und die allocate_node() Funktionen eine Größe verlangen.
Dank der RawAllocator Abstraktion ist die Verwendung im Zusammenhang mit STL Containern etc. identisch.

Fazit

Es gibt viele Bibliotheken, die Pools implementieren. memory ist jedoch die einzige, die ein Rundum-Paket an Allokatoren bietet. Ich habe längst nicht alles an Funktionalität gezeigt. Es gibt noch viele weitere Allokatoren und Adapter, z.B. Deleter Klassen für std::unique_ptr, und die ganze allocator_storage Funktionalität, die beispielsweise allocator_reference implementiert, habe ich überhaupt nicht angesprochen.
Die Bibliothek ist so entworfen, dass man einfach nur den Allokator, den man braucht dort hineinstecken kann, wo man ihn braucht, bietet allerdings auch die Möglichkeit ganz nah ran zu gehen und jedes Detail einzustellen.

Wer mehr über das Design von memory wissen will, dem empfehle ich meinen Meeting C++ Talk im November.
Ansonsten folgt mir doch auf Twitter oder schaut auch mal auf meinem Blog vorbei.

Wie geht's weiter?

Mit diese Artikel enden meine Artikel zur embedded Programmierung im allgemeinen und zur Speichermanagement im besonderen. Weiter geht es im nächsten Artikel mit der funktionalen Programmierung in C++.

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.