Wie funktioniert jemalloc? Was sind die Vorteile?

75

Firefox 3 wurde mit einem neuen Allokator geliefert : jemalloc.

Ich habe an mehreren Stellen gehört, dass dieser neue Allokator besser ist. Die Top-Google-Ergebnisse gaben jedoch keine weiteren Informationen und ich bin daran interessiert, wie genau es funktioniert.

Albert
quelle

Antworten:

126

jemallocerschien zuerst für FreeBSD, die Idee eines "Jason Evans", daher das "je". Ich würde ihn verspotten, weil er egoistisch ist, hätte ich nicht einmal ein Betriebssystem namens geschrieben paxos:-)

In diesem PDF finden Sie alle Details. Es ist ein Whitepaper, das detailliert beschreibt, wie die Algorithmen funktionieren.

Der Hauptvorteil ist die Skalierbarkeit in Multiprozessor- und Multithread-Systemen, die teilweise durch die Verwendung mehrerer Arenen (die Teile des Rohspeichers, aus denen Zuordnungen vorgenommen werden) erreicht wird.

In Situationen mit einem Thread haben mehrere Arenen keinen wirklichen Vorteil, sodass eine einzelne Arena verwendet wird.

In Situationen mit mehreren Threads werden jedoch viele Arenen erstellt (viermal so viele Arenen wie Prozessoren), und diesen Arenen werden Threads im Round-Robin-Verfahren zugewiesen.

Dies bedeutet, dass Sperrenkonflikte reduziert werden können, da zwar mehrere Threads gleichzeitig mallocoder freegleichzeitig aufgerufen werden , sie jedoch nur dann miteinander konkurrieren, wenn sie dieselbe Arena gemeinsam nutzen. Zwei Threads mit unterschiedlichen Arenen beeinflussen sich nicht gegenseitig.

Darüber hinaus wird jemallocversucht, die Cache-Lokalität zu optimieren, da das Abrufen von Daten aus dem RAM viel langsamer ist als die Verwendung von Daten, die sich bereits in den CPU-Caches befinden (im Konzept nicht anders als der Unterschied zwischen schnellem Abrufen aus dem RAM und langsamem Abrufen von der Festplatte). Zu diesem Zweck wird zunächst versucht, die Speichernutzung insgesamt zu minimieren, da dadurch eher sichergestellt wird, dass sich der gesamte Arbeitssatz der Anwendung im Cache befindet.

Und wo dies nicht erreicht werden kann, wird versucht, sicherzustellen, dass die Zuordnungen zusammenhängend sind, da der gemeinsam zugewiesene Speicher tendenziell zusammen verwendet wird.

Aus dem Whitepaper geht hervor, dass diese Strategien den derzeit besten Algorithmen für die Verwendung mit einem Thread eine ähnliche Leistung bieten und gleichzeitig Verbesserungen für die Verwendung mit mehreren Threads bieten.

paxdiablo
quelle
14

Es gibt eine interessante Quelle: die C-Quelle selbst: https://dxr.mozilla.org/mozilla-central/source/memory/build/mozjemalloc.cpp ( alt )

Am Anfang beschreibt eine kurze Zusammenfassung, wie es ungefähr funktioniert.

// This allocator implementation is designed to provide scalable performance
// for multi-threaded programs on multi-processor systems.  The following
// features are included for this purpose:
//
//   + Multiple arenas are used if there are multiple CPUs, which reduces lock
//     contention and cache sloshing.
//
//   + Cache line sharing between arenas is avoided for internal data
//     structures.
//
//   + Memory is managed in chunks and runs (chunks can be split into runs),
//     rather than as individual pages.  This provides a constant-time
//     mechanism for associating allocations with particular arenas.
//
// Allocation requests are rounded up to the nearest size class, and no record
// of the original request size is maintained.  Allocations are broken into
// categories according to size class.  Assuming runtime defaults, 4 kB pages
// and a 16 byte quantum on a 32-bit system, the size classes in each category
// are as follows:
//
//   |=====================================|
//   | Category | Subcategory    |    Size |
//   |=====================================|
//   | Small    | Tiny           |       4 |
//   |          |                |       8 |
//   |          |----------------+---------|
//   |          | Quantum-spaced |      16 |
//   |          |                |      32 |
//   |          |                |      48 |
//   |          |                |     ... |
//   |          |                |     480 |
//   |          |                |     496 |
//   |          |                |     512 |
//   |          |----------------+---------|
//   |          | Sub-page       |    1 kB |
//   |          |                |    2 kB |
//   |=====================================|
//   | Large                     |    4 kB |
//   |                           |    8 kB |
//   |                           |   12 kB |
//   |                           |     ... |
//   |                           | 1012 kB |
//   |                           | 1016 kB |
//   |                           | 1020 kB |
//   |=====================================|
//   | Huge                      |    1 MB |
//   |                           |    2 MB |
//   |                           |    3 MB |
//   |                           |     ... |
//   |=====================================|
//
// NOTE: Due to Mozilla bug 691003, we cannot reserve less than one word for an
// allocation on Linux or Mac.  So on 32-bit *nix, the smallest bucket size is
// 4 bytes, and on 64-bit, the smallest bucket size is 8 bytes.
//
// A different mechanism is used for each category:
//
//   Small : Each size class is segregated into its own set of runs.  Each run
//           maintains a bitmap of which regions are free/allocated.
//
//   Large : Each allocation is backed by a dedicated run.  Metadata are stored
//           in the associated arena chunk header maps.
//
//   Huge : Each allocation is backed by a dedicated contiguous set of chunks.
//          Metadata are stored in a separate red-black tree.
//
// *****************************************************************************

Es fehlt jedoch eine eingehendere Algorithmusanalyse.

Albert
quelle
4

Was welche Vorteile jemalloc zu mozilla gebracht, pro http://blog.pavlov.net/2008/03/11/firefox-3-memory-usage/ (auch erste Ergebnis google für mozilla + jemalloc):

[...] kamen zu dem Schluss, dass jemalloc uns nach einem langen Lauf die geringste Fragmentierung verlieh . [...] Unsere automatisierten Tests unter Windows Vista zeigten einen Rückgang der Speichernutzung um 22%, als wir jemalloc einschalteten.

Nickolay
quelle
1

Aerospike hat jemalloc 2013 bereits in einer Privatniederlassung implementiert. 2014 wurde es in Aerospike 3.3 integriert. Psi Mankoski hat gerade über die Implementierung von Aerospike sowie darüber geschrieben, wann und wie jemalloc für eine hohe Skalierbarkeit effektiv eingesetzt werden kann .

jemalloc hat Aerospike wirklich dabei geholfen, die Vorteile moderner Multithread-Computerarchitekturen mit mehreren CPUs und mehreren Kernen zu nutzen. Es gibt auch einige sehr wichtige Debugging-Funktionen, die in jemalloc integriert sind, um Arenen zu verwalten. Durch das Debuggen konnte Psi beispielsweise feststellen, was ein echter Speicherverlust war und was das Ergebnis einer Speicherfragmentierung war. Psi erläutert auch, wie der Thread-Cache und die Zuweisung pro Thread zu einer Verbesserung der Gesamtleistung (Geschwindigkeit) geführt haben.

Peter Corless
quelle