Искал я несложные и адекватные идеи для менеджера и в рунете, и на англоязычных сайтах — всё никак не мог найти никаких хороших статей про адекватный, работающий не за O(N) аллокатор. Что же, сегодня мы рассмотрим более хорошую идею для менеджера памяти, продолжение помещаю под кат.
Теория
Из вики: Менеджер памяти — часть компьютерной программы (как прикладной, так и операционной системы), обрабатывающая запросы на выделение и освобождение оперативной памяти или (для некоторых архитектур ЭВМ) запросы на включение заданной области памяти в адресное пространство процессора.
Предлагаю так же перед продолжением прочитать эту статью.
Watermak Allocator
Что же, наверное самый простой из всех аллокаторов — Watermark Allocator. Суть его примерно следующая: вся память разбита на блоки, у блока есть заголовок, в котором лежит размер этого и предыдущего блока, статус блока(занят/свободен), зная адрес блока мы за O(1) можем получить адрес следующего и предыдущего блока.
Выделение памяти
Для выделения памяти нам просто напросто нужно бежать по блокам, и искать блок, размер которого больше или равен размеру требуемой для выделения памяти. Как вы уже поняли, асимптотика O(N) — плохо.Высвобождение памяти
Для высвобождения памяти нам достаточно установить статус блока как «свободный» — O(1) — супер!Но, как вы понимаете, могут начать образовываться дыры, в которых 2 и более свободных блоков — память дефрагментированна, при высвобождении можно просматривать соседние блоки, и в случае, когда один или два свободны — мержить их в один.
Аллокатор за логарифмическую скорость
Мы знаем, что нам надо искать только среди свободных блоков. Бегать только по свободным улучшает скорость в среднем в два раза, но это всё равно линия. Что же, зачем нам бегать по всем блокам, ища размер, если мы можем организовать дерево из свободных блоков! Изначально у нас только один свободный блок, а дальше мы добавляем свободные блоки в бинарное дерево поиска, ключом будет — размер блока. Таким образом, чтобы выделить память нам достаточно найти блок в дереве, у которого размер больше или равен тому, что нам нужен. Это мы спокойно делаем за O(log N), просто спускаясь по дереву вниз. Дальше мы либо режем блок на два, либо полностью отдаем его тому, кто запросил память. Дальше мы удаляем блок из дерева за O(1). И, если надо, вставляем оставшуюся часть блока обратно за O(log N). Для высвобождения нам достаточно вставить блок обратно, и не надо забывать про фрагментацию.
Логично, что использовать простое дерево не надо, надо использовать самобалансирующееся дерево, Red-Black или AVL. Хранить дерево блоков можно в статическом массиве, или же придумать как это сделать по-другому.
Собственно, код:
char * malloc(size_t size) {
if (!size) {
return 0;
}
char * addr = 0;
int i;
for (i = 0; i < allocationAvlTree.size; )
{
int r;
node_t *n;
n = &allocationAvlTree.nodes[i];
/* couldn't find it */
if (!n->key) {
return NULL;
}
r = allocationAvlTree.cmp(n->key, size);
if (r <= 0)
{
//We're lucky today.
//Get memory block header
alloc_t * block = (size_t)n->val - sizeof(alloc_t);
//Set to used
block->status = 1;
//Set size
block->size = size;
alloc_t * next = (size_t)n->val + size;
next->prev_size = size;
next->status = 0;
next->size = n->key - size - 16;
avltree_remove(&allocationAvlTree, n->key, n->val);
if (n->key - size - 16)
avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t));
memset((size_t)block + sizeof(alloc_t), 0, block->size);
block->signature = 0xDEADBEEF;
unlockTaskSwitch();
return (size_t)block + sizeof(alloc_t);
}
else if (r > 0)
i = __child_r(i);
else
assert(0);
}
return 0;
}
void free(void * mem) {
if (!mem)
return;
//Get current alloc
alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t));
if (alloc->signature != 0xDEADBEEF)
return;
alloc->status = 0;
alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size);
if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size)
{
//Merge blocks
if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) {
left->size += sizeof(alloc_t) + alloc->size;
alloc = left;
}
else assert(0);
}
alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size;
if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF)
{
if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t)))
alloc->size += sizeof(alloc_t) + right->size;
else assert(0);
}
avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t));
}
Удачи и этичного хакинга! Любая объективная критика приветствуется, цель статьи не сказать, что это вах какой аллокатор, а просто рассказать о аллокаторе, который будет лучше, чем тупые реализации простых аллокаторов.
Комментарии (31)
a-tk
11.01.2019 10:09Но, как вы понимаете, могут начать образовываться дыры, в которых 2 и более свободных блоков — память дефрагментированна, при высвобождении можно просматривать соседние блоки, и в случае, когда один или два свободны — мержить их в один.
С точностью наоборот: фрагментирована. Дефрагментация — процесс исключения фрагментации.
Бегать только по свободным улучшает скорость в среднем в два раза, но это всё равно линия.
Это точно не машинный перевод?
OldFisher
11.01.2019 10:15+1Аллокаторы лучше затачивать под специфику задачи. Например, аллокатор, выделяющий блоки одного-единственного размера, может работать за O(1) на выделение и освобождение с весьма малым оверхедом на заголовки. Для объектов, существующих хотя бы по большей части по стековому принципу (те, что созданы позже, уничтожаются раньше) и имеющих предсказуемый объём, можно получить амортизированное O(1).
konsoletyper
11.01.2019 14:08+1Аллокатор как часть ОС? А зачем? Обычно ОС предоставляют низкоуровневые вызовы, резервирующие память страницами, вроде sbrk/mmap в POSIX или VirtualAlloc в Windows, а уже поверх них в userspace реализуется что-нибудь вроде malloc. Последний может быть и не нужен, если вы запускаете на своей ОС какую-нибудь Java, где свой аллокатор, который непосредственно в тот же mmap бегает.
Sap_ru
12.01.2019 03:32Windows, «Обычно» это Linux? ;) WIndows имеет системный аллокатор (HeapCreate и HeapAlloc) от чего есть свои плюсы.
Например, с своими кастомным malloc, как прикажете шарить память, выделенную разными библиотеками (линкованными с несовместимыми версиями libc или даже со статическими libc)? Ядро и сервисы всякие не имеют возможности освобождать буфера юзерспейса и память, выделенную друг-другом. А без этого трудно внедрить общесистемный стандарт данных высокого уровня.
Собственно, простая задача — как передавать строки и массивы двоичных данных между библиотеками и программами не думая о бинарной совместимости. В том смысле, что передать передать легко, но кто освобождать буфер будет в тяжёлых случаях, когда вызываются всякие отложенные callback и вы не контролируете момент вызова?
А в Windows, например, можно вполне безопасно обмениваться OLE-совместимыми строками между программами на совершенно разных языках (лишь бы типы данных OLE поддерживались, но это стандарт по Win и его поддерживаются все языки).
Sipidronov
11.01.2019 14:45Константное время аллок/деаллок + довольно низкая фрагментация: TLSF www.gii.upv.es/tlsf
klirichek
11.01.2019 15:54Для какой-нибудь специфической задачи/железа оно может и имеет смысл.
А вот в общем…
Осенью прошлого года подумалось попробовать "тот самый" аллокатор мелких объектов из книжки Александреску. Как раз для них самих (для мелких объектов).
Ок, нашёл либу, отревьювил, адаптировал под современные реалии (тогда же не было ещё move-семантики в плюсах, а нынче почему бы не воспользоваться?) По итогу взлетело, поведение соответствует ожидаемому и вроде всё здорово. Код прямой, как палка, и вроде не содержит никаких явных затыков…
Угумс… Делаем бенч, аллоцируем/освобождаем в цикле с десяток миллионов чанков случайной длины (такой, чтоб именно в алгоритм аллокатора попадало). И ровно то же самое — "стандартным" malloc/free… И тут внезапно(?) оказывается, что "тот самый" аллокатор 10-летней давности даже близко не стоит к штатному из glibc. Разница по скорости вышла чудовищная (чуть ли не в сотню раз). Никакие улучшения/оптимизации ситуацию существенно не улучшили. Потому что "штатный" пилился и улучшался все эти годы; добавлялась многопоточность; оптимизировались алгоритмы и подходы, и по итогу соревноваться с ним стало весьма сложно.
И в итоге было решено оставить затею и, не выпендриваясь, пользоваться "штатными" средствами. Ну, в крайнем случае — jmalloc (благо, он не требует пересборки и легко цепляется через LD_PRELOAD).Videoman
11.01.2019 16:32А будет еще быстрее, когда в глобальный delete размер добавят.
Дело в том, что освобождение и так более сложная операция чем выделение, так еще все усложняется тем, что интерфейс delete повторяет интерфейс free() и при использовании стороннего аллокатора, прежде чем начать что-то удалять, необходимо понят, а какого размера объект указатель на который нам передали? А это отдельная песня, с блокировками, походами по таблицам и т.д.klirichek
11.01.2019 18:53мне почему-то вот тут сразу вспомнилась "знаменитая" книжка "Visual C++ 6.0 для компьютеров и программирования" под авторством некоего Секунова. А запомнилась она по одному пассажу, который я до сих пор помню: Не всегда понятно, когда использовать delete а когда delete[], и это определяется, как правило, методом "научного тыка".
Videoman
11.01.2019 19:37Всё очень просто: для указателя выделенного по new нужно звать delete, а для указателя выделенного по new[] нужно звать delete[].
klirichek
11.01.2019 19:39Да Вы не поняли :)
В ПЕЧАТНОЙ книжке (которая при этом претендует на серьёзный учебник; в то время жёлто-чёрной серии книжек "для чайников" не существовало!) автор предлагает использовать "метод научного тыка"!
rkfg
12.01.2019 18:29Я не поленился и нашёл это место. Книга называется «Самоучитель Visual C++ 6», PDF-версия не распознана,
так что скриншотом:
Videoman
13.01.2019 01:34Это жесть конечно! Особенно радует не соответствие семантики конструктора копирования и оператора «копирования» принимающего не константную ссылку, если его можно так назвать, который на самом деле делает перемещение. Ну хоть не MSDN перепечатали :).
rkfg
13.01.2019 01:41Я даже не вчитывался, это действительно неплохой «сюрприз». Вот интересно, в те годы ещё copy&swap idiom не изобрели, что ли? Потому что она сразу убирает проверку на равенство указателей, убирает дублирование кода и избавляет от ошибок при всех этих операциях.
Eagle_NN
11.01.2019 17:13Поздравляю! Теперь Вы узнали что современные средства языка С++ хотя, во многих случаях, и упрощают читабельность, однако работают не самым быстрым образом по сравнению с «обычной» реализацией (или вообще реализацией на С).
Я не призываю не пользоваться новым, однако стоит понимать, тот оверхед который с ними приходит, и корректно выбирать задачи которые ими решаются.klirichek
11.01.2019 19:08Да там нет особого оверхеда.
Просто специфическая реализация широко используемых библиотек использует разные современные бустеры и фичи современных процессоров, так что даже будучи написанной на С++ (я не про аллокатор прямо сейчас, а в целом) влёгкую окажется намного быстрее "велосипедов" хотя бы за счёт скрупулёзности, выверенности и оптимизации под конкретные архитектуры.
Например: де-ескейпим строчку из json: ходим в цикле по символам; видим обратный слэш — обрабатываем, иначе просто копируем символ их входа на выход (т.е. в конце цикла есть немудрёная строчка
*dest++ = *src++. Что может быть проще?
Ага, заменяем эту строчку на memchr('\') + последующий memmove найденного куска без слэшей — и несмотря на вызовы функций вместо вроде бы линейного кода получаем ускорение раза в полтора (на типовых строках, где экранированных символов около 10%). И всё потому что и memchr и memmove отлично разбираются в архитектурах современных процессоров, а потому умеют делать свою задачу настолько оптимально и быстро, что в профайлере занимают какую-то долю процента.Eagle_NN
12.01.2019 19:09Ну во первых эти функции первые попадают под оптимизацию компилятора. Во вторых они inline. Так что никаких, якобы, вызовов и быть не должно. В третьих они отлично параллелятся на суперскалярных процессорах. Как результат отдельный цикл может не развернуться в инструкции scasb и stosb. А использование memchr и memmove удачно в них преобразуются. Эффективность их будет зависеть от длины строки (точнее от соотношения длины строки и длины буфера данных процессора)
robert_ayrapetyan
11.01.2019 22:25+1>Искал я несложные и адекватные идеи для менеджера и в рунете, и на англоязычных сайтах — всё никак не мог найти никаких хороших статей про адекватный, работающий не за O(N) аллокатор.
Согласен с предыдущими комментами — если вы пишете ОС, то вам нужен не malloc, а аналог sbrk\mmap. Для malloc cоветую покурить jemalloc (https://github.com/jemalloc/jemalloc). Там учтены уже все детские болезни велосипедных аллокаторов (как-то: оптимизация вызовов sbrk\mmap, локов для многопоточных приложений, фрагментации, кешей, специфика архитектуры процев, разные логики на большие\малые выделения и т.п). Без глубокого закапывания в эти детали лезть в какую-либо оптимизацию вообще не стоит, O(N) и так сойдет.
Siemargl
Недавно реализовывал. Выяснилось, что на реальных задачах фрагментация такая, что без объединения соседних свободных, менеджер практически неработоспособен.
Так вот это объединение — весьма дорогая операция. Я сделал линейным поиском примыкающих сверху и снизу от освобождаемого. Но может, есть идеи получше?
Кстати, описание неточное — аллокатор потому и watermark, что в начала каждого блока и стоит ватермарка — занят он или свободен. К сожалению, ватермарки не помогли с объединением, потому что иногда сверху, например — не «наша» память.
Malligan0
Siemargl
делает. потому что ватермарка — читаемый текст. подроднее и зачем так см на OSDev Wiki
mk2
Если вас не смущает оверхед, то выделяем память кусками степени 2. Если у нас нет сейчас достаточно маленького куска, делим один из имеющихся на половины. Соответственно если обе половины какого-то куска свободны, мы их объединяем обратно.
Это даже как-то называется, но я не помню как)
alexxisr
У Кнута, помнится, был еще вариант с числами Фибоначи вместо степеней двойки. При этом вроде как память более плотно используется, и сложение/вычитание вместо умножения/деления (хотя в наше время это уже не важно)
Videoman
Buddy allocator. По сути, это и есть двоичное дерево, которое не требует никакой балансировки. Автор его и «изобрел», но сильно переусложнив саму структуру. Похожий механизм, насколько я знаю, как раз и используется ядром для первичного распределения страниц, так как идеально подходит для аллокации выровненных и кратных степени двойки кусков памяти.
DrZlodberg
А почему дорогая? Достаточно совместить с первым методом (т.е. хранить ссылки на пред/след). Правда придётся ещё хранить ссылку на ноду каждого, чтобы его не искать в дереве.