В мире аллокаторов: glibc, схемы и стратегии

glibc's malloc интересен. В основном тем, что концептуально это практически тот же dlmalloc, но в гораздо больших масштабах. Во-первых, у них есть thread-local tcache, чтобы не соваться в глобальные арены с их нагруженными локами. Тут аллокации происходят по segregated free list схеме - о ней см. ниже. Если тут ничего нет, мы идём тогда в fastbins - single linked lists чанков по их size-классам. Интересная штука, что когда они освобождаются, то они не объединяются сразу в большие сегменты. Ну, когда-нибудь, когда аллокатор решит консолидироваться - но не сразу, как в dlmalloc.

Если и там ничего не нашлось, тогда уже идут smallbins (полностью соответствущие таковым в dlmalloc) и largebins. Largebins заменили treebins в угоду перфоманса, вместо дерева они заделаны на двойном связном списке. Тут, помимо указателей на предыдущий и следующий узлы, ещё лежат их размеры. Ещё одно отличие от dlmalloc, кстати, что здесь никто не будет разбивать больший блок - идут просто по минимизации остатка.

То есть, glibc идёт всё дальше и дальше, пока где-то не найдётся местечко. Но первым делом он всё-таки не в tcache идёт, а в unsorted bin, куда скидываются все недавно освобождённые джанги. Правда, оттуда берётся сегмент, только если он идеально по размеру подходит.

Вот такой вот зверь.


О, фанфакт. У best-fit даже есть антонимическая пара - worst-fit, который пытается всегда в наибольший блок засунуть. Справляется, к слову, соответственно названию.

Коль уж речь зашла, фитов вообще до пизды. Но конкретно все эти - best-fit, first-fit (в первый попавшийся), last-fit (в последний попавшийся), next-fit (начало поиска там, где в прошлый раз кончили) - относятся к схеме sequental fits. Потому что друг от друга отличаются, как пригожин в париках. Есть, конечно, и другие схемы:
- segregated free list - список из очередей для разных size-классов, в каждой очереди свободные слоты, почти как treebins;
- buddy systems - как предыдущий, только хип размечается экспоненциально - делим пополам, вторую половину снова делим пополам, и так пока не усрёмся; фрагментация ебейшая, без героических оптимизаций и/или гибридизации сосёт;
- indexed fits - в сущности обычный sequental fit с индексирующей структурой данных - фактически этим treebin и является;
- bitmapped fits - битмапа, где каждый бит соответствует статусу сегмента фиксированной длины;

Последнее - прикольная, но ненужная вещь, GP аллокаторы его не имплементируют, потому им он, видите ли, медленный. Я пытался себе для HTTP2 его переизобрести, но в результате нашлась опция получше. Зато прекрасно применяют в mark-sweep сборщиках мусора.

Но сразу говорю, делить по схемам - дело гиблое. Как минимум, даже dlmalloc сел минимум на два стула, а glibc-шный это вообще ядерный микс из четырёх аллокаторов, где один из них вообще сразу две стратегии объединяет.

Так что, как обычно, практики наложили себе в руки, как только увидели, что наизобретали теоретики. Всё-таки скорее инженерное нежели математическое это дело, программирование.



Между делом: когда ресёрчил, то внезапно оказалось, что заголовки динмассива по-умному называются dope vector. Почему не метадатой назвать? А хуй его, гуси еблись, а информатик слово придумывал. Но это ещё ладно. Знаете, как указательная арифметика для адрессации массива называется, которая offset + index*sizeof(T)? Dead reckoning. Википедия ведёт вообще на линейную интерполяцию ИЗ НАВИГАЦИИ. БЛЯТЬ.