Le secret des 12 000 lignes derrière la vitesse de Bing : comment mimalloc a surmonté le compromis des allocateurs

L'allocation mémoire passe souvent inaperçue dans les performances système. Mais pour l'équipe Bing de Microsoft, le passage à un allocateur personnalisé construit par la propre division de recherche de l'entreprise s'est directement traduit par des temps de réponse plus rapides. Cet allocateur, mimalloc, fait l'objet d'un nouvel article de blog du groupe RiSE chez Microsoft Research, qui explique les décisions de conception lui permettant de passer d'un runtime de langage de programmation monothread à un service cloud de 500 GiB.

Avec seulement 12 000 lignes de C, mimalloc est délibérément compact. Sa véritable innovation réside dans la manière dont il contourne un compromis classique des systèmes : le choix entre l'extensibilité sur de nombreux threads et le maintien de l'utilisation mémoire proche de ce dont l'application a réellement besoin. Le blog, publié sur le site web de Microsoft Research, explore l'architecture avec une profondeur technique inhabituelle, incluant des extraits de code du chemin rapide et une description du mécanisme de "vol de page" développé avec l'équipe Azure Cosmos DB.

Le chemin rapide : peu de branches, pas d'atomiques

L'idée centrale de mimalloc est que la plupart des allocations sont petites et locales au thread. Chaque thread possède son propre tas local, ou "theap", qui détient un ensemble de "pages mimalloc" de 64 Ko. Chaque page contient des blocs d'une seule classe de taille. Pour allouer un bloc, le thread le retire simplement d'une liste libre, sans verrou, sans opération atomique. Le blog fournit le résultat assembleur pour le chemin rapide sur x64 : sept instructions avec seulement deux branches rares (une pour les allocations surdimensionnées, une pour une page vide).

Cette minimisation des branches provient d'une stratégie d'initialisation minutieuse : le pointeur theap local au thread n'est jamais NULL, et toutes les entrées du tableau small_pages pointent vers des pages vides pré-initialisées (dont la liste libre est NULL). Comme le notent les auteurs, cela élimine deux vérifications conditionnelles dont la plupart des allocateurs ont besoin, convertissant le cas courant en une ligne droite d'instructions.

Trois listes libres par page, l'inspiration randomisée

Là où mimalloc diverge le plus nettement de ses pairs, c'est dans sa conception de liste libre. Chaque page mimalloc maintient trois listes libres : la liste free principale pour les allocations, la liste local_free pour les blocs libérés par le thread propriétaire, et la liste thread_free, atomique, pour les blocs libérés par d'autres threads. Un programme peut facilement avoir des milliers de listes libres en vol.

Le blog relie explicitement cette conception aux algorithmes randomisés. Tout comme un treap utilise des divisions aléatoires pour maintenir un arbre équilibré sans rotations complexes, mimalloc repose sur la loi des grands nombres : avec des milliers de listes atomiques par page, la probabilité que deux threads tentent simultanément de libérer sur la même page est faible. La plupart des opérations compare-and-swap sont sans contention et peu coûteuses. "Par pur hasard, nous obtenons également des arbres suffisamment équilibrés", écrivent les auteurs, prolongeant l'analogie.

Cette disposition par page améliore également la localité du cache. Parce que l'allocation a tendance à rester dans la même page jusqu'à ce qu'elle soit pleine, les blocs récemment libérés sont susceptibles de se trouver dans les mêmes lignes de cache que celles déjà utilisées par le thread, un contraste frappant avec les conceptions ayant une seule liste libre par classe de taille, qui peuvent disperser les blocs en mémoire.

Le trilemme de l'allocateur : des benchmarks qui montrent la tension

L'article inclut un benchmark qui rend le compromis visible. Utilisant le pool de threads Windows avec environ 800 threads actifs, le test exécute une charge de travail qui alterne allocation, désallocation et brèves périodes de blocage, une simulation des services cloud modernes. Trois allocateurs sont comparés :

• Allocateur système standard : excellent partage mémoire (seulement 1,1× engagé par rapport aux données vivantes), mais n'a réussi à allouer que 56 Go pendant la durée du test. Il n'a pas passé à l'échelle.
• Un allocateur concurrent concurrent : a alloué 262 GiB, près de 4 fois plus, mais a engagé 4 fois plus de mémoire que les données vivantes. À grande échelle, ce ratio devient prohibitif.
• mimalloc : a alloué les mêmes 262 GiB tout en maintenant la mémoire engagée à seulement 1,3× les données vivantes. La ligne rouge (engagée) reste proche de la ligne bleue (vivante).

Le blog attribue la percée au "vol de page", un mécanisme développé avec l'équipe Azure Cosmos DB qui permet aux threads de prendre possession des pages sans synchronisation coûteuse entre threads. Les auteurs promettent un prochain rapport technique avec une description précise, mais les résultats du benchmark suggèrent déjà que mimalloc atteint ce qui était longtemps considéré comme impossible : faire passer l'extensibilité du débit sans faire exploser la mémoire.

De Lean à Bing à CPython

Conçu à l'origine en 2020 pour prendre en charge les langages de programmation Lean et Koka, qui reposent tous deux sur le comptage de références guidé par le compilateur, mimalloc a depuis été adopté bien au-delà de Microsoft Research. Bing l'utilise en production, contribuant directement à des temps de réponse plus rapides. En dehors de l'entreprise, c'est l'allocateur mémoire pour la version NoGIL de CPython 3.13+, intégré à Unreal Engine, et utilisé dans des jeux comme Death Stranding. Son wrapper Rust seul voit plus de 100 000 téléchargements par jour.

Le projet est hébergé sur GitHub et a accumulé plus de 12 000 étoiles. Des ports existent pour Windows, macOS, Linux, FreeBSD, NetBSD, DragonFly BSD et diverses consoles de jeux. Le blog souligne que ses structures de données internes claires, la philosophie "des tableaux, pas d'organigrammes" empruntée à Fred Brooks, ont permis aux contributeurs externes de porter et de personnaliser plus facilement que de nombreux allocateurs industriels.

Ce que cela signifie pour les bâtisseurs de systèmes

Pour les équipes construisant des services à haute concurrence, en particulier celles utilisant de grands modèles de langage avec des empreintes mémoire de centaines de gigaoctets, les temps d'allocation bornés dans le pire des cas et la faible fragmentation interne de mimalloc offrent une voie concrète vers de meilleures performances sans réécrire le code applicatif. C'est un remplacement direct de malloc et free.

La leçon plus profonde est que l'allocateur passe à l'échelle non pas grâce à une structure de données révolutionnaire, mais grâce à un pari statistique délibéré : répartir le coût de coordination sur des milliers de minuscules listes, et la probabilité de conflit s'effondre. À une époque où le nombre de threads par serveur continue d'augmenter, et où l'inférence LLM consomme souvent des centaines de gigaoctets, ce pari porte ses fruits en production, à grande échelle, chez Microsoft et ailleurs.