Разработчик языка lone, lisp-интерпретатора на freestanding C (без libc и malloc), начал с простого самодельного аллокатора. Он сделал связный список блоков с флагами free, размером и указателем на данные. Аллокатор работал по принципу first fit — возвращал первый подходящий блок. Чтобы не тратить лишнюю память, он добавил split: разрезал большой блок на два — ровно под запрос и остаток. При освобождении блок просто помечался free, а coalesce объединял соседние свободные блоки обратно.
У этого аллокатора куча проблем: линейный поиск при каждом malloc, сильная фрагментация, накладные расходы на заголовки (30-50%), уязвимости. Но lone продержался на нём около трёх лет — памяти хватало, чтобы создавать объекты для разработки языка.
Затем возникла задача для сборщика мусора: conservative GC сканирует стек и проверяет, являются ли слова указателями на lisp-объекты. Чтобы не делать квадратичное сравнение, разработчик придумал первую специализированную кучу: связный список массивов значений (linked list of arrays). Каждый массив — это набор lisp-значений, лежащих плотно друг за другом. GC просто проверяет, попадает ли потенциальный указатель в диапазон какого-нибудь массива. Аллокатор не выделял новые значения, а «воскрешал» мёртвые слоты в этих массивах.
Но оставалась проблема: массивы нельзя легко расширять — при ресайзе все указатели внутрь массива повисают. А в lisp все объекты — это указатели. Разработчик осознал «тиранию указателей»: они ленивы и не двигаются. Тогда он переписал систему представления значений: перестал хранить указатели, вместо этого все lisp-значения стали индексами в одном большом плоском массиве — единственной куче (the lone heap). Связанные списки ушли. Теперь код оперирует только позиционно-независимыми индексами, а реальный указатель вычисляется на лету как heap base + index.
Это позволило использовать mmap и mremap. Куча теперь состоит из страниц, а каждый lisp-объект выровнен до 64 байт — ровно одна кеш-линия. При росте кучи разработчик вызывает linux_mremap с флагом MREMAP_MAYMOVE — ядро перестраивает таблицы страниц, перемещая всю кучу без единого копирования. Это почти бесплатный realloc.
GC по-прежнему линейно сканирует кучу от начала, ища мёртвые слоты для повторного использования — другого выхода нет, потому что любой объект (даже с индексом 0) может быть убит сборщиком. Так из грубого самодельного аллокатора выросла эффективная, кеш-дружественная mremap-куча для lisp-интерпретатора.