Stack allocator: el truco de Blizzard para asignar memoria

En un juego de mundo abierto con 100 MB de memoria compartida entre el nivel y el personaje, tener 40 MB libres no garantiza nada: si esos 40 MB están partidos en dos bloques de 20 MB y la siguiente reserva pide 30 MB, la asignación falla. Ese es el problema de la fragmentación, y la solución que el equipo de StarCraft 2 en Blizzard usó —un stack allocator de doble cabeza— se aplica igual de bien a cualquier backend que gestione memoria transitoria a alta frecuencia.

¿Qué es un stack allocator y por qué acelera tanto?

Un stack allocator —también llamado bump allocator— no busca huecos ni mantiene listas de bloques libres. Reserva un bloque fijo de memoria (por ejemplo, 1 MB) y guarda una única variable entera, el tos (top of stack), que indica dónde termina lo que ya se usó. Asignar es devolver la dirección que apunta tos y sumarle el tamaño pedido. Liberar todo es poner tos en cero.

• Asignar cuesta una suma de enteros.
• Liberar todo cuesta una asignación de entero.
• No hay metadatos por bloque, ni recorrido de listas, ni búsqueda del hueco que mejor encaje.

El autor del blog demofox cuenta que vivió el antes y el después. Alrededor de 2010 trabajaba en Surreal Software (Midway Seattle) en el juego de mundo abierto This is Vegas, que se canceló cuando Midway cerró. Una de sus tareas era la programación de animación: cada estado de un conjunto de huesos era un árbol de mezclas, y evaluar y mezclar esas animaciones en CPU generaba muchísimas reservas dinámicas por frame. El asignador aparecía como punto caliente en el profiler.

La solución fue un stack allocator que se reseteaba a cero cuando el blending terminaba y los resultados ya estaban copiados a los buffers que iban al vertex shader. El resultado, según el propio autor, fue un cambio radical: la asignación dejó de tener tiempo medible.

Hay tres límites que conviene tener presentes antes de copiar la idea:

• No llama constructores ni destructores. La construcción se puede resolver con placement new, pero destruir de forma ordenada es manual y propenso a errores. El patrón funciona mejor con tipos simples.
• Permite liberaciones parciales. Si guardas el valor de tos al entrar en un nivel de un proceso recursivo y lo restauras al salir, cada nivel libera lo suyo sin tocar el resto.
• Funciona en multihilo. Basta con que la suma al tos sea atómica para que varios hilos asignen del mismo stack, algo útil en esquemas fork/join o en algoritmos que corren en GPU.

¿Cómo funciona el stack allocator de doble cabeza?

El problema que resuelve aparece cuando dos sistemas reservan y liberan cantidades variables de memoria en momentos distintos. El autor lo escuchó de James Anhalt, su jefe en el equipo de StarCraft 2 en Blizzard, que lo había usado para resolver un caso real de fragmentación.

El ejemplo es claro. Supón 100 MB de memoria compartida entre el nivel (que se transmite desde disco a medida que el jugador avanza) y el personaje (que cambia de forma). El nivel reserva 20 MB, el personaje 30 MB, el nivel otros 20 MB y el personaje los 30 MB finales. Ahora el jugador llega a una zona nueva y el nivel libera todo. La nueva geometría necesita una sola reserva de 30 MB. Hay 40 MB libres, pero partidos en dos bloques de 20 MB: la reserva falla aunque sobre memoria. Eso es fragmentación, y en entornos con memoria acotada es un problema serio.

La solución del doble encabezado es tener un solo bloque de memoria con dos tos:

• El del nivel crece hacia arriba desde el inicio del bloque.
• El del personaje crece hacia abajo desde el final.
• Se sabe que no queda memoria cuando ambos se cruzan, es decir, cuando el tos del nivel supera al del personaje.

Así, cuando el nivel necesita cambiar, resetea su tos a cero y vuelve a reservar lo que necesita, sin fragmentación. Lo mismo hace el personaje desde su extremo. Y sigue funcionando en multihilo: basta con que las sumas a cada tos sean atómicas, incluso si distintos hilos reservan desde cualquiera de los dos lados.

¿Por qué no usar dos stack allocators separados? Porque el doble encabezado sirve cuando sabes que el tamaño de un solo stack alcanza para los dos sistemas, pero la proporción entre ambos es flexible. En el ejemplo, un nivel puede necesitar más memoria y el personaje menos, sin que tengas que redimensionar pools ni reservar de más por si acaso.

¿Cómo se guardan objetos de tamaño variable en un espacio fijo?

Hay una variante muy útil para empaquetar objetos de tamaño variable en una región fija con acceso aleatorio por índice. El caso típico: construir un paquete de red de tamaño fijo que contenga una cantidad variable de comandos de tamaños distintos, y poder recorrerlos con facilidad.

El truco es usar el doble encabezado con dos roles:

• Un stack guarda los objetos (los datos).
• El otro stack guarda una tabla de enteros con el offset donde vive cada objeto.

Al reservar, escribes el objeto en la posición que marca el primer tos, avanzas ese tos y luego reservas un entero en el segundo stack donde anotas el offset. Repites el proceso con cada objeto. Para saber cuántos hay, puedes llevar un contador aparte o usar un valor centinela en la tabla de offsets.

Esta configuración también admite multihilo sin necesidad de hacer transaccionales las dos actualizaciones con un bucle de compare-and-swap. Y como los objetos se referencian por offset, puedes eliminarlos o moverlos dentro de la región y basta con actualizar la tabla: otra forma de combatir la fragmentación.

La documentación del Vulkan Memory Allocator de AMD describe este mismo algoritmo lineal para pools de memoria personalizados, así que no es una curiosidad de un solo estudio.

¿Qué significa esto para tu startup?

No necesitas escribir un motor de videojuegos para aprovechar esto. Cualquier servicio que arme y descarte estructuras temporales a alta frecuencia —parsear un JSON, serializar una respuesta, componer un lote de eventos— paga el costo de un asignador general en cada operación.

Tres acciones concretas:

• Perfila antes de tocar nada. Busca si el asignador aparece como punto caliente en las rutas que se ejecutan miles de veces por segundo (por frame, por request, por mensaje). Si no aparece ahí, optimizar esa capa no te va a mover la aguja.
• Aísla la memoria transitoria. Identifica los buffers que solo viven dentro de un ciclo (una petición, un frame, un job) y muévelos a un arena o stack allocator que se resetea al terminar el ciclo. Es el cambio con mejor relación esfuerzo/beneficio.
• Si el problema es fragmentación entre dos sistemas con proporciones variables, evalúa el doble encabezado antes de crear dos pools separados y sobredimensionados.

Y si el cuello de botella no está en la memoria transitoria sino en el asignador general, hay otra vía. Según WWWhat's new, Microsoft Research publicó en mayo de 2026 un análisis de mimalloc, su asignador open source con licencia MIT de unas 12.000 líneas que ya usan servicios de backend de Meta y las compilaciones optimizadas de CPython. En sus benchmarks supera a glibc entre un 10% y un 50% en throughput multihilo y usa entre un 20% y un 40% menos de memoria en aplicaciones de larga duración. Es un reemplazo directo de malloc y free, así que se puede probar sin reescribir código.

Para un equipo en LATAM o España con presupuesto de infraestructura ajustado, la memoria no es un detalle abstracto: es factura de nube. Menos fragmentación y menos footprint significan más instancias por servidor, y eso se traduce directo en runway.

Conclusión

El stack allocator de doble cabeza no es una técnica exótica: es la respuesta a una pregunta muy concreta —cómo comparto un bloque de memoria entre dos sistemas que crecen y se encogen sin coordinarse— y su respuesta es tan simple como dos enteros que avanzan en direcciones opuestas hasta cruzarse. La lección para un founder es más amplia: cuando el rendimiento se cae, muchas veces el problema no está en el algoritmo de negocio sino en la capa de gestión de recursos que nadie mira. Medir con un profiler antes de reescribir sigue siendo el mejor atajo.

Fuentes

• The Double Headed Stack Allocator (fuente original)
• Microsoft publica el análisis definitivo de mimalloc
• Vulkan Memory Allocator: custom memory pools