Comment fonctionne jemalloc ? Quels en sont les avantages ?

Question

Firefox 3 a été livré avec un nouvel allocateur : jemalloc .

J'ai entendu à plusieurs endroits que ce nouvel allocateur est meilleur. Les premiers résultats de Google ne donnent pas plus d'informations et je suis curieux de savoir comment il fonctionne exactement.

Answer 1

jemalloc est apparu pour la première fois pour FreeBSD, l'idée d'un certain "Jason Evans", d'où le "je". Je me moquerais bien de son égoïsme si je n'avais pas écrit une fois un système d'exploitation appelé paxos :-)

Voir ce PDF pour plus de détails. Il s'agit d'un livre blanc qui décrit en détail le fonctionnement des algorithmes.

Le principal avantage est l'évolutivité dans les systèmes multiprocesseurs et multithreads, obtenue en partie grâce à l'utilisation de plusieurs arènes (les morceaux de mémoire brute à partir desquels les allocations sont effectuées).

Dans les situations où il n'y a qu'un seul fil, il n'y a pas de réel avantage à avoir plusieurs arènes, donc une seule arène est utilisée.

Cependant, dans les situations multithreads, de nombreuses arènes sont créées (quatre fois plus d'arènes qu'il n'y a de processeurs), et les threads sont assignés à ces arènes de manière round-robin.

Cela signifie que la contention des verrous peut être réduite car, alors que plusieurs threads peuvent appeler malloc o free en même temps, ils ne s'affronteront que s'ils partagent la même arène. Deux fils avec des arènes différentes ne s'affecteront pas l'un l'autre.

En outre, jemalloc tente d'optimiser la localité du cache, car l'extraction de données de la RAM est beaucoup plus lente que l'utilisation de données déjà présentes dans les caches du CPU (le concept n'est pas différent de la différence entre l'extraction rapide de données de la RAM et l'extraction lente de données du disque). À cette fin, il tente d'abord de minimiser l'utilisation de la mémoire dans son ensemble, car il est plus probable que l'ensemble des données de travail de l'application se trouve dans le cache.

Et, lorsque cela n'est pas possible, il essaie de s'assurer que les allocations sont contiguës, puisque la mémoire allouée ensemble tend à être utilisée ensemble.

D'après le livre blanc, ces stratégies semblent offrir des performances similaires à celles des meilleurs algorithmes actuels pour une utilisation monofilière, tout en offrant des améliorations pour une utilisation multi-filière.

Answer 2

Il existe une source intéressante : le C-source lui-même : https://dxr.mozilla.org/mozilla-central/source/memory/build/mozjemalloc.cpp ( vieux )

Au début, un court résumé décrit grossièrement son fonctionnement.

// 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.
//
// *****************************************************************************

Cependant, une analyse algorithmique plus approfondie fait défaut.

Answer 3

Quant aux avantages que jemalloc a apporté à Mozilla, par http://blog.pavlov.net/2008/03/11/firefox-3-memory-usage/ (également premier résultat de google pour mozilla+jemalloc) :

[...] a conclu que jemalloc nous a donné le fragmentation minimale après avoir fonctionné pendant une longue période de temps. [...] Nos tests automatisés sur Windows Vista ont montré que une baisse de 22 % de l'utilisation de la mémoire quand nous avons activé jemalloc.

Answer 4

Aerospike a implémenté jemalloc de retour dans une branche privée en 2013. En 2014, elle a été intégrée à Aerospike 3.3. Psi Mankoski vient d'écrire sur l'implémentation d'Aerospike, ainsi que sur le moment et la manière d'utiliser efficacement jemalloc pour Haute évolutivité .

jemalloc a vraiment aidé Aerospike à tirer parti des architectures informatiques modernes multithreadées, multi-CPU et multi-cœurs. Il y a également des capacités de débogage très importantes intégrées à jemalloc pour gérer les arènes. Le débogage a permis à Psi d'être en mesure de dire, par exemple, ce qui était une véritable fuite de mémoire, par rapport à ce qui était le résultat de la fragmentation de la mémoire. Psi explique également comment le cache des threads et l'allocation par threads ont permis une amélioration globale des performances (vitesse).