Jank Busters Part Two: Orinoco

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

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

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

Так как между эвакуацией молодого поколения и компактацией старого поколения нет зависимостей, теперь Orinoco выполняет эти фазы параллельно, как показано на Рисунке 2. Результат этих улучшений — сокращение времени компактации на 75%: с ~7 мс до менее чем 2 мс в среднем.

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

Ранее V8 реализовывал запоминаемые наборы в виде массивов адресов указателей или буферов хранения. Для молодого поколения был один буфер хранения, а для каждого из фрагментированных страниц старого поколения был свой. Буфер хранения страницы содержит адреса всех входящих указателей, как показано на Рис. 3. Записи добавляются в буфер хранения в барьере записи, который защищает операции записи в коде JavaScript. Это может привести к дублирующимся записям, поскольку буфер хранения может включать один указатель несколько раз, а два разных буфера хранения могут включать один и тот же указатель. Дублирующиеся записи усложняют параллелизацию этапа обновления указателей из-за состояния гонки, вызванного тем, что два потока пытаются обновить один и тот же указатель.

Orinoco устраняет эту сложность, реорганизуя запоминаемый набор для упрощения параллелизации и обеспечения того, чтобы потоки получали несмежные наборы указателей для обновления. Вместо хранения входящих интересных указателей в массиве каждая страница теперь хранит смещения интересных указателей, исходящих из этой страницы, в корзинах битмапов, как показано на Рис. 4. Каждая корзина либо пуста, либо указывает на битмап фиксированной длины. Бит в битмапе соответствует смещению указателя на странице. Если бит установлен, то указатель является интересным и входит в запоминаемый набор. Используя эту структуру данных, мы можем параллелизовать обновление указателей на основе страниц. Отсутствие дублирующихся записей и плотное представление указателей также позволили нам удалить сложный код для обработки переполнения запоминаемого набора. В нашем длительном тесте производительности Gmail это изменение уменьшило максимальное время паузы при сборке мусора с уплотнением на 45% с 42ms до 23ms.

Третья оптимизация, которую вводит Orinoco, — это черное выделение, улучшение этапа маркировки сборщика мусора. Черное выделение (включено в V8 5.1) — это техника сборки мусора, при которой все объекты, выделенные в старом поколении (например, выделения с предварительным закреплением или продвигаемые объекты сборщиком мусора) сразу же отмечаются черным, чтобы обозначить их как "живые". Интуитивное предположение черного выделения заключается в том, что объекты, выделенные в старом поколении, вероятнее всего, долгоживущие. Следовательно, объекты, которые были недавно выделены в старом поколении, по крайней мере должны пережить следующую сборку мусора старого поколения, иначе они были ошибочно повышены. После окрашивания недавно выделенных объектов в черный сборщик мусора не будет их посещать. Мы ускоряем окрашивание черных объектов, выделяя их на черных страницах, где все объекты изначально черные. Еще одно преимущество черных страниц состоит в том, что их не нужно подметать, так как все объекты на них (по определению) живые. Черное выделение ускоряет прогресс инкрементальной маркировки, поскольку объем маркировочной работы не увеличивается с новыми выделениями. Воздействие черного выделения особенно видно на тесте Octane Splay, где производительность и оценка задержки улучшились примерно на 30%, а использование памяти уменьшилось на 20% из-за более быстрого прогресса маркировки и меньшей работы при сборке мусора в целом.

Мы планируем скоро внедрить больше функций Orinoco. Следите за обновлениями, мы продолжаем экспериментировать!