Если честно, это одна из самых жестоких статей, что я читал за последнее время: тут много про смерть в молодом возрасте, про гонения из одной области памяти в другую и про ожесточённую борьбу за производительность. В общем, добро пожаловать под кат — там перевод отличной статьи Питера Маршалла о том, как сегодня работает сборка мусора в V8.



За последние несколько лет подход к сборке мусора в V8 сильно изменился. В рамках проекта Orinoco он прошёл путь от последовательного подхода stop-the-world к параллельному и конкурентному подходам с инкрементальным фолбэком.

Примечание: если вам больше нравится смотреть доклад, чем читать статью, это можно сделать здесь. Если же нет, то читайте дальше.

У любого сборщика мусора есть набор задач, которые нужно периодически выполнять:

1. Находить живые/мёртвые объекты в памяти.
   
2. Переиспользовать память, занимаемую мёртвыми объектами.
   
3. Уплотнять/дефрагментировать память (опционально).
   

Эти задачи можно выполнять последовательно, а можно — чередовать. Самый простой способ — это остановить выполнение JavaScript и сделать всё последовательно в основном потоке. Однако это может привести к задержкам, о которых мы говорили в предыдущих постах, а также к снижению производительности программы в целом.

Основной GC (full mark-compact)

Основной GC собирает мусор из всей кучи.

Чистка мусора происходит в три этапа: маркировка, утилизация и уплотнение

Маркировка

Определение того, из-под каких объектов можно освободить память, — обязательная часть работы сборщика мусора. Он считает объект живым на основе информации о его достижимости. Это значит, что любой объект, на который есть ссылки из текущей среды исполнения, должен быть сохранён в памяти, а все недоступные объекты могут быть собраны GC.

Маркировка — это процесс поиска достижимых объектов. У GC есть набор указателей, с которого он начинает искать, — так называемое корневое множество (root set). Этот набор включает в себя объекты из текущего стека выполнения и global объекта. Начав с этого множества, GC следует по каждому указателю на JavaScript-объект и помечает каждый как достижимый, после чего переходит к указателям из объектов на другие объекты и повторяет этот процесс рекурсивно, пока каждый достижимый объект не будет промаркирован.

Утилизация

Утилизация — это процесс, в ходе которого области памяти, оставшиеся от мёртвых объектов, заносятся в список, называемый free-list. Как только процесс маркировки завершается, GC находит такие области и добавляет их в подходящий список. Free-list’ы отличаются друг от друга тем, какого размера области памяти в них хранятся, что позволяет быстрее находить нужную. В последующем, когда мы захотим выделить память, мы посмотрим в один из списков и найдём участок подходящего размера.

Уплотнение

Также основной GC иногда принимает решения об очистке/уплотнении некоторых страниц памяти, исходя из собственных эвристических оценок, основанных на степени фрагментации страницы. Можно думать об уплотнении как об аналоге дефрагментации жёсткого диска на старых ПК. Мы копируем выжившие объекты на другие страницы, которые ещё не подвергались уплотнению (тут как раз используется free-list). Таким образом мы можем переиспользовать маленькие разбросанные участки памяти, оставшиеся от мёртвых объектов.

Один из недостатков GC, который копирует выжившие объекты, заключается в том, что, когда создаётся много долгоживущих объектов, приходится платить высокую цену за их копирование. Именно по этой причине уплотнению подвергаются только некоторые сильно фрагментированные страницы памяти, в отношении остальных же просто проводится утилизация, которая не требует копирования выживших объектов.

Устройство поколений памяти

Куча в V8 разбита на области, называемые поколениями. Есть молодое поколение (которое в свою очередь подразделяется на поколение-«ясли» и «промежуточное» поколение) и старые поколения. Создаваемые объекты помещаются в «ясли». Впоследствии, если они переживают следующую сборку мусора, они остаются в молодом поколении, но переходят в разряд «промежуточных». Если они выживают и после следующей сборки, то помещаются в старшее поколение.

Куча V8 разбита на поколения. Объекты перемещаются из младшего в старшее поколение, если переживают сборку мусора

В сборке мусора есть важный термин «гипотеза поколений». Если по-простому, то это значит, что большинство объектов «умирают молодыми». Другими словами, большинство объектов создаются и почти сразу умирают с точки зрения GC. И это утверждение справедливо не только для JavaScript, но и для большинства динамических языков программирования.

Организация кучи в V8 опирается на вышеуказанную гипотезу. Например, на первый взгляд может показаться нелогичным, что GC занимается уплотнением/перемещением объектов, которые пережили сборку мусора, ведь копирование объектов — довольно дорогая операция для того, чтобы проводить её во время сборки мусора. Но, исходя из гипотезы поколений, мы знаем, что очень немного объектов переживут эту процедуру. Так что, если переместить только выжившие объекты, всё, что не было перемещено, может автоматически считаться мусором. Это означает, что цена, которую мы платим за копирование, пропорциональна количеству выживших объектов, а не всех созданных.

Вспомогательный GC (scavenger)

На самом деле в V8 два сборщика мусора. Основной (mark-compact) довольно эффективно собирает мусор со всей кучи, вспомогательный же — собирает мусор только в молодой памяти, потому что гипотеза поколений говорит нам, что основные усилия по сборке мусора нужно направить именно туда.

Принцип работы вспомогательного GC таков, что выжившие объекты всегда перемещаются на новую страницу памяти. В V8 молодая память разделяется на две половины. Одна всегда свободна для того, чтобы была возможность перемещать в неё выжившие объекты, и во время сборки эта изначально пустая область называется To-space. Область же, из которой происходит копирование, называется From-space. В худшем случае каждый объект может выжить, и тогда придётся копировать их все.

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

При копировании объектов из From-space в To-space все выжившие объекты размещаются в непрерывном участке памяти. Таким образом удаётся избавиться от фрагментации — промежутков памяти, оставшихся от мёртвых объектов. После окончания переноса To-space становится From-space, и наоборот. Как только GC завершит свою работу, память под новые объекты будет выделяться начиная с первого свободного адреса во From-space.

Scavenger переносит выжившие объекты на новую страницу памяти

Если использовать только эту стратегию и не перемещать объекты из молодой памяти, то память довольно быстро закончится. Поэтому объекты, которые пережили две сборки мусора, перемещаются в старую память.

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

Scavenger переносит «промежуточные» объекты в старую память, а объекты из «ясель» — на новую страницу

Таким образом, сборка мусора в молодой памяти состоит из трёх шагов: маркировка объектов, их копирование, обновление указателей.

Orinoco

Большинство перечисленных алгоритмов описываются в различных источниках и часто применяются в средах исполнения с поддержкой автоматической сборки мусора. Но GC в V8 прошёл долгий путь, прежде чем стать по-настоящему современным инструментом. Одни из значимых метрик, описывающих эффективность его работы, — это то, как часто и как долго основной поток стоит на паузе, пока сборщик мусора выполняет свои функции. Для классических stop-the-world сборщиков, это время накладывает свой отпечаток на опыт использования страницы за счёт задержек, некачественного рендеринга и увеличения времени отклика.

Логотип Orinoco GC V8

Orinoco — это кодовое название GC с использованием современных техник параллельной, инкрементальной и конкурентной сборки мусора. Есть некоторые термины, имеющие специфическое значение в контексте GC, так что давайте сначала приведём их определения.

Параллельность

Параллельность — это когда главный и вспомогательные потоки делают примерно одинаковый объём работы в единицу времени. Это по-прежнему подход stop-the-world, но длительность паузы в этом случае делится на количество потоков, участвующих в работе (за вычетом расходов на синхронизацию).

Это самая простая из трёх техник. Куча не изменяется, поскольку JavaScript не исполняется, так что потокам достаточно поддерживать синхронизацию доступа к объектам.

Главный и вспомогательные потоки работают над одной задачей одновременно

Инкрементальность

Инкрементальность — это когда основной поток делает небольшой объём работы с перерывами. Вместо полной сборки мусора делаются небольшие задачи по частичной сборке.

Это более сложная задача, так как между инкрементальными сборками происходит выполнение JavaScript, что означает, что состояние кучи изменяется, что в свою очередь может инвалидировать часть работы, сделанной в предыдущей итерации.

Как видно из диаграммы, такой подход не уменьшает суммарное количество работы (а, как правило, даже увеличивает его), но он распределяет эту работу во времени. Поэтому это хороший способ решения одной из главных задач — уменьшения времени отклика главного потока.
Позволяя JavaScript выполняться с небольшими перерывами на сборку мусора, приложение может продолжать быть отзывчивым: реагировать на пользовательский ввод и обновлять анимации.

Небольшие участки работы GC в основном потоке

Конкурентность

Конкурентность — это когда основной поток непрерывно выполняет JavaScript, а вспомогательные потоки занимаются сборкой мусора в фоновом режиме. Это самая сложная из трёх техник: куча может измениться в любой момент, инвалидируя работу, сделанную GC раньше.

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

Сборка происходит полностью в фоновом режиме, основной поток в это время может выполнять JavaScript

Состояние GC в V8

Scavenging

V8 распределяет работу по сборке мусора между вспомогательными потоками в молодой памяти (scavenging). Каждый поток получает набор указателей, следуя по которым, перемещает все живые объекты в To-space.

Во время перемещения объектов в To-space потокам необходимо синхронизироваться через атомарные read/write/compare and swap операции, чтобы избежать ситуации, когда, к примеру, другой поток обнаружил этот же объект, но следуя по другому пути, и тоже пытается переместить его.

Поток, который переместил объект в To-space, потом возвращается и оставляет forwarding указатель, чтобы другие потоки, которые найдут этот объект, могли проследовать по верному адресу. Для быстрого и не требующего синхронизации выделения памяти для выживших объектов потоки используют thread local буферы.

Параллельная сборка распределяет работу между несколькими вспомогательными потоками и основным потоком

Основной GC

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

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


Основной GC использует конкурентную маркировку, утилизацию и параллельное уплотнение и обновление указателей

По окончании конкурентной маркировки основной поток осуществляет быстрый шаг окончания маркировки. Во время этого выполнение JavaScript в основном потоке приостанавливается.

Корневое множество сканируется ещё раз для того, чтобы убедиться, что все живые объекты помечены, а затем в несколько потоков начинаются уплотнение памяти и обновление указателей.
Не все страницы в старой памяти уплотняются — те, что нет, будут просканированы на освободившиеся участки памяти (sweeping) для занесения их в списки (free-lists).

Во время этой паузы стартуют sweeping задачи, которые работают конкурентно с задачами по уплотнению памяти и основным потоком и могут продолжаться, даже когда в основном потоке выполняется JavaScript.

Idle-time GC

Разработчики JavaScript не имеют доступа к GC — он является деталью реализации окружения. И хотя JS-код не может вызвать GC напрямую, V8 предоставляет такой доступ среде, встраивающей движок.

GC может присылать задачи (idle tasks), которые можно выполнить «в свободное время» и которые представляют собой части работы, которую в любом случае пришлось бы сделать. Среда вроде Chrome, куда встраивается движок, может иметь своё представление о том, что считать свободным временем. К примеру, в Chrome при частоте 60 кадров в секунду у браузера есть примерно 16,6 мс на отрисовку кадра анимации.

В случае если работа по анимированию завершена раньше, в свободное время, перед наступлением следующего кадра, Chrome может выполнить некоторые из задач, полученных от GC.

GC использует свободное время основного потока, чтобы сделать предварительную очистку

Узнать подробности можно из нашей публикации об Idle-time GC.

Итоги

GC в V8 проделал большой путь с момента своего появления. Добавление в него параллельных, инкрементальных и конкурентных техник заняло несколько лет, но окупилось, позволив делать большую часть работы в фоновом режиме.

Значительно улучшилось всё, что связано с паузами основного потока, временем отклика и загрузки страницы, что позволяет делать анимации, скроллинг и взаимодействие с пользователем на странице намного более гладкими. Параллельный сборщик позволил уменьшить общую продолжительность обработки молодой памяти на 20—50% в зависимости от нагрузки.

Idle-time GC позволяет уменьшить размер использованной кучи для Gmail на 45%. Конкурентная маркировка и утилизация (sweeping) позволяют сократить длительность GC-пауз в тяжелых WebGL-играх до 50%.

Тем не менее работа ещё не окончена. Сокращение пауз  остаётся важной задачей для упрощения жизни пользователей веба, и мы ищем возможность применения более продвинутых техник для достижения цели.

Ко всему прочему Blink (рендерер в Chrome) также снабжён сборщиком (Oilpan), и мы работаем над улучшением взаимодействия между двумя GC, а также над тем, чтобы использовать техники Orinoco в Oilpan.

Большинству разработчиков JavaScript не нужно думать о том, как работает GC, однако некоторое представление об этом может помочь принимать оптимальные решения в части использования памяти и паттернов программирования. К примеру, учитывая структуру кучи V8, основанную на поколениях, маложивущие объекты на самом деле довольно дёшево обходятся с точки зрения GC, так как мы платим в основном за выжившие объекты. И такого рода паттерны свойственны не только JavaScript, но и многим языкам с поддержкой сборки мусора.