Создание Garbage Collector-а

Народ, а кто-нибудь в Garbage Collection смыслит? Я вот слушаю сейчас автора Phantom OS, тот рассуждает о создании быстрого GC. Самое шустрое — ref-counting, но не работает с циклическими ссылками. И тут он возвращается к обычному GC-пауку. И тут я подумал… Цитирую свой комментарий:

У меня в голове смутно появилась мысль, что можно использовать идею рефкаунтов для циклов. Что я имею в виду. Я имею в виду, что в менеджере объектов к каждому объекту надо привязывать историю создания и ссылок. То есть — объект A порождает объект B, порождает объекты C, тот ссылается на A… И тут мы получаем у последнего историю: A-B-C-A и сразу видим цикл! Если на объект есть множество ссылок, их истории суммируются в массив, проверяются по очереди.

Я правильно понимаю, что это будет очень дешево и будет работать?
  • Вопрос задан
  • 2839 просмотров
Пригласить эксперта
Ответы на вопрос 7
@lesha_penguin
Отвечая на вопрос, хочу поделиться одним хорошо себя зарекомендовавшим решением. Извиняюсь что для комментария «много букв», ибо только что хотел написать это как топик, но увы, у меня кармы пока нема…

Представим что у нас есть очень-очень хитрая структура данных, элементами которой являются куча (возможно даже разнородных) объектов содержащие кучу ссылок на другие объекты этой структуры. Например, хитрый граф с циклами и прочими радостями. Само собой, наша реальная программа кроме этого хитрого графа, работает еще с кучей прочих объектов, в том числе, например, другие, не менее хитрые графы, на которые тоже нужна память, и вообще-то немало.

Вроде бы «задача для школьников» написал структуры данных со всеми полями для вершин и ребер графа, а дальше вроде все просто, «все как по учебнику» — выделяй для них память из кучи с помощью 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.: Желаю всем хабраюзерам приятных экспериментов.
Ответ написан
@dborovikov
На сколько я знаю, основная проблема рефкаунтинга в том, что бы считать ссылки атомарно. Если доступ к объекту осуществляется из разных тредов, то придется синхронизироваться на счетчике, а это станет узким местом. Рефкаунтинг видимо хорошо работает только в однопоточном окружении.
Ответ написан
@pennanth
Проблема как раз не в таких простых циклах, а ветвящихся.

К примеру, 20 A(i) объектов порождают свои 20 B(j) объектов, а те — порождают C(k) объекты — и B(j).C(k) ссылается на A(k+j+i % 20). Будет ли тут циклическая связь?

Т.е. нужно вести или прямой граф A(i) -> B(j) -> C(k), но там проблема в том, что A не узнает о C без специальной магии, или обратный C(k) -> B(j) -> A(i), и тут возникает проблема — как найти все C, на которые ссылается данный A(i). И, разумеется, для объекта с 3 byte полями вести такие списки крайне накладно — две ссылки на родительские объекты (каждая — в 64 бита) уже окажутся больше по объему памяти для такого объекта (с учетом выравнивания).

Есть, конечно, эффективные имплементации деревьев и хэш-таблиц (и других похожих структур), но для управления кусочками памяти по 16 байт вся эта мощь, как из гаубицы по колибри.
Ответ написан
shadowjack
@shadowjack
Хм-м, ну вот например в Perl собиратель мусора, насколько я понимаю, работает по принципу ref-counter'а. Если нужно сделать циклическую структуру, то для этого есть функция Scalar::Util::weaken, которая уменьшит значение счётчика и память нормально освободится.
Я к тому, что никакой особой чёрной магии при использовании ref-counter'а с циклическими структурами нет. 8)
Ответ написан
Amper
@Amper
Например, в ocaml «Stop&Copy» и «Mark&Sweep» вполне справляются с циклическими ссылками и неатомарностью и при этом ocaml'овский GC очень шустро работает.
Ответ написан
@diostm
В книге Thinking in Java очень хорошо расписано, что к чему про работу Garbage Collector'a в Java.
Может навести на дальнейшии рассуждения, отличные от «ref-counting».
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
23 мая 2019, в 18:18
600 руб./в час
23 мая 2019, в 18:11
800 руб./в час
23 мая 2019, в 16:17
500 руб./в час