На конференции DConf 2017 в хакатоне я вел группу (из 2 человек) занимающуюся druntime — ковырявшуюся в сборщике мусора D. Спустя пару часов я не мог стряхнуть чувство — черт это все неплохо бы переписать. Так что я решил начать задачу построения лучшего сборщика мусора для D. Первая итерация должна быть более быстрым классическим mark-sweep сборщиком.
Чтобы объяснить мою мотивацию я покажу внутренности текущего сборщика мусора, перечислю все проблемы его дизайна. Так или иначе, мы должны анализировать то, что мы имеем, чтобы понять куда идти дальше.
Пулы, пулы повсюду
Если бы мы проигнорировали некоторую глобальную машинерию то сборщик мусора это просто массив пулов. Каждый пул это кусок mmap-нутой памяти + пачка malloc-нутых метаданных таких как таблицы для mark битов, free битов и так далее. Все аллокации происходят внутри пула, если ни один пул не может аллоцировать память, то создается новый пул. Размер пула определяется арифметической прогрессией по числу пулов или 150% размера аллокации, в зависимости от того, что больше.
Любая маленькая аллокация сперва округляется до одной из степеней 2 (класс размера) — 16, 32, 64, 128,256, 512, 1024, 2048.Затем проверяется глобальный freelist для этих классов размеров, если не удается найти мы ищем маленький пул. Этот маленький пул будет аллоцировать новую страницу связывать ее с free list объектов это класса размеров. И тут видна первая ошибка дизайна — класс размера назначается каждой странице, и следовательно нам нужна таблица, которая отражает страницу пула в класс размер (называемой pagetable).
Теперь чтобы найти начало объекта из внутреннего указателя мы сперва обнаруживаем страницу к которой он относится, затем находим ее класс и наконец маскируем биты чтобы получить начало объекта. Более того метаданные это просто пачка простых побитовых таблиц, которым нужно подстроится под гетерогенные страницы, что делается путем выделения ~7 бит на 16 байт вне зависимости от размера объекта.
Что смотивировало такой дизайн? У меня две гипотезы. Первая это нежелание резервировать память для недостаточно утилизированных пулов, что не является проблемой из-за того как устроена виртуальная память с ленивым выделением ресурсов. Вторая это опасения выделения слишком большого числа пулов, замедляя выделение памяти и что любопытно фазу mark сборщика мусора. Последнее скорее всего и есть причина, поскольку сборщик мусора делает линейный проход по пулам довольно часто и двоичный поиск для каждого потенциального указателя во время фазы mark.
Это подводит нас ко второй ошибке поиск пула за logP, где P число пулов, что делает mark NlogP задачей. Хештаблица могла бы сэкономить изрядное число циклов.
Завершая наш обзор малых пулов мы также рассмотрим выбор классов размера. Это третья проблема (не ошибка, но спорное решение) в выборе степеней двойки, что гарантирует нам вплоть до 50% внутренней фрагментации. Современные аллокаторы такие как jemalloc предоставляют по одному классы между степенями двоек. Деление на константу не степени двойки немного дороже чем один AND, но все же вполне приемлимы по скорости.
Давайте посмотрим на пулы для больших объектов. Первое, что бросается в глаза это то, что гранулярность одна страница памяти — 4кб для метаданных и аллокаций. Ряды свободных страниц связаны в free list, который сканируется линейно для каждой аллокации. Это четвертая ошибка, то есть с производительностью больших аллокаций решили не заморачиваться. Чтобы обнаружить начало объекта поддерживается отдельная таблица, где для каждой страницы хранится индекс начала относящегося к ней объекта. Эта схема кажется разумной пока мы не задумаемся над большими аллокациями 100+ Mb, поскольку почти наверняка не сможет релоцироваться по месту и создаст новый пул, что израсходует впустую огромный объем памяти на мета данные того, что по сути является одним объектом.
Сборка
До сих пор мы рассматривали путь аллокации, деаллокация проходит через те же стадии. Что более интересно это автоматический возврат памяти, что и есть суть сборки мусора. Позволим себе заметить, что сборка мусора в D консервативная, то есть сборщик не знает является ли что-то указателем или нет. Также он поддерживает финализацию, то есть действия которые вызываются на объекте прежде, чем возвращать его память. Эти два фактора сильно ограничивают архитектуру сборщика.
На верхнем уровне сборка неожиданно занимает аж 4 фазы: prepare, markAll, sweep и recover.
Стадия prepare самая странная, поскольку по сути она должна быть просто «скопировать free биты в mark биты» (чтобы избежать сканирования свободной памяти). Ситуация осложнена тем что мы вычисляем свободное простоанство путем обхода всех free list. Это 5-я (?) ошибка — скакание дополнительно по неизвестному числу указателей это последнее что стоит делать во время stop the world паузы. Более удачный дизайн это переключать биты при аллокации, особенно с учетом того, что free list поддерживает указатели на пулы для каждого объекта чтобы не выполнять поиск пула.
Реальный mark выполняется в вызове markAll, которая просто передает подходящие диапазоны памяти в функцию mark. Эта функция заслуживает более глубокого рассмотрения.
- Для каждого указателя в диапазоне памяти она сперва проверяет попадает ли адрес в диапазон адресов кучи сборщика мусора (от наименьшего адреса в пуле до наибольшего адреса в пуле).
- После этого идет пугающий двоичный поиск, чтобы найти соответствующий пул для указателя.
- Независимо от типа пула делается чтение из таблицы страниц текущего пула чтобы посмотреть класс размера или является ли это большим объектом, или даже свободной памятью. Небольшая оптимизация состоит в том, что это чтение также говорит нам, является ли это началом большого объекта или его продолжением. У нас 3 случая — маленький объект, большой объект или продолжение большого объекта. Последние два случая одинаковы за исключением дополнительного чтения из таблицы.
- Определение начала объекта маскирование бит с соответствующей маской, плюс в случае продолжения большого объекта дополнительное чтение из таблицы смещений.
- В случае большого объекта существует бит «нет внутренних указателей», что позволяет игнорировать указатели внутрь объекта.
- Наконец проверить и выставить бит mark, если он не был выставлен или стоит noscan бит добавить объект к стеку памяти под сканирование.
Пропуская любопытные манипуляции со стеком (чтобы избежать переполнения стека и в то же время использовать стековую аллокацию) это все, что у нас есть в mark функции. Кроме уже упоминавшегося поиска пулов, неэффективностей полно. Смещивание памяти без указателей с обычной памятью в одном пуле дает нам дополнительное чтение битовой таблицы на критическом пути. Аналогично чтение таблицы страниц можно было бы избежать если бы мы разделяли пулы по классу размера. И конечно спорная оптимизация «нет внутренних указателей», которая не только дает небезопасный код (объект может быть собран, несмотря на ссылки на него), но и добавляет дополнительные проверки на критическом пути для всех больших объектов, добавляя потенциальное чтение битовой таблицы.
Что же это было довольно сложно, но помните что mark фаза это сердце любого сборщика. Теперь к третьей фазе — sweep. Иронично sweep не подчищает память в free list-ы как можно было бы ожидать. Вместо этого все чем она занимается это вызов finalizer-ов (если есть) и установкой свободных битов и прочих таблиц. Имеем в виду, что при этом выполняется линейный проход по памяти каждого пула и просмотр mark битов.
Финальная стадия — recover, действительно строит free list-ы. Это опять линейный проход, но только по маленьким пулам. Снова чтение таблицы страниц для каждой страницы чтобы узнать класс размера, просто хочется плакать. Но основной вопрос без ответа — зачем? Зачем дополнительный проход? Я сильно старался чтобы придумать разумное объяснение, но не смог, «для простоты» слабая, но вероятная причина. Это последняя большая ошибка по моим подсчетам.
Чего здесь нет
До сих пор я критиковал то, что видно невооруженным глазом, теперь настало время пройтись по тому, чего просто нет.
Thread cache явный недосмотр, имея в виду что сборщик мусора D уходит корнями в ранние 2000ые это не так уж неожиданно. Практически каждый современный аллокатор имеет некий thread cache, некоторые пытаются поддерживать по процессорный кеш. Кеш работает так, что каждый thread выделяет аллокации пачками, сохраняя запас аллокаций на будущее. Это амортизирует цену блокирования общих структур кучи. Кстати присутствует немного fine grained блокирование, но не на уровне отдельных пулов, к примеру.
[Обновление 2024] Сборщик D получил параллельный mark и есть даже версия concurrent сборщика для Posix.
Параллельный mark еще один пример современной фичи, которая ожидается от любого сборщика мусора. Также популяны concurrent или mostly concurrent сборщики, в которых mark и немного реже sweep/compaction выполняются одновременно с работой пользовательских потоков.
В заключение
Пост оказался довольно длинным и несколько сложнее, чем я хотел бы. И все же я уверен, что он доносит мысль — сборщик мусора D медленный не из-за какого-то фундаментального ограничения, а из-за полудюжины или около того плохих решений при реализации. В том же духе можно реализовать сборщик с поколениями, который будет медленным, просто упустив хорошие техники реализации.
Теперь подведем итог моей первой итерации изменений по сравнению с статус-кво.
- Разделить маленькие пулы по классу размера.
- Сделать поиск пула O (1).
- Попытаться использовать классы размера не степеней двойки как jemalloc, чтобы побороть внутренную фрагментацию.
- Разделит все пулы на основе noscan атрибута, это ускоряет mark.
- Предусмотреть 3-ий класс «пулов» для огромных аллокаций рассчитанных только на один объект.
- Аллокация объектов для больших пуллов требует проработки, нужно какое-то дерево с ключом по размеру блока. jemallox использует красно-черные деревья.
- Игнорировать атрибут «нет внутренних указателей» он пытается побороть ложные указатели по причине консервативности сборщика мусора. Однако это фундаментально небезапасно и цена слишком высока, ну и наконец, это абсолютно бессмысленно на 64-битных системах, где живут ваши серверы.
- Никаких сомнительных мультифазных сборок, это mark и sweep и точка.
- Fine grained блокировки с самого начала, я не вижу проблем с блокировками по отдельным пулам.
Вторая итерация будет сосредоточенна на более мясистых вещах вроде thread cache, параллельного mark и concurrent mark с использованием fork.
Третья итерация, если мы до нее доберемся, будет абсолютно новый дизайн — mark-region сборщик, с архитектурой вдохновленной immix.
На этом мои планы завершаются и на этой оптимистичной ноте, я должен предупредить, что поначалу это будет Linux специфичный сборщик, постепенно эволюционирующий до любой Posix системы, а поддержка Windows является отдаленной возможностью.
Vkontakte
Twitter
Одноклассники
