Мусорный разговор: сборщик мусора Orinoco
За последние годы сборщик мусора (GC) в V8 сильно изменился. Проект Orinoco преобразовал последовательный сборщик мусора с полной остановкой мира в в основном параллельный и конкурентный сборщик с плановой обратной связью.
Примечание: Если вы предпочитаете смотреть презентацию вместо чтения статьи, то наслаждайтесь видео ниже! Если нет, пропустите видео и продолжайте читать.
Любой сборщик мусора должен периодически выполнять несколько основных задач:
- Определить живые/мертвые объекты
- Освободить или повторно использовать память, занятую мертвыми объектами
- Компактировать/дефрагментировать память (опционально)
Эти задачи можно выполнить последовательно или чередовать произвольным образом. Простой подход — остановить выполнение JavaScript и выполнить каждую из этих задач последовательно на основном потоке. Это может вызывать заикание и проблемы с задержкой на основном потоке, о которых мы говорили в предыдущих сообщениях в блоге, а также снижать производительность программы.
Основной сбор мусора (Полная маркировка-компактизация)
Основной сбор мусора собирает мусор со всей кучи.
Маркировка
Выявление объектов, которые можно собрать, является важной частью сборки мусора. Сборщики мусора делают это, используя достижимость в качестве прокси для «живости». Это означает, что любой объект, который в данный момент доступен в рантайме, должен быть сохранен, а любой недоступный объект может быть собран.
Маркировка — это процесс, в ходе которого находятся доступные объекты. GC начинает с набора известных указателей объектов, называемых корневым набором. Это включает стек выполнения и глобальный объект. Затем он следует за каждым указателем на объект JavaScript и помечает этот объект как достижимый. GC проходит по каждому указателю в этом объекте и продолжает этот процесс рекурсивно, пока не будут найдены и отмечены все объекты, которые доступны в рантайме.
Очистка
Очистка — это процесс, при котором пробелы в памяти, оставленные мертвыми объектами, добавляются в структуру данных, называемую списком свободных блоков (free-list). После завершения маркировки GC находит непрерывные пробелы, оставленные недоступными объектами, и добавляет их в соответствующий список свободных блоков. Списки свободных блоков разделены по размеру блока памяти для быстрого поиска. В будущем, когда нам нужно выделить память, мы просто обращаемся к списку свободных блоков и находим соответствующий блок памяти.
Компактизация
Основной GC также выбирает определенные страницы для эвакуации/компактизации на основе эвристики фрагментации. Вы можете представить компактизацию как дефрагментацию жесткого диска на старом ПК. Мы копируем оставшиеся объекты в другие страницы, которые в данный момент не компактизируются (используя список свободных блоков для этой страницы). Таким образом, мы можем использовать маленькие и разбросанные пробелы в памяти, оставленные мертвыми объектами.
Одна из потенциальных слабостей сборщика мусора, который копирует оставшиеся объекты, заключается в том, что, когда мы выделяем много долгоживущих объектов, мы платим высокую цену за их копирование. Именно поэтому мы выбираем для компактизации только некоторые сильно фрагментированные страницы и просто выполняем очистку на остальных, что не требует копирования оставшихся объектов.
Поколенческая структура
Куча в V8 разделена на различные области, называемые поколениями. Существует молодое поколение (дополнительно разделенное на «ясли» и «промежуточные» под-поколения) и старшее поколение. Объекты сначала размещаются в ясли. Если они переживают следующий GC, они остаются в молодом поколении, но их считают «промежуточными». Если они переживают еще один GC, они перемещаются в старшее поколение.
В сборке мусора существует важный термин: «Поколенческая гипотеза». Это в основном утверждает, что большинство объектов умирает молодыми. Другими словами, большинство объектов выделяется и затем почти сразу становится недоступным с точки зрения GC. Это справедливо не только для V8 или JavaScript, но и для большинства динамических языков.
Генеративное размещение кучи V8 разработано для использования этого факта о времени жизни объектов. Сборщик мусора является компактизационным/перемещающим, что означает, что он копирует объекты, которые переживают сбор мусора. Это кажется контринтуитивным: копирование объектов дорого обходится при сборке мусора. Но мы знаем, что согласно гипотезе поколений, только очень небольшой процент объектов действительно переживает сбор мусора. Перемещая только те объекты, которые переживают сборку, каждое другое выделение становится 'неявным' мусором. Это значит, что мы платим стоимость (за копирование), пропорциональную количеству оставшихся объектов, а не количеству выделений.
Незначительный GC (Scavenger)
В V8 есть два сборщика мусора. Основной GC (Mark-Compact) собирает мусор из всей кучи. Незначительный GC (Scavenger) собирает мусор в молодом поколении. Основной GC эффективен в сборке мусора из всей кучи, но гипотеза поколений говорит нам о том, что недавно выделенные объекты с большой вероятностью нуждаются в сборке мусора.
В Scavenger, который собирает только в молодом поколении, пережившие объекты всегда эвакуируются на новую страницу. V8 использует ‘половинное пространство’ для молодого поколения. Это значит, что половина общего пространства всегда остаётся пустой, чтобы позволить выполнить этап эвакуации. Во время очистки это первоначально пустое пространство называется ‘To-Space’. Пространство, из которого мы копируем, называется ‘From-Space’. В худшем случае каждый объект может пережить очистку, и нам придётся копировать каждый объект.
Для очистки у нас есть дополнительный набор корней, который представляет собой ссылки от старого к новому пространству. Это указатели в старом пространстве, которые ссылаются на объекты в молодом поколении. Вместо того чтобы отслеживать весь граф кучи при каждой очистке, мы используем барьеры записи, чтобы поддерживать список ссылок от старого к новому. В сочетании со стеком и глобальными переменными мы знаем каждую ссылку в молодом поколении без необходимости отслеживать всё старое поколение.
Этап эвакуации перемещает все пережившие объекты в непрерывный кусок памяти (в пределах страницы). Это имеет преимущество полного устранения фрагментации - пробелов, оставленных мёртвыми объектами. Затем мы изменяем местами два пространства, то есть To-Space становится From-Space и наоборот. После завершения GC новые выделения происходят по следующему свободному адресу в From-Space.
Мы быстро исчерпываем пространство в молодом поколении только с этой стратегией. Объекты, которые переживают вторую сборку GC, эвакуируются в старое поколение, а не в To-Space.
Последний этап очистки — обновление указателей, которые ссылаются на оригинальные объекты, которые были перемещены. Каждый скопированный объект оставляет адрес пересылки, который используется для обновления оригинального указателя, чтобы он указывал на новое местоположение.
При очистке мы фактически выполняем три шага - маркировку, эвакуацию и обновление указателей - все в переплетённом виде, а не в отдельных фазах.
Orinoco
Большинство этих алгоритмов и оптимизаций являются общими в литературе о сборке мусора и могут быть найдены во многих языках с сборкой мусора. Но современные технологии сборки мусора прошли долгий путь. Один из важных показателей для измерения времени, затраченного на сборку мусора, — это количество времени, которое основной поток проводит в состоянии паузы, пока выполняется GC. Для традиционных сборщиков мусора уровня ‘остановить мир’ это время может действительно складываться, и время, затраченное на GC, непосредственно ухудшает пользовательский опыт в виде рывков страниц и плохого рендеринга и задержки.
Orinoco — кодовое название проекта GC, использующего новейшие и лучшие параллельные, инкрементные и конкурентные техники сборки мусора для освобождения основного потока. Здесь есть некоторые термины, которые имеют конкретное значение в контексте GC, и стоит их подробно определить.
Параллельный
Параллельный — это когда основной поток и вспомогательные потоки выполняют примерно одинаковое количество работы одновременно. Это всё ещё подход «остановить мир», но теперь общее время паузы делится на количество потоков, принимающих участие (плюс накладные расходы на синхронизацию). Это самая простая из трёх техник. Куча JavaScript приостанавливается, так как JavaScript не выполняется, поэтому каждый вспомогательный поток просто должен убедиться, что он синхронизирует доступ к любым объектам, которые также могут понадобиться другому помощнику.
Инкрементный
Инкрементальный подход заключается в том, что основной поток выполняет небольшие участки работы прерывисто. Мы не выполняем всю сборку мусора за одну инкрементальную паузу, а лишь небольшую часть всей необходимой работы. Это сложнее, потому что JavaScript выполняется между каждым инкрементальным сегментом работы, что означает, что состояние кучи изменилось, что может сделать недействительной предыдущую работу, выполненную инкрементально. Как видно из диаграммы, это не уменьшает общее время, затраченное на основной поток (на самом деле, оно обычно немного увеличивается), но равномерно распределяет его по времени. Это всё равно является хорошей техникой для решения одной из наших первоначальных проблем: задержки основного потока. Позволяя JavaScript выполняться прерывисто, но продолжая выполнять задачи сборки мусора, приложение может продолжать реагировать на ввод пользователя и обеспечивать прогресс анимации.
Параллельный
Параллельный подход заключается в том, что основной поток постоянно выполняет JavaScript, а вспомогательные потоки выполняют работу по сборке мусора полностью в фоновом режиме. Это самый сложный из трёх методов: всё, что находится в куче JavaScript, может изменить своё состояние в любой момент времени, делая недействительной выполненную ранее работу. Кроме того, теперь возникают гонки на чтение/запись, так как вспомогательные потоки и основной поток одновременно читают или изменяют одни и те же объекты. Преимущество здесь в том, что основной поток полностью свободен для выполнения JavaScript — правда, есть незначительные издержки из-за необходимости синхронизации с вспомогательными потоками.
Состояние сборки мусора в V8
Сбор мусора
Сегодня V8 использует параллельную очистку для распределения работы между вспомогательными потоками в процессе сборки мусора из молодого поколения. Каждый поток получает некоторое количество указателей, которые он следует, усердно перемещая любые живые объекты в To-Space. Задачи очистки должны синхронизироваться с помощью атомарных операций чтения/записи/сравнения-и-обмена при попытке эвакуации объекта; другая задача очистки может найти этот же объект по другому пути и также попытаться его переместить. Тот вспомогательный поток, которому удалось переместить объект, затем обновляет указатель. Оставляется направляющий указатель, чтобы другие потоки, которые найдут объект, могли обновить соответствующие указатели. Для быстрой бессинхронной размещения выживших объектов задачи очистки используют локальные буфера размещения потоков.
Основная сборка мусора
Основная сборка мусора в V8 начинается с параллельной маркировки. Когда куча приближается к динамически вычисленному пределу, запускаются задачи параллельной маркировки. Каждому вспомогательному потоку предоставляется некоторое количество указателей для обхода, и они помечают все найденные объекты, следуя всем ссылкам от обнаруженных объектов. Параллельная маркировка полностью происходит в фоновом режиме, пока JavaScript выполняется в основном потоке. Барьеры записи используются для отслеживания новых ссылок между объектами, которые создаются JavaScript, пока вспомогательные потоки маркируют.
Когда параллельная маркировка завершена, или мы достигаем динамического предела размещения, основной поток выполняет быстрый финализирующий этап маркировки. На этом этапе начинается пауза основного потока. Это представляет общее время паузы для основной сборки мусора. Основной поток снова сканирует корни, чтобы убедиться, что все живые объекты помечены, а затем вместе с рядом вспомогательных потоков начинает параллельную компактацию и обновление указателей. Не все страницы в старом пространстве доступны для компактации — те, которые нет, будут очищаться с использованием ранее упомянутых списков свободных областей. Основной поток запускает параллельные задачи очистки во время паузы. Эти задачи выполняются одновременно с задачами параллельной компактации и основным потоком — они могут продолжаться даже когда JavaScript снова выполняется в основном потоке.
Сборка мусора в период простоя
Пользователи JavaScript не имеют прямого доступа к сборщику мусора; он полностью определяется реализацией. Однако V8 предоставляет механизм для встраивания, чтобы вызвать сборку мусора, даже если программа на JavaScript этого сделать не может. GC может создавать «Задачи простоя», представляющие собой необязательную работу, которая в конечном итоге была бы выполнена в любом случае. Встраиваемые системы, такие как Chrome, могут иметь представление о свободном или состоянии покоя. Например, в Chrome при 60 кадрах в секунду у браузера есть примерно 16,6 мс, чтобы отрендерить каждый кадр анимации. Если работа для текущего кадра анимации завершена раньше времени, Chrome может выбрать выполнение некоторых задач простоя, созданных GC, в оставшееся время до следующего кадра.
Для подробной информации, обратитесь к нашему подробному изданию о GC в период простоя.
Выводы
Сборщик мусора в V8 прошёл долгий путь с момента своего создания. Добавление параллельных, инкрементальных и конкурентных техник в существующую систему сбора мусора потребовало многолетних усилий, но это окупилось, перемещая большую часть работы в фоновые задачи. Это значительно улучшило время приостановки, задержку и загрузку страниц, делая анимацию, прокрутку и взаимодействие с пользователем намного более плавными. Параллельный Scavenger уменьшил общее время сбора мусора молодого поколения на основном потоке примерно на 20%–50%, в зависимости от рабочей нагрузки. Сбор мусора в режиме ожидания может уменьшить объём памяти JavaScript в Gmail на 45%, когда он находится в режиме ожидания. Конкурентное маркирование и уборка сократило время приостановки в тяжёлых играх WebGL до 50%.
Но работа здесь ещё не завершена. Сокращение времени приостановок при сборке мусора по-прежнему важно для обеспечения лучшего опыта пользователей в интернете, и мы изучаем ещё более продвинутые техники. К тому же Blink (отрисовщик в Chrome) также имеет сборщик мусора (называется Oilpan), и мы работаем над улучшением взаимодействия между двумя сборщиками и переносом некоторых новых техник из Orinoco в Oilpan.
Большинству разработчиков не нужно задумываться о сборке мусора при создании программ на JavaScript, но понимание некоторых внутренних механизмов может помочь в управлении использованием памяти и полезными шаблонами программирования. Например, с поколенческой структурой кучи V8, объекты с коротким сроком жизни фактически очень дешевы с точки зрения сборщика мусора, так как мы оплачиваем только объекты, которые переживают сборку. Подобные шаблоны хорошо работают во многих языках с автоматической сборкой мусора, а не только в JavaScript.