Параллельная маркировка в V8

Этот пост описывает технику сборки мусора, называемую параллельной маркировкой. Оптимизация позволяет JavaScript-приложению продолжать выполнение, пока сборщик мусора сканирует кучу для нахождения и маркировки живых объектов. Наши тесты показывают, что параллельная маркировка сокращает время, затрачиваемое на маркировку в главном потоке, на 60%–70%. Параллельная маркировка является последним элементом проекта Orinoco — проекта по постепенной замене старого сборщика мусора новым, в основном параллельным и многопоточным сборщиком мусора. Параллельная маркировка включена по умолчанию в Chrome 64 и Node.js v10.

Фон

Маркировка является фазой Mark-Compact сборщика мусора V8. В этой фазе сборщик обнаруживает и маркирует все живые объекты. Маркировка начинается с набора известных живых объектов, таких как глобальный объект и текущие активные функции — так называемые корни. Сборщик маркирует корни как живые и следует указателям в них, чтобы обнаружить больше живых объектов. Сборщик продолжает маркировать вновь обнаруженные объекты и следовать указателям, пока не останется больше объектов для маркировки. В конце маркировки все немаркированные объекты в куче становятся недоступными для приложения и могут быть безопасно освобождены.

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

V8 реализует маркировку, используя два битa маркировки для каждого объекта и рабочий список маркировки. Два бита маркировки кодируют три цвета: белый (00), серый (10) и черный (11). Изначально все объекты белые, что означает, что сборщик еще не обнаружил их. Белый объект становится серым, когда сборщик обнаруживает его и помещает в рабочий список маркировки. Серый объект становится черным, когда сборщик извлекает его из рабочего списка маркировки и посещает все его поля. Эта схема называется трехцветной маркировкой. Маркировка завершается, когда больше нет серых объектов. Все оставшиеся белые объекты недоступны и могут быть безопасно освобождены.

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

Сокращение паузы маркировки

Маркировка, выполняемая за один раз, может занять несколько сотен миллисекунд для больших куч.

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

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

Инкрементная маркировка не предоставляется бесплатно. Приложение должно уведомлять сборщик мусора обо всех операциях, которые изменяют граф объектов. V8 реализует уведомление с использованием барьера записи, выполненного в стиле Дейкстры. После каждой операции записи вида object.field = value в JavaScript V8 вставляет код барьера записи:

// Вызывается после `object.field = value`.
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

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

Инкрементное маркирование хорошо интегрируется с планированием сборки мусора во время простоя, как описано в предыдущей записи блога. Планировщик задач Blink в Chrome может запланировать небольшие шаги инкрементного маркирования во время простоя на основном потоке без создания замираний. Эта оптимизация работает очень хорошо, если доступно время простоя.

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

Параллельное маркирование выполняется на основном потоке и рабочих потоках. Приложение приостановлено на всем протяжении фазы параллельного маркирования. Это многопоточная версия маркирования типа 'остановить все'.

Конкурентное маркирование выполняется преимущественно на рабочих потоках. Приложение может продолжать работать, пока идет процесс конкурентного маркирования.

Следующие две секции описывают, как мы добавили поддержку параллельного и конкурентного маркирования в V8.

Параллельное маркирование

Во время параллельного маркирования мы можем предполагать, что приложение не работает одновременно. Это значительно упрощает реализацию, поскольку можно считать, что граф объектов статичен и не изменяется. Чтобы выполнить маркирование графа объектов параллельно, необходимо сделать структуры данных сборщика мусора безопасными для потоков и найти способ эффективно разделить работу по маркированию между потоками. Следующий диаграмма показывает структуры данных, участвующие в параллельном маркировании. Стрелки указывают направление потока данных. Для упрощения на диаграмме опущены структуры данных, необходимые для дефрагментации кучи.

Заметьте, что потоки только читают граф объектов и никогда его не изменяют. Битмарки объектов и рабочая очередь маркирования должны поддерживать доступ на чтение и запись.

Рабочая очередь маркирования и кража работы

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

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

Конкурентное маркирование

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

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

• Выделение объекта.
• Запись в поле объекта.
• Изменения макета объекта.
• Десериализация из снимка.
• Материализация во время дезоптимизации функции.
• Эвакуация во время сборки мусора молодого поколения.
• Патчинг кода.

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

Заглушка записи

Гонка данных, вызванная записью в поле объекта, разрешается путем превращения операции записи в ослабленную атомарную запись и настройки заглушки записи:

// Вызывается после atomic_relaxed_write(&object.field, value);
write_barrier(object, field_offset, value) {
  если (цвет(значение) == белый && атомный_переход_цвета(значение, белый, серый)) {
    список_работ_маркировки.push(значение);
  }
}

Сравните это с ранее используемым барьером записи:

// Вызывается после `object.field = значение`.
барьер_записи(object, field_offset, значение) {
  если (цвет(object) == черный && цвет(значение) == белый) {
    установить_цвет(значение, серый);
    список_работ_маркировки.push(значение);
  }
}

Есть два изменения:

1. Проверка цвета исходного объекта (цвет(object) == черный) удалена.
2. Переход цвета значения из белого в серый происходит атомарно.

Без проверки цвета исходного объекта барьер записи становится более консервативным, то есть он может отмечать объекты как активные, даже если эти объекты действительно недостижимы. Мы удалили проверку, чтобы избежать дорогостоящего барьера памяти, который был бы необходим между операцией записи и барьером записи:

атомарная_расслабленная_запись(&object.field, значение);
барьер_памяти();
барьер_записи(object, field_offset, значение);

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

Список работы для откатов

Некоторые операции, например модификация кода, требуют эксклюзивного доступа к объекту. Ранние мы решили избегать блокировок на уровне объекта, поскольку они могут привести к проблемам с инверсией приоритетов, где главный поток должен ждать рабочего потока, который был снят с расписания, удерживая блокировку объекта. Вместо блокировки объекта мы позволяем рабочему потоку отказаться от посещения объекта. Рабочий поток делает это, поместив объект в список работы для откатов, который обрабатывается только главным потоком:

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

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

Изменения структуры объекта

Поле объекта может хранить три вида значений: тегированный указатель, тегированное маленькое целое число (также известное как Smi) или нетегированное значение, такое как необработанное число с плавающей точкой. Тегирование указателей — это хорошо известная техника, позволяющая эффективно представлять необработанные целые числа. В V8 наименее значимый бит тегированного значения указывает, является ли это указателем или целым числом. Это основывается на том, что указатели выровнены по словам. Информация о том, является ли поле тегированным или нетегированным, хранится в скрытом классе объекта.

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

атомный_переход_цвета(object, белый, серый);
если (атомный_переход_цвета(object, серый, черный)) {
  // Объект будет снова посещен главным потоком во время обработки
  // списка работы для откатов.
  список_работы_для_откатов.push(object);
}
небезопасное_изменение_структуры_объекта(object);

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

снимок = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
  pointer = atomic_relaxed_load(object + field_offset);
  snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
  visit_pointers(snapshot);
}

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

Объединение всех компонентов

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

Результаты

Наш фреймворк тестирования реального мира показывает снижение времени маркировки основного потока на цикл сборки мусора примерно на 65% и 70% соответственно для мобильных устройств и настольных компьютеров.

Конкурентная маркировка также уменьшает задержки при сборке мусора в Node.js. Это особенно важно, поскольку Node.js никогда не реализовывал планирование сборки мусора в моменты простоя и, следовательно, никогда не мог скрыть время маркировки в фазах, критичных к задержкам. Конкурентная маркировка была внедрена в Node.js v10.