Andersen

Как организовать сборку мусора на вебе и как работает Orinoco GC

Jul 08, 2020
Blog

Чистка памяти — процесс, обязательный для любых приложениях, в том числе, написанных на JS. Если игнорировать этот момент, память заполнится объектами (преимущественно “мертвыми”), и в какой-то момент для новых данных просто не найдется места. В этой статье мы разберем базовые принципы очистки памяти на JS, а также рассмотрим несколько алгоритмов сбора мусора и определим, какой из них наиболее эффективен.

Что такое мусор

Мусор — это любой объект, к которому невозможно пройти по ссылке от “корня”. К мусору относятся все “мертвые объекты”, которые утратили связь с корневым. 

При этом “мертвые” объекты часто могут быть перелинкованы друг с другом, и образовывать внушительных размеров цепи. Однако это все равно не делает их “живыми”, и именно поэтому такой подход к сбору мусора, как подсчет ссылок, не работает. А какие, в таком случае, работают? Разберем по-порядку.

Подходы к сборке мусора

Рассмотрим несколько подходов, начиная с самых простых и быстрых, и заканчивая наиболее эффективными, но медленными.

Mark and Sweep

Самый простой алгоритм поиска и удаления мусора. Работает только тогда, когда мусор есть, если память наполнена только живыми объектами, Mark and Sweep ничего не делает.

Основной минус Mark and Sweep в том, что он фрагментирует память. В итоге он может очистить много места, но новый крупный объект все равно не сможет разместиться в оперативной памяти.

Mark-Sweep-Compact

В алгоритме Mark-Sweep-Compact добавляется как раз та самая необходимая функция дефрагментации. После очистки он смещает все оставшиеся объекты и создает единое пространство свободной памяти.

С точки зрения результата Mark-Sweep-Compact оптимален. Однако сам процесс смещения объектов довольно ресурсозатратный, к тому же Mark-Sweep-Compact нужно проходить по памяти 2-3 раза, что занимает много лишнего времени.

SemiSpace

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

Этот алгоритм проще и быстрее Mark-Sweep-Compact, однако требует выделения дополнительного места для копирования живых объектов. К тому же сам процесс копирования также ресурсозатратен.

Слабая гипотеза о поколениях

Согласно теории поколений, объекты “умирают молодыми” гораздо чаще, чем “старыми”. Недавно созданный объект станет мусором с гораздо большей вероятностью. Именно поэтому сборщику мусора рационально проверять такие объекты чаще.

Рассмотрим подход с разделением на поколения на примере алгоритма сбора мусора для языка Java. Она работает следующим образом:

  1. Вся память делится на молодое и старое поколение.
  2. Молодое поколение делится на слоты Eden, Survivor Space 1 и 2 (S0 и S1).
  3. Все новые объекты попадают в Eden.
  4. При каждой проверке алгоритм перемещает живые объекты из Eden и одного из S-слотов в другой S-слот, затем полностью чистит проверенные слоты.
  5. C-слоты алгоритм проверяет поочередно: если во время предыдущей проверки проверялись слоты Eden и S0, а живые объекты копировались в S1, во время следующей проверки проверяться будут уже Eden и S1, а живые объекты будут копироваться в S0.
  6. Объекты, которые смогут прожить достаточно долго, перемещаются в старшее поколение. За это время они успевают пройти множество проверок и с большой долей вероятности и дальше будут оставаться живыми.

Похожий принцип применяется при работе сборщика мусора Orinoco GC в движке V8 JS

Orinoco GC

Orinoco GC также сегментирует память и перемещает объекты в зависимости от их возраста, но у этого алгоритма есть свои нюансы:

  1. Память делится на молодую и старую однако молодая память включает всего два слота: Nursery и Intermediate. 
  2. Проверка памяти осуществляется сразу в несколько потоков. При перемещении живого объекта из Nursery в Intermediate поток оставляет forward-указатель. Это сделано для того, чтобы другой поток, который пришел к этому же объекту, но по другой цепочке ссылок, не попытался переместить его повторно.

Алгоритм Orinoco GC работает следующим образом.

  1. Все новые объекты попадают в Nursery, затем, после проверки Scavenger, выжившие перемещаются в Intermediate, остальные удаляются.
  2. После уплотнения памяти и прохождения следующей проверки Scavenger живые объекты перемещаются в старую память.
  3. Старая память проверяется реже, проверку осуществляет основной GC.

В Orinoco работает два сборщика мусора: вспомогательный (Scavenger), который проверяет молодую память, и основной, который проверяет весь массив. Фаза Compact опциональна, и это прерогатива основного сборщика. Так как перемещение объектов остается ресурсозатратным предприятием, для того, чтобы минимизировать такие действия, в Orinoco используются фрилисты. Это списки свободного пространства в памяти, которые позволяют определить новый объект на подходящее ему свободное место. В случае, когда память слишком фрагментирована, и для объекта не находится подходящего места, алгоритм переходит в фазу Compact.

JS-разработчики не имеют доступа к GC, он является деталью реализации. Хотя JS не может вызвать коллектор напрямую, V8 предоставляет доступ среде, в которую движок встраивается. GC может выставлять задачи, которые среда выполняет в свободное время. 

Previous articleNext article