Список свободной памяти
Список свободной памяти (англ. free list) — структура данных, используемая в алгоритмах динамического выделения памяти. Принцип работы заключается в объединении свободных областей памяти в связанный список, используя первое слово каждой свободной области в качестве указателя на следующий участок. Этот подход наиболее удобен при выделении памяти из пула, где все объекты имеют одинаковый размер.
Списки свободной памяти упрощают операции выделения и освобождения памяти: чтобы освободить область, нужно просто добавить её в этот список, а чтобы выделить область можно просто удалить последнюю область в списке и использовать её. Если размеры областей разные, то необходим поиск области достаточно большого размера, что может быть затратно по ресурсам.
Списки свободной памяти имеют недостаток, присущий связанным спискам — низкую локальность ссылок, что влечёт неэффективность использования кэша. Также в таких списках не происходит автоматического объединения соседних областей для выделения областей большего размера, в отличие от «системы двойников» (англ. buddy memory allocation), описанной Кнутом в монографии «Искусство программирования» . Тем не менее, списки свободной памяти находят свой применение в простых приложениях, где не нужен полноценный аллокатор памяти, или его накладные расходы слишком велики.