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

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

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

Mark-sweep

Уборка старого поколения происходит в две фазы.

Фаза 1. Пометка (mark)

У объекта в заголовке есть служебный бит пометки (mark bit). В начале уборки он у всех обнулен. Сборщик идет от корней по ссылкам и каждому объекту, до которого дотянулся и помечает их “живыми”, если объект достижим, т.е проставляет бит пометки. Когда сборщик обошел всех, то можем наблюдать картину, что у всех достижимых объектов стоит бит, а у остальных по нулям. 

Обходя поля объектов, сборщик по последнему биту сразу понимает, что есть число, а что есть объект.

Корень - это ссылка, которая лежит вне кучи и про которую известно, что программа пользуется ей прямо сейчас. Это могут быть: локальные переменные выполняющихся функций, глобальные и статические переменные, служебные ссылки самой Dart VM.

Фаза 2. Очистка (sweep)

Теперь сборщик проходит по каждому объекту и проверяет бит. Если бит не стоит, то его память попадает в free list (список свободных блоков). В такие блоки мы можем записать новый объект. Если бит стоит, тогда сборщик просто сбрасывает его, чтобы к следующей уборке начать все сначала. Если на целой странице памяти не осталось ни одного живого объекта, страница возвращается операционной системе.

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

Фрагментация

После очистки старое поколение выглядит как дырявый сыр. Живые объекты стоят там, где стояли, а между ними остались дыры от мертвых. Свободной памяти может быть много, но она разрезана на мелкие куски. И когда программа просит место под крупный объект, может оказаться, что цельного куска нужного размера не будет. Это и называется фрагментацией. Для борьбы с этой проблемой Dart использует mark Compact. 

Mark-compact

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

Dart использует скользящий уплотнитель(sliding compactor). Все объекты сдвигаются в начало, сохраняя свой порядок. Уплотнение делается только когда фрагментация начинает мешать.

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

Как ссылки находят объекты после сдвига

Для переноса используется forwarding table (таблица пересылки). Dart делит кучу на блоки и для каждого блока хранит новый адрес и битовый вектор. Чтобы вычислить адрес нового объекта – нужно взять адрес блока, рассчитать, сколько живых клеток лежит до нужного объекта и получить конечный адрес.

Сама куча нарезана на страницы фиксированного размера. Каждая такая страница начинается с круглого адреса. Поэтому для поиска служебного заголовка достаточно обнулить младшие биты адреса.

Откуда берутся GC-паузы

Если вы в DevTools заметили ощутимые паузы GC, то это почти всегда означает, что идет очистка старого поколения. Проследить за его работой можно на вкладке Memory в DevTools.

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

Если все выше понятно, то возникает логичный вопрос: почему же эти паузы не превращаются в секундные фризы? Eve будет посвящена четвертая и финальная часть статьи, где мы рассмотрим Concurrent Marking, барьеры записи и финализаторы.

Источники:

• Вячеслав Егоров. Introduction to Dart VM, раздел Garbage Collection: https://mrale.ph/dartvm/gc.html

• Исходный код Dart SDK (runtime/vm/heap): marker, sweeper, compactor, freelist.