Der Code, auf dem dieser Artikel basiert, befindet sich in der Entwicklung, wobei verschiedene Commits unter dem Thema Allocator anstehen. Beachten Sie, dass der Code verschiedene C++17-Features verwendet.
Vor einigen Monaten arbeiteten die Entwickler der Qt Company daran, zu korrigieren, wie QHostInfo Ergebnisse an den Aufrufer sendet, was zu einer leichten Optimierung der Speicherzuweisung für Argumente in QMetaCallEvent führte. Entwickler verwenden Objekte dieses Typs in Signal-/Slot-Verbindungen zu Warteschlangen, und einige Zeit in diesem Code zu verbringen, erinnerte mich daran, dass Qt ein Muster hat, eher kleine, kurzlebige Objekte auf dem Heap zuzuweisen, sowie die Leistung des kritischen Pfads des Codes.
Daher begannen sie sich zu fragen, ob es möglich sei, QEvent-Instanzen aus einem zugewiesenen Speicherpool mit einem speziellen Allokator zuzuweisen.
Einige Statistiken
Die Neuimplementierung von QEvent::operator new(size_t) und die Verwendung von QHash als Histogramm-Datenstruktur zeigt, dass die meisten QEvent-Instanzen in einer kleinen Qt-Anwendung nur 24 Bytes groß sind:
using HistogramHash = QHash<size_t, int>;
Q_GLOBAL_STATIC(HistogramHash, histogram);
void *QEvent::operator new(std::size_t size) noexcept
{
++(*histogram())[size];
qDebug() << "QEvent:" << *histogram();
return ::operator new(size);
}
Indem wir dasselbe für QObject tun, erhalten wir eine breitere Streuung, aber auch hier sind die meisten Instanzen klein. 16 Byte ist die gebräuchlichste Größe.
Dies ist nicht überraschend. Die QObject-Instanz hat eine Tabelle mit virtuellen Funktionen und einen d-Zeiger auf QObjectPrivate, wo sich alle realen Daten befinden. Unterklassen von QObject verwenden Unterklassen von QObjectPrivate für ihre privaten Daten und übergeben diese privaten Instanzen zur Speicherung an QObject.
Daher sind QEvent- und QObject-Instanzen ziemlich klein, und selbst die Anwendung weist eine ganze Reihe von ihnen zu. Wie schwierig wäre es, einen für diese Anwendungsfälle optimierten Speicherzuordner zu implementieren?
Allocator für allgemeine Zwecke im Vergleich zu spezialisierten
Standardmäßig weist der globale C++-Operator new Speicher mit malloc() zu. malloc() ist ein Allzweck-Allocator, der für alle Größen gut funktionieren sollte, von einigen Bytes bis zu einigen Gigabytes, sodass für jede Zuweisung ein wenig Buchhaltungsaufwand anfällt. Es gibt verschiedene Implementierungen von malloc(), und einige von ihnen sind wirklich erstaunlich darin, die Zuordnung kleiner Objekte und andere gängige Anwendungsfälle zu optimieren. Sie sind jedoch immer noch Allzweckzuordner, sodass sie zur Laufzeit Entscheidungen treffen müssen, die ein spezialisierter Zuordner möglicherweise nicht treffen muss.
Spezialisierte Allokatoren werden typischerweise in Situationen verwendet, in denen Datenstrukturen sehr dynamisch zugewiesen werden müssen und Datenerzeugung und -vernichtung eine hohe Leistung aufweisen müssen. Ein Anwendungsgebiet, in dem oft kleine, kurzlebige Objekte entstehen und zerstört werden, sind Spiele: Geschosse in einem Ego-Shooter sind ein Beispiel. Andere Domänen sind Szenendiagramme in Rendering-Engines, Parser, die ASTs erstellen, Hash-Tabellen. In all diesen Fällen ist oft im Voraus bekannt, welche Art von Speicherallokation benötigt wird, und die Entwickler würden gerne mehrere CPU-Zyklen reduzieren.
Ein weiterer Grund, warum ein benutzerdefinierter Allokator wertvoll sein kann, ist, dass einige Plattformen nicht mit einem Speicherverwaltungsblock ausgeliefert werden. Wie kürzlich angekündigt, läuft Qt jetzt auf Mikrocontrollern und diese Geräte haben oft keine MMU. In solchen Umgebungen kann die Speicherfragmentierung durch häufige kleine Allokationen schnell zu einem ernsthaften Problem werden.
Durch die Vorabzuweisung von Speicher und die Verwaltung dieses Pools in einer für entsprechende Nutzungsmuster optimierten Weise kann ein spezialisierter Allokator viele Overhead- und Kernel-Roundtrips schützen. Speicherfragmentierungsprobleme sind zumindest auf diesen Speicherpool beschränkt und wirken sich weniger wahrscheinlich auf das gesamte System aus.
Grundlegende Datenstrukturen
Der Pool-Zuordner von Qt sollte eine schnelle Zuweisung und Freigabe für verschiedene Objekte ermöglichen, aber normalerweise kleine Größen, die zur Kompilierzeit bekannt sind. Der Zuordner muss auf einem Speicherpool arbeiten, der groß genug ist, um nur sehr selten Kernel-Zugriffe zu erfordern. Zuweisungen und Freigaben sollten in zufälliger Reihenfolge möglich sein.
Eine schnelle Datenstruktur zum Verwalten freier Speicherblöcke ohne zusätzliche Kosten ist ein In-Place-Stack: Eine vorab zugewiesene Speicherseite wird in Blöcke gleicher Größe unterteilt, die jeweils an einem Knoten liegen, der auf den vorherigen Block zeigt. Für ausgewählte Knoten müssen Sie den vorherigen Knoten nicht kennen, sodass Sie Union und den gesamten Block für Benutzerdaten verwenden können. Eine Zuordnung entfernt einen Knoten vom Stapel, eine Freigabe verschiebt den Knoten zurück auf den Stapel.
template<size_t ChunkSize>
class PoolAllocator
{
struct Page
{
char memory[4096];
};
union Node
{
Node *previous;
char chunk[ChunkSize];
};
public:
PoolAllocator()
{
initPage(&m_page);
}
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
if (!stack)
return nullptr;
Node *top = stack;
stack = stack->previous;
return top->chunk;
}
void free(void *ptr)
{
Node *top = static_cast<Node*>(ptr);
top->previous = stack;
stack = top;
}
private:
void initPage(Page *page)
{
Node *newStack = reinterpret_cast<Node*>(page->memory);
newStack->previous = stack;
const size_t numChunks = sizeof(Page) / sizeof(Node);
for (size_t i = 0; i < numChunks - 1; ++i, ++newStack)
newStack[1].previous = newStack;
stack = newStack;
}
Node *stack = nullptr;
Page m_page;
};
Dies ergibt eine O(1)-Komplexität zum Zuweisen und Freigeben und eine fast 100-prozentige Speichereffizienz. Alles, was der Allokator speichern muss, ist ein Zeiger auf die Spitze des Stacks (für eine 4K-Speicherseite bedeutet dies 8 Byte Overhead auf einem 64-Bit-System. Das ist sehr gut!) Aber im Moment kann der Qt-Allokator nur funktionieren mit fester Speicherkapazität.
Anstatt auf eine Speicherseite beschränkt zu sein und nullptr zurückzugeben, wenn er aufgebraucht ist, könnte man eine andere Seite zuweisen und die Chunks auf den Stack schieben. Auf diese Weise kann der Speicherpool so weit wie nötig wachsen, ohne sich darum kümmern zu müssen, den Speicherpool zur Kompilierzeit groß genug zu machen. Es wird immer noch möglich sein, mehr als hundert 40-Bit-Objekte in eine einzige 4K-Speicherseite zu packen, und ein einziger Kernel-Zugriff wird ausreichen, wenn es wachsen muss. Es ist jedoch jetzt notwendig, einen Vektor von Zeigern in Speicherseiten aufrechtzuerhalten, damit Seiten freigegeben werden können, wenn der Zuordner zerstört wird.
template<size_t ChunkSize>
class PoolAllocator
{
struct Page
{
char memory[4096];
};
union Node
{
Node *previous;
char chunk[ChunkSize];
};
public:
PoolAllocator()
{
}
~PoolAllocator()
{
for (auto page : pages)
::free(page);
}
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
if (!stack && !grow())
return nullptr;
Node *top = stack;
stack = stack->previous;
return top->chunk;
}
void free(void *ptr)
{
Node *top = static_cast<Node*>(ptr);
top->previous = stack;
stack = top;
}
private:
bool grow()
{
Page *newPage = static_cast<Page*>(::malloc(sizeof(Page)));
if (!newPage)
return false;
initPage(newPage);
pages.append(newPage);
return true;
}
void initPage(Page *page)
{
Node *newStack = reinterpret_cast<Node*>(page->memory);
newStack->previous = stack;
const size_t numChunks = sizeof(Page) / sizeof(Node);
for (size_t i = 0; i < numChunks - 1; ++i, ++newStack)
newStack[1].previous = newStack;
stack = newStack;
}
Node *stack = nullptr;
QVector<Page*> pages;
};
Der Allocator kann nun Seite für Seite auf die erforderliche Größe wachsen.
Benchmarking
Es gibt einen grundlegenden Poolzuordner als Vorlagenklasse, die unter Verwendung der Datenblockgröße erstellt wird. Dadurch kann der Compiler sehr effizienten Code generieren. Wie schnell ist es wirklich? Ein trivialer Benchmark weist einfach Speicher in einer Schleife zu und gibt ihn frei. Wir müssen für kleine Objekte optimieren, also müssen wir die Geschwindigkeit für 16, 32 und 64 Byte Speicher vergleichen, 100, 200 und 400 Blöcke gleichzeitig zuweisen und diese Blöcke dann in zwei Zyklen freigeben, wobei wir zuerst die freigeben ungerade und dann die geraden Indizes. Um ziemlich stabile und vergleichbare Ergebnisse zu erhalten, führen wir 250.000 Iterationen durch.
void *pointers[allocations];
QBENCHMARK {
for (int i = 0; i < 250000; ++i) {
for (int j = 0; j < allocations; ++j)
pointers[j] = ::malloc(allocSize);
for (int j = 0; j < allocations; j += 2)
::free(pointers[j]);
for (int j = 1; j < allocations; j += 2)
::free(pointers[j]);
}
}
Die verglichenen Allokatoren sind die Standardimplementierungen von malloc auf Desktop-Plattformen – macOS 10.14 (Entwicklerplattform), Windows 10 mit VC++17 und das Linux-malloc-System (Ubuntu 18.04, das ptmalloc2 verwendet). Unter Linux wurden auch Googles tcmalloc, Microsofts mimalloc und jemalloc von FreeBSD und Firefox verglichen. Es ist trivial, diese Zuweisungen anstelle von malloc() von glibc unter Linux zu verwenden, wo sie einfach LD_PRELOAD sein können.
$ LD_PRELOAD=LD_PRELOAD=/usr/local/lib/libtcmalloc.so ./tst_bench_allocator
Diese Ergebnisse sind sehr vielversprechend:
Alle Allokatoren haben ein ausreichend stabiles Verhalten für diesen Test. Die Größe des zugewiesenen Blocks spielt kaum eine Rolle, und die Verdoppelung der Anzahl der Zuweisungen dauert doppelt so lange.
In Anbetracht der einfachen Implementierung ist es nicht verwunderlich, dass der spezialisierte Pool-Allokator von Qt selbst die schnellsten Allzweck-Allokatoren um das Dreifache über mimalloc und das 70-fache über System-malloc in macOS 10.14 übertrifft.
Multithreaded-Modelle
Ein Anwendungsfall, für den die Qt-Entwickler einen Zuordner entwerfen möchten, sind QEvent-Zuweisungen im Allgemeinen und QMetaCallEvent-Zuweisungen im Besonderen. QEvents können aus mehreren Threads erstellt werden, daher muss der Allocator Thread-sicher sein. Darüber hinaus wird QMetaCallEvent verwendet, um Signale/Slots zwischen Threads zu übergeben, und Ereignisse können normalerweise an Objekte in verschiedenen Threads gesendet werden. Daher ist der zuordnende Thread nicht notwendigerweise der Thread, der das Objekt freigibt, und der zuordnende Thread kann sogar beendet werden, bevor das Objekt verarbeitet und auf dem empfangenden Thread verworfen wurde.
Aber es wird sicherlich Fälle geben, in denen Client-Code sicherstellen kann, dass derselbe Thread, der Speicher zuweist, auch der Thread ist, der diesen Speicher freigibt, oder wenn alles im selben Thread passiert (z. B. Szenendiagrammarbeit). Im Idealfall ist es möglich, für jede dieser Situationen eine optimierte Implementierung vorzunehmen, ohne den gesamten Code zu duplizieren.
Schlösser
Die Optionen zum Erstellen eines Thread-Zuordners sind sicher, indem eine Sperre eingeführt oder eine Sperren-freie Stack-Implementierung mit atomaren Anweisungen verwendet wird. Eine atomare Implementierung macht die Stack-Implementierung selbst lock-frei, hilft uns aber nicht beim Wachsen, wenn uns der Stack ausgeht. Bei einem Mutex ist die Ansichtskonkurrenz jedoch sehr hoch, wenn mehrere Threads versuchen, Speicher zuzuweisen und freizugeben.
Es ist möglich, Sperrenkonflikte zu reduzieren, indem ein Datenstück aus dem freien Stack zugewiesen wird, aber das Stück an einen anderen "Backlog"-Stapel zurückgesendet wird. Dann können Sie einen weiteren Mutex verwenden, um das Backlog zu schützen, wenn freie Datenfragmente ausgehen, ist es möglich, Plätze im Backlog zu tauschen. Beide Mutexe müssen für diese Operation gehalten werden.
void *allocate()
{
auto stack_guard = lock_stack();
// try to adopt backlog
if (!stack) {
auto backlog_guard = lock_backlog();
stack = backlog;
backlog = nullptr;
}
if (!stack && !grow())
return nullptr;
Node *top = stack;
stack = stack->previous;
return top->chunk;
}
void free(void *ptr)
{
auto guard = lock_backlog();
Node *top = static_cast<Node*>(ptr);
top->previous = backlog;
backlog = top;
}
Das hilft ein wenig, aber wenn man diesen Test mit mehreren Threads durchführt, zeigt sich schnell, dass dies allein keine erfolgreiche Strategie sein kann.
Arenen
Eine komplexere Architektur wäre, wenn jeder Thread in seiner eigenen "Arena" laufen würde. Jeder Thread muss über einen eigenen Speicherpool verfügen, um zu funktionieren, daher entsteht ein gewisser Overhead. Sie können die thread_local-Variable für einen Thread-spezifischen Bereich verwenden. Die Lebensdauer von arena wird mit std::unique_ptr mit der Lebensdauer des Threads in Beziehung gesetzt.
private:
struct Arena
{
void push(void *ptr);
void *pop();
void grow();
void initPage();
QVector<page*> pages;
Node *stack = nullptr;
};
inline thread_local static std::unique_ptr<Arena> current_thread;
Arena *arena()
{
Arena *a = current_thread.get();
if (!a) {
a = new Arena;
current_thread.reset(a);
}
return a;
}
public:
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
Node *node = return arena()->pop();
return node ? node->chunk : nullptr;
}
void free(void *ptr)
{
Node *node = static_cast<Node*>(ptr);
arena()->push(node);
}
Und solange der Client-Code sicherstellen kann, dass der Speicher von demselben Thread freigegeben wird, der ihn zugewiesen hat, müssen keine Sperren verwendet werden, um Operationen auf dem Arena-Stack zu synchronisieren.
Wenn wir die beiden Ansätze kombinieren, erhalten wir einen Allokator, in dem jeder Thread ohne jegliche Blockierung Fragmente aus seiner eigenen Arena abruft. Threads, die Speicher aus der Arena eines anderen Threads freigeben, schieben Chunks auf den Backlog-Stack der ursprünglichen Arena, sodass sie nur mit anderen ähnlichen freigebenden Threads um die benötigte Sperre konkurrieren. Wenn der Stack erschöpft ist, ändert sich das Backlog, aber dann muss auch der Allocator-Thread um die Sperre konkurrieren. Wir müssen jedoch in der Lage sein, einen Teil des Speichers, den der Client-Code an free() übergibt, der richtigen Arena zuzuordnen, da es nicht mehr möglich ist, nur den thread_local-Zeiger von arena zu verwenden, da wir sonst mit einem befreienden Thread enden das wird den gesamten Speicher von den zuweisenden Threads nehmen. Einen Zeiger auf die Arena für jedes Speicherelement auf dem Stack zu haben, wäre eine Option, führt jedoch zu einem erheblichen Mehraufwand bei der Ressourcenzuweisung. 8 Byte für ein 40-Byte-Fragment schreiben zu müssen bedeutet, dass 20 % des Speichers verschwendet werden.
Stattdessen können Sie die Tatsache nutzen, dass mit mmap() zugewiesene Speicherseiten immer 4-KByte-ausgerichtet sind. In einer Seitenadresse, die mit mmap (oder VirtualAlloc unter Windows) zugewiesen wird, sind die unteren 12 Bits (4096 = 2^12) immer Null, d. h. 0x123456789abcd000. Die Datenblockadressen auf der Seite haben die gleichen oberen 52 Bits, sodass es möglich ist, eine einfache Bitmaske auf die Datenblockadresse anzuwenden und die Seitenadresse zu erhalten. Sie können dann dafür sorgen, dass die Speicherseite einen Zeiger auf die Arena enthält, zu der sie gehört, sodass Sie nur 8 Bytes für jede 4K-Seite opfern müssen.
pivate:
struct Page
{
char memory[4096 - sizeof(Arena*)];
Arena *arena;
static Page *fromNode(Node *node)
{
return reinterpret_cast<Page*>(uintptr_t(node) & ~(sizeof(Page) - 1));
}
};
struct Arena
{
bool grow()
{
void *ptr = ::mmap(NULL, sizeof(Page), PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
Q_ASSERT_X(!(uintptr_t(ptr) % sizeof(Page)),
"PoolAllocator", "Page Alignment Error!");
if (!ptr)
return false;
Page *newPage = static_cast<Page*>(ptr);
initPage(newPage);
newPage->arena = this;
pages.append(newPage);
return true;
}
};
public:
void *allocate(size_t size)
{
Q_ASSERT(size <= ChunkSize);
Node *node = arena()->pop();
return node ? node->chunk : nullptr;
}
void free(void *ptr)
{
Node *node = static_cast<Node*>(ptr);
Arena *arena = Page::fromNode(node)->arena;
arena->push(node);
}
Zu der Komplexität trägt die Möglichkeit bei, dass der Auswahl-Thread endet, während die Objekte in seiner Arena noch am Leben sind. Dazu müssen wir die Lebensdauer des Speicherpools von der Arena (die über den thread_local-Speicher mit der Lebensdauer des Threads verknüpft ist) trennen. Der Zuordner kann sich um solche veralteten Speicherpools kümmern. Zukünftige Streams werden sie akzeptieren.
Um dies zu implementieren, müssen Sie herausfinden, ob noch zugewiesener Speicher vorhanden ist. Die Datenstruktur weiß nichts über den allokierten Speicher, nur über den freien Speicher. Der schnellste Weg zur Überprüfung besteht also darin, den gesamten Stack zu durchlaufen und zu zählen, wie viele Knoten er hat. Wenn es weniger Knoten gibt, als auf alle zugewiesenen Seiten passen, wird immer noch Speicher verwendet.
Vergleich von Strömungsmodellen
Jetzt gibt es also vier Multithreading-Modelle mit unterschiedlichen Kompromissen in Bezug auf Leistung, Speicher-Overhead und Parallelität.
• Singlethreaded (single-threaded), als Trivialfall mit einer Arena und ohne Locks.
• Das Shared-Pool-Modell, bei dem alle Threads auf derselben Arena mit zwei Sperren arbeiten.
• Ein Multi-Pool-Modell, bei dem jeder Thread in seiner eigenen Arena bleiben muss und keine Sperren benötigt.
• Schließlich das Multithread-Modell, bei dem Threads von ihrer eigenen Arena zugewiesen werden, Speicher jedoch von jedem Thread freigegeben werden kann und Threads beendet werden können, während der von ihrer Arena zugewiesene Speicher noch verwendet wird.
Die ersten drei Modelle werden viele Anwendungsfälle haben, aber für den QEvent-Fall benötigen Sie ein Multithread-Modell.
Das Ausführen des vorherigen Tests mit diesen verschiedenen Implementierungen, aber ohne Verwendung von Threads, misst den Netto-Overhead, den die verschiedenen Strategien darstellen:
Es scheint, dass der zusätzliche Code, der zum Implementieren der Arena-Strategie erforderlich ist, nur sehr wenig Overhead mit sich bringt. Das Shared-Pool-Modell hingegen hat keinen großen Vorteil gegenüber der einfachen Verwendung von malloc, obwohl es dennoch nützlich sein kann, wenn man die Speicherfragmentierung in Betracht zieht.
Multithread-Benchmarking
Das Benchmarking von Allokatoren in einem realistischen Szenario mit mehreren Threads ist nicht einfach. Sogar das malloc-System ist sehr schnell, sodass es schwierig ist, die tatsächliche Auswirkung des Zuordners zu messen, wenn Sie etwas anderes als das Zuweisen und Freigeben von Speicher in einem Test tun. Wenn jedoch nur Speicher zugewiesen und freigegeben wird, dann wird die Auswirkung von Sperrenkonflikten in Allokatoren stark übertrieben. Andererseits müssen Entwickler möglicherweise Synchronisierungsprimitive wie Mutexe oder Wartebedingungen verwenden, um den Datenfluss in realistischen Producer/Consumer-Szenarien zu modellieren (z. B. wenn Qt QMetaCallEvent für Signal-/Slot-Verbindungen verwendet, die Datenströme kreuzen). Dadurch werden die Auswirkungen von Sperren in der Zuweisung ausgeblendet.
Die relativen Zahlen sollten jedoch eine Vorstellung davon vermitteln, wie effizient der Qt-Allocator ist, der unter Stress deutlich schneller ist als andere und sich mit hoher Wahrscheinlichkeit positiv auf die Leistung einer realen Anwendung auswirken wird. Basierend auf der Beobachtung aus dem ersten Test, dass alle Allokatoren die gleichen Leistungsmerkmale haben, egal wie groß die Objekte sind. Jetzt führen wir nur einen Test für 16-Byte-Objekte durch, aber mit so vielen Threads, wie wir Prozessoren haben.
Das hier verwendete Threading-Modell ist die vollständige Multithread-Implementierung, bei der der Qt-Allocator die schnellste Allzweckalternative immer noch um den Faktor 2,5 übertrifft und das malloc-System standardmäßig einen Faktor von mindestens 7 hat.
Im nächsten Artikel werden wir uns mit Methoden zum Testen und Debuggen von Speicher befassen. Lassen Sie uns zeigen, wie die bisher entwickelten Ideen bei der Verteilung von Objekten unterschiedlicher Größe verwendet werden können. Und vielleicht finden wir heraus, wie wir die leeren Seiten befreien können.
