company_banner

Высокопроизводительная сборка мусора для C++

Автор оригинала: Anton Bikineev, Omer Katz, Michael Lippautz
  • Перевод
Мы уже писали о сборке мусора для JavaScript, о DOM, и о том, как всё это реализовано и оптимизировано в JS-движке V8. Правда, Chromium — это не только JavaScript. Большая часть браузера и движок рендеринга Blink, куда встроен V8, написаны на C++. JavaScript можно использовать для работы с DOM, а на экран изменения выводятся с использованием конвейера рендеринга.

Так как граф C++-объектов, имеющих отношение к DOM, тесно связан с JavaScript-объектами, команда разработчиков Chromium пару лет назад начала использовать для управления памятью, в которой хранятся эти объекты, сборщик мусора, названный Oilpan. Oilpan — это сборщик мусора, написанный на C++ и предназначенный для управления C++-памятью, которая может быть подключена к V8. Управление памятью осуществляется с использованием технологии кросс-компонентной сборки мусора. В рамках этой технологии граф связанных C++/JavaScript-объектов рассматривается как единая куча.



Этот материал является первой публикацией, посвящённой Oilpan. Здесь будет сделан обзор основных принципов, лежащих в основе данного сборщика мусора, а также — C++-API Oilpan. Мы рассмотрим некоторые возможности, поддерживаемые Oilpan, расскажем о том, как устроена работа различных подсистемам сборщика мусора. Тут же мы разберём процесс конкурентного освобождения памяти, занятой объектами.

Самое интересное здесь то, что система Oilpan является частью Blink, но сейчас осуществляется её перевод в V8, где она будет представлена в форме библиотеки для сборки мусора. Цель этого всего заключается в том, чтобы облегчить доступ к C++-механизмам сборки мусора всем тем, кто встраивает в свои платформы движок V8. Кроме того, то, что Oilpan станет библиотекой, позволит пользоваться этой системой абсолютно всем заинтересованным в ней C++-программистам.

Общие сведения


В Oilpan применяется система сборки мусора, в которой используется алгоритм пометок (Mark and Sweep). Этот алгоритм предусматривает разделение процесса сборки мусора на две фазы. Первая фаза заключается в исследовании кучи, и в пометке (mark) «живых» объектов, которые нельзя удалять из памяти. Вторая фаза — это очистка (sweep) памяти кучи, которую занимают ненужные («мёртвые») объекты.

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

В этом плане C++ от JavaScript не отличается. Правда, в отличие от JavaScript-объектов, C++-объекты статически типизированы. Они, в результате, не могут менять собственное представление во время выполнения программы. При работе с C++-объектами с применением Oilpan этот факт учитывается и предоставляется описание указателей на другие объекты (рёбра графа) с использованием паттерна «Посетитель» (Visitor). Базовый паттерн используемый для описания Oilpan-объектов, выглядит так:

class LinkedNode final : public GarbageCollected<LinkedNode> {
 public:
  LinkedNode(LinkedNode* next, int value) : next_(next), value_(value) {}
  void Trace(Visitor* visitor) const {
    visitor->Trace(next_);
  }
 private:
  Member<LinkedNode> next_;
  int value_;
};

LinkedNode* CreateNodes() {
  LinkedNode* first_node = MakeGarbageCollected<LinkedNode>(nullptr, 1);
  LinkedNode* second_node = MakeGarbageCollected<LinkedNode>(first_node, 2);
  return second_node;
}

В этом примере Oilpan управляет LinkedNode, на что указывает то, что класс LinkedNode является наследником GarbageCollected<LinkedNode>. Когда сборщик мусора обрабатывает объект, он находит указатели на другие объекты, вызывая метод объекта Trace. Тип Member — это интеллектуальный указатель, который, с синтаксической точки зрения, похож, например, на std::shared_ptr, который предоставляется Oilpan и используется для поддержания единообразного состояния при обходе графа объектов во время выполнения маркировки объектов. Всё это позволяет Oilpan точно знать о том, где именно находятся указатели, с которыми работает эта система.

Тот, кто внимательно прочитал вышеприведённый код, возможно, заметил (и, может быть, его это испугало) то, что first_node и second_node хранятся в стеке в виде обычных C++-указателей. Oilpan не задействует дополнительные абстракции для работы со стеком. Сборщик мусора, обрабатывая корневые объекты в куче, которой управляет, полагается исключительно на консервативное сканирование стека при поиске указателей. Всё это работает путём пословного перебора стека и благодаря интерпретации слов в виде указателей на сущности, находящиеся в управляемой куче. Это означает, что использование Oilpan не приводит к ухудшению производительности при доступе к объектам, размещаемым в стеке. Вместо этого нагрузка переносится на этап сборки мусора, когда осуществляется консервативное сканирование стека. Oilpan интегрирован в подсистему рендеринга и пытается откладывать запуск процедуры сборки мусора до тех пор, пока система не достигнет состояния, когда в стеке, точно, не будет ничего интересного. Так как работа веб основана на событиях, а выполнение кода производится путём обработки задач в циклах событий, в распоряжении Oilpan оказывается достаточно удобных моментов для запуска сборки мусора.

Oilpan используется в Blink, а это — большая кодовая база, написанная на C++, в которой содержатся значительные объёмы зрелого кода. Благодаря этому Oilpan, кроме прочего, отличается следующими возможностями:

  • Множественное наследование с помощью миксинов и ссылок на подобные миксины (внутренние указатели).
  • Поддержка вызова сборки мусора при выполнении конструкторов.
  • Поддержание объектов из неуправляемой памяти в «живом» состоянии с помощью интеллектуальных указателей Persistent, которые рассматриваются как корневые сущности.
  • Коллекции, представляющие собой последовательные (например — vector) и ассоциативные (например — set и map) контейнеры. Возможность уплотнения данных, лежащих в основе коллекций.
  • Слабые ссылки, слабые функции и эфемерные структур данных.
  • Финализаторы — методы, выполняемые перед удалением из памяти отдельных объектов.

Очистка памяти для C++


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

Очистка — это та фаза работы Oilpan, когда уничтожаются «мёртвые» объекты (те, которых не удалось достичь на фазе пометки объектов). Память, которую они занимают, либо возвращается операционной системе, либо становится доступной для выделения под другие объекты. Ниже мы поговорим о том, как Oilpan выполняет очистку памяти, рассмотрим особенности выполнения этого процесса и его ограничения. Мы, кроме того, поговорим о том, как механизму очистки памяти Oilpan удаётся достигать высоких скоростей при уничтожении «мёртвых» объектов.

Система очистки памяти находит «мёртвые» объекты, перебирая память кучи и проверяя соответствующие биты объектов. Для того чтобы сохранить семантику C++, системе очистки памяти нужно вызывать деструктор каждого из «мёртвых» объектов перед освобождением занимаемой им памяти. Нетривиальные деструкторы реализуются в виде финализаторов.

Здесь, с точки зрения программиста, нет заранее заданного порядка, в котором вызываются деструкторы, так как механизм перебора, используемый системой очистки памяти, не принимает во внимание порядок создания уничтожаемых объектов. Это накладывает на финализаторы ограничения, в соответствии с которым они не могут обращаться к другим объектам, находящимся в куче. Перед нами встаёт задача, встречающаяся достаточно часто. Она заключается в следующем: есть платформа, которая не поддерживает указание порядка финализации объектов (вроде Java), но при этом для данной платформы нужно писать код, требующий определённого порядка вызова финализаторов. Oilpan использует плагин Clang, который, в статическом режиме, обеспечивает запрет доступа к объектам кучи в процессе уничтожения объектов (это — лишь одна из многих возможностей Clang):

class GCed : public GarbageCollected<GCed> {
 public:
  void DoSomething();
  void Trace(Visitor* visitor) {
    visitor->Trace(other_);
  }
  ~GCed() {
    other_->DoSomething();  // error: Finalizer '~GCed' accesses
                            // potentially finalized field 'other_'.
  }
 private:
  Member<GCed> other_;
};

В этом коде происходит ошибка при попытке обращения к объекту из кучи в ходе уничтожения другого объекта.

Если вас интересует вопрос уничтожения объектов, то знайте, что Oilpan даёт в распоряжение программиста коллбэки, вызываемые перед финализатором. Это позволяет реализовывать сложные схемы уничтожения объектов, когда объекту, перед уничтожением, нужен доступ к другим объектам. Подобные коллбэки создают немалую дополнительную нагрузку на систему в ходе сборки мусора. Эта нагрузка больше той, которую способны создать деструкторы. Поэтому такие коллбэки используются в Blink относительно редко.

Инкрементальная и конкурентная очистка памяти


Теперь, когда мы поговорили об ограничениях деструкторов в управляемом C++-окружении, пришло время более подробно остановиться на том, как в Oilpan реализована и оптимизирована очистка памяти.

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

В самом начале в Oilpan использовался механизм очистки памяти, реализованный по схеме «stop-the-world». Это означало, что выполнение приложения в главном потоке приостанавливалось во время проведения процедуры очистки памяти.


Приостановка выполнения кода в ходе очистки памяти

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


Инкрементальная очистка памяти

При использовании инкрементального подхода фазы пометки и уничтожения объектов отделены друг от друга. При этом процедура очистки памяти разбита на несколько частей, представленных отдельными задачами, выполняющимися в главном потоке. В лучшем случае подобные задачи выполняются только во время простоя системы, что позволяет избежать их конфликта с задачами, представляющими обычные механизмы приложения. Внутренние механизмы сборщика мусора разделяют одну большую задачу по очистке памяти на небольшие задачи, это разделение основано на понятии «страница». Страницы могут пребывать в двух состояниях. Одни страницы находятся в состоянии ожидания очистки (to-be-swept), а другие уже являются очищенными (already-swept). Механизмы выделения памяти учитывают только страницы, которые уже очищены, и пополняют локальные буферы выделения памяти (Local Allocation Buffer, LAB) из списка свободной памяти, в котором хранится список доступных фрагментов памяти. Для того чтобы получить память, сведения о которой есть в списке свободной памяти, приложение сначала попытается найти память, которая относится к уже очищенным страницам. Затем приложение попытается помочь системе в обработке страниц, которые ожидают очистки, воспользовавшись там, где оно пытается выделить память, системой очистки памяти. Новая память у операционной системы будет запрошена лишь в том случае, если вышеприведённые действия не привели к тому, что приложение получило нужную ему память.

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

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

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


Конкурентная очистка памяти с использованием фоновых задач

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

Результаты


Механизм фоновой очистки памяти был выпущен в сборке Chrome M78. Наш фреймворк для тестирования Chrome в условиях, приближенных к реальным, показал уменьшение времени, уходящего в главном потоке на операции, связанные с очисткой памяти, на 25-50% (в среднем — на 42%). Ниже показаны результаты испытаний некоторых популярных веб-проектов.


Время в миллисекундах, затрачиваемое на выполнение операций по очистке памяти. Синим цветом выделены результаты, полученные в M77 без использования конкурентной очистки памяти. Красным представлены результаты M78, где конкурентная очистка памяти используется

То время, которое всё ещё уходит в главном потоке на очистку памяти, требуется для выполнения финализаторов. В настоящее время идёт работа по оптимизации финализаторов для типов объектов, которые часто используются в Blink. Примечательно здесь то, что все такие оптимизации проводятся за пределами кода системы очистки памяти, так как эта система, в её текущем виде, автоматически подстраивается под ситуацию при отсутствии финализаторов.

Сталкивались ли вы с проблемами производительности веб-проектов, которые вызваны системой сборки мусора Chrome?



RUVDS.com
RUVDS – хостинг VDS/VPS серверов

Комментарии 6

    –2

    Убийца раста?

      +2
      Идея раста как раз в том чтобы не иметь сборщика мусора, но при этом, чтобы работа с пямятью оставалась максимально безопасной.
      В C++ для этого существуют умные указатели и RAII, но это не одно и то же.
      Кроме того, для C++ уже давно существуют сборщики мусора.
      Например, Boehm-Demers-Weiser Garbage Collector.
        +1

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


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

      +3

      Так и не понял из статьи, зачем это всё вдруг понадобилось.

        0

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

        0
        А кому это показалось интересным, советую еще посмотреть отличный доклад «Unified Javascript & Blink Heap» с BlinkOn 9, где разработчики рассказывают, как они красиво увязали V8 (JS) и Blink (C++) хипы (один и тот же DOM-объект живет и там и там одновременно со ссылками в обе стороны) и заставили оба сборщика мусора работать оптимальнее.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое