Softwareentwicklung: Polymorphe Allokatoren in C++17​

Dieser Artikel ist der Auftakt zu einer Miniserie über ein fast unbekanntes Feature in C++17: polymorphe Allokatoren. Ich habe oft versprochen, dass ich über polymorphe Allokatoren schreiben werde. Heute löse ich mein Versprechen ein.

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

Seit C++98 lässt sich Speicherzuweisung im allgemein, aber auch für benutzerdefinierte Typen oder Container der Standardbibliothek exakt an die Anforderungen anpassen. Zum Beispiel haben die Container der sequenziellen und assoziativen Container der STL einen Default-Allokationsparameter. Exemplarisch zeigen die folgenden Zeilen die Deklaration der Container std::string, std::vector und std::unordered_map:

template<class CharT, class Traits = std::char_traits<CharT>,
         class Allocator = std::allocator<CharT>> 
class basic_string;
using string = basic_string<char>;

template<class T, class Allocator = std::allocator<T>> 
class vector;

template<class Key, class T, class Hash = std::hash<Key>,
         class KeyEqual = std::equal_to<Key>,
         class Allocator = std::allocator<std::pair<const Key, T>>>
class unordered_map;

Der Speicher wird per Default aus dem Heap zugewiesen, aber dieser Default ist nicht immer sinnvoll. Oft soll eine andere Strategie zum Einsatz kommen. Hier sind ein paar Ideen:

• Die Speicherzuweisung soll auf dem Stack statt dem Heap erfolgen.
• Die Anzahl der Speicherzuweisungen soll reduziert werden.
• Zusammenhängende Speicherblöcke sollen verwendet werden, um vom CPU-Caching zu profitieren.
• Der Speicher soll zugewiesen, aber nicht freigeben werden.
• Ein Speicherpool soll zum Einsatz kommen.
• Die Speicherzuweisung soll thread-safe erfolgen.
• Verschiedene Allokatoren sollen für unterschiedliche Datentypen zum Einsatz kommen.
• Die Speicherzuweisungsstrategie soll sich für einen Datentyp ändern, wenn seine Größe zunimmt.

Mit C++98 konnte man bereits einen eigenen Speicherallokator implementieren und verwenden, aber das war ziemlich schwierig und fehleranfällig. Ich habe bereits zwei Artikel über Speicherallokatoren in C++ geschrieben: "Speicher anfordern mit std::allocator" und einen Gastbeitrag von Jonathan Müller: "Memory Pool Allokatoren".

Dank der polymorphen Allokatoren in C++17 wird deine Arbeit viel einfacher. Bevor ich auf die Details eingehe, möchte ich ein einführendes Beispiel vorstellen.

// polymorphicAllocator.cpp

#include <array>
#include <cstddef>
#include <memory_resource>
#include <vector>

int main() {

    std::array<std::byte, 200> buf1;                   // (1)
    std::pmr::monotonic_buffer_resource pool1{buf1.data(), 
                                              buf1.size()};
    std::pmr::vector<int> myVec1{&pool1};              // (3)
    for (int i = 0; i < 5; ++i) {
        myVec1.push_back(i);
    }

    char buf2[200] = {};                               // (2)
    std::pmr::monotonic_buffer_resource pool2{std::data(buf2),
                                              std::size(buf2)};
    std::pmr::vector<int> myVec2{&pool2};
    for (int i = 0; i < 200; ++i) {
        myVec2.push_back(i);
    }

}

Zuerst fordere ich Speicher auf dem Stack an. Für diese Aufgabe kann ich ein byte-Array (Zeile 1) oder ein char-Array (Zeile 2) verwenden. Außerdem initialisiere ich einen std:pmr::monotonic_buffer mit der Adresse und der Größe des bereits auf dem Stack angeforderten Speichers. Der letzte Schritt ist, dass der std::pmr::vector diese Speicherressource verwendet.

Die Namensraum-Komponente pmr steht für polymorphic memory resource. Alle Komponenten der polymorphen Allokatoren befinden sich in diesem Namensraum. Die Container der STL haben ihre pmr-Pendants. Das verwendete pmr-Pendant ist nur ein Alias für einen std::vector, der den speziellen Allokator verwendet. Die folgenden zwei Zeilen sind gleichwertig:

std::pmr::vector<int> myVec1{&pool1}; 

std::vector<int, std::pmr::polymorphic_allocator<int>> 
  myVec1{&pool1};

Bei dem Beispiel polymorphicAllocator.cpp mag die Frage aufkommen, wie ein Vektor mit 200 int's myVec2 in ein char-Array mit 200 Elementen passen kann. Die Antwort ist einfach: std::pmr::new_delete_resource als sogenannter upstream Allokator kommt als Fallback zum Einsatz. C++17 bietet ein paar vordefinierte Speicherressourcen.

Vordefinierte Speicherressourcen

Ich werde die aufgelisteten vordefinierten Speicherressourcen in den nächsten Artikeln anwenden. Deshalb ist hier ein kurzer Überblick. Alle vordefinierten Speicherressourcen sind von der Schnittstellenklasse std::pmr::memory_resource abgeleitet. Die Klasse bietet die drei öffentliche Funktionen allocate, deallocate und is_equal an.

std:pmr::memory_resource bietet entsprechend drei private virtuelle Mitgliedsfunktionen do_allocate, do_deallocate und do_is_equal an. Typischerweise überschreibt eine benutzerdefinierte Speicherressource diese drei virtuellen Mitgliedsfunktionen. Genauso verhalten sich die folgenden vordefinierten Speicherressourcen:

std::pmr::new_delete_resource

gibt einen Zeiger auf eine Speicherressource zurück, die die globalen Funktionen new und delete aufruft. Sie ist die Standard-Speicherressource, wenn nicht anders angegeben.

std::pmr::null_memory_resource

gibt einen Zeiger auf eine Null-Speicherressource zurück. Die Verwendung dieser Speicherressource für die Allokation führt zu einer std::bad_alloc-Ausnahme. Diese Speicherressource stellt sicher, dass man nicht willkürlich Speicher auf dem Heap alloziert.

std::pmr::synchronized_pool_resource

Eine Klasse, die eine Speicherressource mit geringerer Fragmentierung erstellt, die Thread-sicher ist. Diese Klasse dient als Wrapper für die Standardressource.

std::pmr::unsynchronized_pool_resource

Eine Klasse, die eine Speicherressource mit geringerer Fragmentierung erstellt, die nicht Thread-sicher ist. Diese Klasse dient als Wrapper für die Standardressource.

std::pmr::monotonic_buffer_resource

Eine Klasse zum Erstellen von Speicherressourcen in einem zusammenhängenden, nicht Thread-sicheren Speicherbereich, der man optional einen Puffer übergeben kann. Diese Speicherressource ist äußerst schnell und kann nur wachsen. Sie destruiert die Objekte, gibt den Speicher aber nicht frei.

Ich habe im vorherigen Programm polymorphicAllocator.cpp einen std::pmr::monotonic_buffer mit einem byte-Array (1) und einem char-Array (2) als Puffer verwendet. Außerdem hat der Vektor myVec2 den zusätzlichen Speicher mit dem Standard-Allokator (Upstream-Allokator) std::pmr::new_delete_resource allokiert.

Wie geht's weiter?

Zugegeben, dies war ein technischer Artikel. In meinem nächsten Artikel werde ich die Theorie anwenden und eine Speicherressource implementieren, die ihre Allokationen und Deallokationen darstellt. (rme)