У меня хобби такое, аллокаторы переизобретать.
Аллокаторов вагон, маленькой тележкой занимаюсь пока я. Практически у каждой программы свой уникальный паттерн мемори-менеджмента. Некоторым нужно аллоцировать очень много маленьких объектов (как вот питон), некоторые жрут килобайтами (как вот компиляторы). Ясен хуй, каждый из кейсов накладывает свои ограничения, вокруг которых можно чуть эффективнее играться. Пускай это будет некий оптимум. Даже general-purpose аллокаторы блуждают вокруг чутка разных усреднённых оптимумов - скорость, фрагментация, thread-safety. По хорошему, конечно, и их тоже под задачу выбирать надо. Как жаль что поебать.
Есть сегмент памяти, у нас там 4 объекта живёт. Скажем, два посередине освобождаются, и у нас остаётся два свободных блока - и два занятых по краям. Нам бы эту память посередине переиспользовать, но аллокатор-то не может знать, какого размера будут новые объекты. Это называется coalescing (объеденить два маленьких сегмента для одного большого объекта) и splitting (разбиение большего сегмента для объекта поменьше).
Вот сначала и был dlmalloc, отец ptmalloc и дед glibc's malloc. О нём и поговорим.
Его инвариант - не может быть двух соседствующих свободных блоков. То есть, занято-свободно-занято-... идёт в строго шахматном порядке:
chunk A | FREE | FREE | chunk B
↓
chunk A | LARGE FREE | chunk B
Но устроен он интереснее. У него есть отдельные корзины (bins) для маленьких <256 байт объектов, и отдельное бинарное дерево для >256 байт (но меньше 256 килобайт). Логика такая: оверхед 8 байт для аллокации на 40 байт это дохуя. Оверхед 10 килобайт для аллокации на 400 килобайт - это норм. Сами smallbins - это просто double linked-list, при том зацикленные. Их 28 штук, на каждый (разумный) size-class. В неаллоцированных и лежат как раз указатели на предыдущий и следующий узлы, пока они не будут выделены и их не перезапишет программа своей хуйнёй. На них есть своя лукап-таблица на 32 вхождения, поэтому выделение маленьких объектов пиздец быстрое и константное.
Бинарное дерево у них называется treebin (видимо чтобы не путать). Это, ну... Просто бинарное дерево, самое обыкновенное. Правда, они тоже делятся на size classes, только тут они уже очень широкие и идут по степеням двойки (каждый следующий size class range экспоненциально больше). Подходящий блок внутри них ищется по стратегии best-fit, то есть куда аллокация лучше всего влазит. Правда, с небольшой девиацией - обычно best-fit выбирает свободный блок, который максимально близок по размеру к запрашиваемому. Но тут, если для 380кб аллокации будут претенденты 400кб и 900кб, то выбор падёт на последнего - потому что после него останется 520кб дура. Аллокатору такая идея нравится больше, так как можно будет ещё один здоровый кусок нормально туда уместить. Его стратегия вообще agressively coalesce:
We don't know the future, so use a generally robust policy: coalesce aggressively, preserve large holes by best-fit for larger allocations, and use fast size classes/locality heuristics for small allocations.
Этим-то он и отходит от теоретического best-fit.