El asignador de pila de doble cabeza que elimina la fragmentación de memoria
The Double Headed Stack Allocator
El asignador de pila (bump allocator) asigna memoria con una simple suma de enteros y libera todo con una asignación. En un juego de mundo abierto en Surreal Software, esto eliminó el costo de asignación en el perfilador. James Anhalt, de Blizzard, ideó el asignador de doble cabeza: dos pilas que crecen desde extremos opuestos del mismo bloque, una para el nivel y otra para el personaje, evitando la fragmentación cuando ambos sistemas asignan y liberan de forma independiente. También permite almacenar objetos de tamaño variable con acceso aleatorio mediante una tabla de offsets en la segunda pila.
El resultado fue como de la noche al día. La asignación ya no tomaba tiempo medible en el perfilador, porque asignar era una suma de enteros, y liberar toda la memoria era una única asignación de entero. No se puede ser más rápido que eso.
- tom_
Esto también funciona bien con un asignador ordinario. En un lugar anterior donde trabajé, teníamos una opción de asignación alta para el gestor de memoria ordinario, que encontraba la dirección más alta posible en lugar de la más baja. Bastante bueno para situaciones en las que necesitabas asignar algunos datos transitorios mientras creabas algunos datos persistentes, sin introducir fragmentación innecesaria.
- Panzerschrek
> Imagina que tuvieras un juego de mundo en streaming donde, a medida que el jugador recorre el mundo, la geometría de nivel antigua se desasigna y la nueva geometría de nivel se asigna y se transmite desde el disco.
En tal caso, un asignador tipo pila no es la mejor estrategia. Se puede usar algún tipo de asignador cíclico en su lugar. Según tengo entendido, Quake hacía esto para la caché de superficies.
- kevin_thibedeau
Los búferes bipartitos son mejores para almacenar una secuencia de objetos de tamaño variable. Funciona como un búfer circular y no te quedas atascado con el agotamiento de memoria del asignador de incremento. Esto requiere iteración secuencial, pero rara vez necesitas acceso aleatorio para ese tipo de cosas.
- windenntw
Y es por eso que AmigaOS permitía una opción MEMF_REVERSE en la llamada al asignador de memoria ( http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodo... )
En algún momento de 1995 o 1996 recuerdo haber hecho un parche de SO muy muy simple que forzaba todas las asignaciones > X tamaño ( 1KB o algo así ) a usar MEMF_REVERSE y eso hizo maravillas para reducir la fragmentación de memoria :)
- saagarjha
Este tipo de patrón es bastante común cuando se trata de algún tipo de canalización. Otra solución que he implementado antes al manejar pesos en streaming hacia una GPU es mapear la región dos veces de forma espejada y repartir punteros en orden desde la primera región, pero permitiendo que se envuelva al frente usando direccionamiento virtual. He encontrado que esto es un poco más potente, ya que permite asignar varias etapas por adelantado, pues no te quedas sin "lados" desde los que asignar. El asignador de doble cara, desafortunadamente, solo permite realmente 1 etapa extra para tu canalización.