El secreto de 12.000 líneas detrás de la velocidad de Bing: cómo mimalloc venció la compensación del asignador de memoria

La asignación de memoria a menudo pasa desapercibida en el rendimiento de los sistemas. Pero para el equipo de Bing de Microsoft, cambiar a un asignador personalizado construido por la propia división de investigación de la empresa se tradujo directamente en tiempos de respuesta más rápidos. Ese asignador, mimalloc, es el tema de una nueva entrada de blog del grupo RiSE en Microsoft Research, que explica las decisiones de diseño que le permiten escalar desde un runtime de un solo hilo hasta un servicio en la nube de 500 GiB.

Con solo 12.000 líneas de C, mimalloc es deliberadamente compacto. Su verdadera innovación radica en cómo evita una clásica compensación de sistemas: elegir entre escalar a través de muchos hilos y mantener el uso de memoria cercano a lo que la aplicación realmente necesita. El blog, publicado en el sitio web de Microsoft Research, profundiza en la arquitectura con un inusual nivel de detalle técnico, incluyendo fragmentos de código de la ruta rápida y una descripción del mecanismo de "robo de páginas" desarrollado con el equipo de Azure Cosmos DB.

La ruta rápida: pocas bifurcaciones, sin atómicos

La idea central de mimalloc es que la mayoría de las asignaciones son pequeñas y locales al hilo. Cada hilo obtiene su propio montón local de hilo, o "theap", que posee un conjunto de "páginas mimalloc" de 64 KiB. Cada página contiene bloques de una única clase de tamaño. Para asignar un bloque, el hilo simplemente lo extrae de una lista libre, sin bloqueos ni operaciones atómicas. El blog proporciona la salida de ensamblador para la ruta rápida en x64: siete instrucciones con solo dos bifurcaciones poco comunes (una para asignaciones de gran tamaño, otra para una página vacía).

Esta minimización de bifurcaciones proviene de una estrategia de inicialización cuidadosa: el puntero theap local del hilo nunca es NULL, y todas las entradas en el array small_pages apuntan a páginas vacías preinicializadas (cuya lista libre es NULL). Como señalan los autores, esto elimina dos comprobaciones condicionales que la mayoría de los asignadores necesitan, convirtiendo el caso común en una línea recta de instrucciones.

Tres listas libres por página, la inspiración aleatorizada

Donde mimalloc más se diferencia de sus pares es en el diseño de su lista libre. Cada página de mimalloc mantiene tres listas libres: la lista libre principal free para asignaciones, la lista local_free para bloques liberados por el hilo propietario, y la lista thread_free, atómica, para bloques liberados por otros hilos. Un programa puede tener fácilmente miles de listas libres en vuelo.

El blog vincula explícitamente este diseño a algoritmos aleatorizados. Así como un treap utiliza divisiones aleatorias para mantener un árbol equilibrado sin rotaciones complejas, mimalloc se basa en la ley de los grandes números: con miles de listas atómicas por página, la probabilidad de que dos hilos intenten liberar simultáneamente en la misma página es baja. La mayoría de las operaciones compare-and-swap no tienen contención y son baratas. "Por mera casualidad, también terminamos con árboles lo suficientemente equilibrados", escriben los autores, extendiendo la analogía.

Esta disposición por página también mejora la localidad de caché. Debido a que la asignación tiende a permanecer dentro de la misma página hasta que está llena, los bloques liberados recientemente probablemente estén en las mismas líneas de caché que el hilo ya está utilizando, un marcado contraste con los diseños que tienen una única lista libre por clase de tamaño, que pueden dispersar los bloques por la memoria.

El trilema del asignador: puntos de referencia que muestran la tensión

La publicación incluye un punto de referencia que hace visible la compensación. Usando el grupo de hilos de Windows con aproximadamente 800 hilos activos, la prueba ejecuta una carga de trabajo que alterna asignación, desasignación y períodos breves de bloqueo, una simulación de servicios en la nube modernos. Se comparan tres asignadores:

• Asignador estándar del sistema: excelente uso compartido de memoria (solo 1,1× comprometido sobre datos activos), pero logró asignar solo 56 GB durante la duración de la prueba. No escaló.
• Un asignador concurrente competidor: asignó 262 GiB, casi 4× más, pero comprometió 4× más memoria que los datos activos. A escala, esa relación se vuelve prohibitiva.
• mimalloc: asignó los mismos 262 GiB mientras mantenía la memoria comprometida en solo 1,3× los datos activos. La línea roja (comprometida) se mantiene cerca de la línea azul (activa).

El blog atribuye el avance al "robo de páginas", un mecanismo desarrollado con el equipo de Azure Cosmos DB que permite a los hilos tomar posesión de páginas sin costosa sincronización entre hilos. Los autores prometen un próximo informe técnico con una descripción precisa, pero los resultados del punto de referencia ya sugieren que mimalloc logra lo que durante mucho tiempo se consideró imposible: escalar el rendimiento sin disparar la memoria.

De Lean a Bing a CPython

Diseñado originalmente en 2020 para soportar los lenguajes de programación Lean y Koka, ambos basados en el conteo de referencias guiado por compilador, mimalloc ha sido adoptado mucho más allá de Microsoft Research. Bing lo usa en producción, contribuyendo directamente a tiempos de respuesta más rápidos. Fuera de la empresa, es el asignador de memoria para la versión NoGIL de CPython 3.13+, integrado en Unreal Engine, y utilizado en juegos como Death Stranding. Solo su envoltorio de Rust supera las 100.000 descargas por día.

El proyecto está alojado en GitHub y ha acumulado más de 12.000 estrellas. Existen versiones para Windows, macOS, Linux, FreeBSD, NetBSD, DragonFly BSD y varias consolas de juegos. El blog enfatiza que sus claras estructuras de datos internas, la filosofía de "tablas, no diagramas de flujo" tomada de Fred Brooks, han facilitado que los contribuyentes externos porten y personalicen el asignador en comparación con muchos asignadores de la industria.

Qué significa esto para los constructores de sistemas

Para los equipos que construyen servicios de alta concurrencia, especialmente aquellos que utilizan modelos de lenguaje grandes con huellas de memoria de cientos de gigabytes, los tiempos de asignación acotados en el peor caso y la baja fragmentación interna de mimalloc ofrecen un camino concreto hacia un mejor rendimiento sin reescribir el código de la aplicación. Es un reemplazo directo para malloc y free.

La lección más profunda es que el asignador escala no por una estructura de datos revolucionaria, sino por una apuesta estadística deliberada: distribuir el costo de coordinación a través de miles de listas diminutas, y la probabilidad de conflicto se desploma. En una era donde el número de hilos por servidor continúa creciendo, y donde la inferencia de LLM a menudo consume cientos de gigabytes, esa apuesta está dando frutos en producción, a escala, dentro y fuera de Microsoft.