Двухголовый стековый аллокатор: как победить фрагментацию памяти в играх
The Double Headed Stack Allocator
В высокопроизводительных приложениях, таких как видеоигры, стандартные аллокаторы могут стать узким местом. Автор делится опытом использования стекового аллокатора (bump allocator) для временных данных, где выделение памяти сводится к сложению, а освобождение — к присваиванию. Затем он рассказывает о двухголовом стековом аллокаторе, который решает проблему фрагментации, позволяя двум системам (например, уровню и персонажу) расти навстречу друг другу в одном блоке памяти. Также рассматривается вариант с таблицей смещений для хранения объектов переменного размера.
Результат был как день и ночь. Аллокация больше не занимала измеримого времени в профайлере, потому что выделение памяти было целочисленным сложением, а освобождение всей памяти — одним целочисленным присваиванием. Быстрее уже некуда.
- tom_
Это хорошо работает и с обычным аллокатором. На моём предыдущем месте работы у обычного менеджера памяти была опция allocate high, которая находила максимально возможный адрес, а не минимальный. Довольно неплохо для ситуаций, когда нужно выделить временные данные при создании постоянных, не внося лишнюю фрагментацию.
- Panzerschrek
> Представьте, что у вас есть игра с потоковым миром, где, пока игрок бегает по миру, старая геометрия уровня освобождается, а новая геометрия уровня выделяется и подгружается с диска.
В таком случае стековый аллокатор — не лучшая стратегия. Вместо него можно использовать какой-нибудь циклический аллокатор. Насколько я знаю, Quake делал так для кэша поверхностей.
- kevin_thibedeau
Двусторонние буферы лучше подходят для хранения последовательности объектов переменного размера. Это работает как циклический буфер, и вы не застреваете из-за исчерпания памяти bump-аллокатора. Это требует последовательной итерации, но для таких вещей случайный доступ нужен редко.
- windenntw
И именно поэтому AmigaOS допускала опцию MEMF_REVERSE в вызове аллокатора памяти ( http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodo... )
Где-то в 95 или 96 году, помню, сделал очень-очень простой патч ОС, который заставлял все выделения размером > X (1KB или что-то в этом роде) использовать MEMF_REVERSE, и это творило чудеса в снижении фрагментации памяти :)
- saagarjha
Такой паттерн довольно распространён при работе с конвейеризацией какого-либо рода. Другое решение, которое я реализовывал раньше при потоковой передаче весов в GPU, — это зеркальное отображение региона дважды и выдача указателей по порядку из первого региона, но с возможностью зацикливания на начало с помощью виртуальной адресации. Я обнаружил, что это немного мощнее, так как позволяет выделять память на несколько стадий вперёд, поскольку у вас не заканчиваются «стороны» для выделения. Двусторонний аллокатор, к сожалению, реально позволяет только 1 дополнительную стадию для вашего конвейера.