Отвечая на вопрос, хочу поделиться одним хорошо себя зарекомендовавшим решением. Извиняюсь что для комментария «много букв», ибо только что хотел написать это как топик, но увы, у меня кармы пока нема…
Представим что у нас есть очень-очень хитрая структура данных, элементами которой являются куча (возможно даже разнородных) объектов содержащие кучу ссылок на другие объекты этой структуры. Например, хитрый граф с циклами и прочими радостями. Само собой, наша реальная программа кроме этого хитрого графа, работает еще с кучей прочих объектов, в том числе, например, другие, не менее хитрые графы, на которые тоже нужна память, и вообще-то немало.
Вроде бы «задача для школьников» написал структуры данных со всеми полями для вершин и ребер графа, а дальше вроде все просто, «все как по учебнику» — выделяй для них память из кучи с помощью malloc/new и проставляй указатели.
Проблема возникает когда мы, поработали с данным графом и он нам больше не нужен. Кажущаяся простая задача «взять и освободить память для всех объектов», т.е. для каждого объекта вызвать соответствующий free/delete причем один один и только один раз, на деле оказывается не просто сложной а в общем случае
NP-сложной. Т.е. вся предыдущая работа работа с этим хитрым графом может показаться «цветочками» по сравнению с попыткой найти в каком же порядке обойти элементы чтобы никого не забыть (ибо иначе утечка памяти) и вызвать освобождение каждого элемента только один раз (ибо при двойном освобождении мы нарушим логику других потоков нашей программы).
По сравнению с внезапно свалившейся на нас проблемой идея использовать разные хитрые алгоритмы автоматического управления памятью, подсчета ссылок, сборки мусора и т.д. уже не кажутся для нас настолько уж бредовой идеей. Только в тупую прикрутить какую-нибудь библиотеку сборки мусора тоже оказыватся не всегда легко удается, ведь не все алгоритмы сбора мусора и подсчета ссылок корректно работают с циклическими ссылками.
Однако давайте посмотрим в корень проблемы. Проблему сложности поэлементного освобождения как таковую порождает само поэлементное выделение обьектов из динамической памяти (кучи). Кстати, это в добавок ко всем остальным проблемам динамической памяти таким как фрагментация, замедление операций выделения/освобождения когда динамическая память представляет собой кашу из сотен тысяч фрагментов разного размера вперемешку с свободными элементами тоже разного размера (а именно такую адскую кашу представляет собой динамическая память у любителей STL).
Решение может быть простым и изящным — аллокатор памяти без поэлементного освобождения. Звучит сложно, но реализация проста.
Основой нашего аллокатора памяти служит чанк. Размер чанка может быть любым, главное чтобы он был больше максимального размера объекта. Идеальный вариант- зная (приблизительно) сколько нам нужно мы выбираем размер чанка. Если структура нашего графа заняла больше — ничего страшного, выделим еще один чанк.
Сам чанк имеет следующую структуру:
struct _alloc_pool_mem_chunk{ // чанк пула-аллокатора без поэлементного освобождения
size_t size; // размер данных чанка
size_t curr; // текущее заполнение чанка
struct _alloc_pool_mem_chunk*next; // указатель на следующий чанк нашего пула
uint8_t data[0]; // данные чанка
};
Выделение памяти из такого чанка элементарно:
static void *memchunk_alloc_from_chunk(struct _alloc_pool_mem_chunk*ch,size_t s){
if(!ch||!s){return 0;} // простая проверка
if( (ch->size-ch->curr) < s){return 0;} // у нас в чанке свободно (ch->size-ch->curr) байт
void *rv=&ch->data[ch->curr];
ch->curr+=s; // сдвигаем на s байт
return rv;
}
Если в чанке нет места для объекта, мы просто добавляем еще онин чанк:
static struct _alloc_pool_mem_chunk *memchunk_add_chunk(struct _alloc_pool_mem_chunk **chp,size_t chunk_size){
struct _alloc_pool_mem_chunk*ch=malloc(sizeof(struct _alloc_pool_mem_chunk)+chunk_size); // выделяем чанк
if(!ch){return 0;}
ch->curr=0;
ch->size=chunk_size;
ch->next=*chp; // сцепляем чанки в связный список
*chp=ср;
return ch;
}
Вся процедура выделения памяти из такого аллокатора в простейшем виде:
void *memchunk_alloc(struct _alloc_pool_mem_chunk **chp,size_t s,size_t chunk_size){
void *rv;
static struct _alloc_pool_mem_chunk *ch=*chp;
if((rv=memchunk_alloc_from_chunk(ch,s))){return rv;} // выделяем из текущего чанка
if(!(ch=memchunk_add_chunk(chp,chunk_size))){return 0;} // не удалось добавить чанк-облом
rv=memchunk_alloc_from_chunk(ch,s); // выделаем из нового чанка
return rv;
}
Функция освобождения всего пула-просто обходим все чанки:
void memchunk_free_all(struct _alloc_pool_mem_chunk **chp){
struct _alloc_pool_mem_chunk *ch=*chp;
while(ch){
struct _alloc_pool_mem_chunk *chn=ch->next;
free(ch);
ch=chn;
}
}
Достоинства:
- Чрезвычайная простота реализации. Даже школьник способен с первого раза за несколько минут написать безошибочно такой аллокатор. Кстати код выше я не копипастил а просто набрал по памяти (из ошибок могут быть очепятки).
- Низкий overhead. всего 12/24 байта (x86/x86_64) на чанк.
- Не фрагментирует память. Существенное достоинство, особенно когда элементов сотни тысяч.
- Выделение элемента работает быстрее, в разы быстрее чем malloc/new. (Выделение памяти для элемента из чанка 3 строки). Освобождение элемента — вообще nop!
- Если нам вдруг захочется threadsafe — мы легко получим всего лишь заменив запись ch->curr+=s на cmpxchg и добавив какой-нибудь легковесный примитив типа spinlockа на добавление чанка.
- У нас свой быстрый и легковесный garbage collector с коммандой «освободи все». Пройти по (NB: небольшому) списку чанков — это не считать ссылки в миллионах объектов.
- Да, контроль занятой памяти нашей хитрой структурой. Мы всегда можем быстро сказать, что например этот граф занимает 3.5Mb, просто пробежавшись по чанкам.
- Проверенно лично мною на десятке highload-проектов.
Недостатки:
- А они бывают только в тех случаях, если этот аллокатор использовать для непредусмотренных целей:)
P.S.: Желаю всем хабраюзерам приятных экспериментов.
Средний
Средний
