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

Эта статья — моя попытка объяснить вам доходчивым языком, что же такое Garbage Collector в Dart, объяснить почему эти некоторые знания нам нужны на практике и что из всей этой тяжелой, технической внутрянки вам необходимо знать.

Эта статья опирается на документацию Вячеслава Егорова о внутренностях Dart VM. Я пересказываю её простым языком и добавляю то, что важно на практике.

Биты наше все

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

Если брать простой пример примитивный, то память компьютера можно визуализировать как длинный ряд ячеек, внутри каждой такой ячейки лежит бит, а бит это 0 или 1.
С битами процессор работает не по одному, а группами. И если мы возьмем «современные» 64-битные процессоры, то увидим, что у все они работают с группами битов размером 64 бит(8 байт). Одну такую группу можно называть машинным словом.
Указатель же в Dart помещается ровно в это одно машинное слово, то есть 8 байт.

Итак, два важных утверждения из описанного:

• Бит 0 или 1 

• Указатель = 8 байт.

Что такое указатель

Указатель это не сам адрес, а место, где этот адрес записан. Возьмем аналогию на примере адреса дома. Листок это указатель, а то, что на нем написано — это и как раз и есть адрес. Когда программе необходимо узнать адрес, она берет указатель и считывает адрес. По этому адресу мы дальше узнаем что же за объект нас ждет и объект ли это вообще.

Адрес может ссылаться не на объект?

Может. И это гениальное решение. В коде мы используем разные данные. Разного вида числа и объекты. 

Возьмем пример: 

int age = 7;

User user = User();

Dart хранит эти две переменные по‑разному. Если он видит, что перед ним число, то он даже не полезет за его адресом в кучу, а вот для объекта придется сходить все‑таки по адресу и навестить объект. Как же он это делает? Все решает последний бит. 

Как работает последний бит

Адреса объектов в памяти кратны 16. Разработчики Dart специально сделали так. Если адрес кратен 16 (10000), то значит его последние биты всегда нули, никакой информации они не несут. Вот это пустующее место и забирает Dart под флажок. Последний бит говорит, чем является значение в указателе. Если он равен 1, значит перед нами ссылка на объект, если 0, значит это число и не нужно искать объект по адресу.

Рассмотрим конкретный пример на произвольном адресе:
Допустим у нас объект лежит по адресу 0x00A03F50 — этот адрес кратен 16.
В двоичном виде последний байт этого адреса выглядит так: 0101 0000.
Видим на конце нули, а зная то, что у нас на конце в адресе всегда будут нули, то это можно использовать для своих нужд. В данном случае Dart сделает это так 0101 0001->0x00A03F51 — поставит единицу в конце, т.е пометит, что это адрес объекта.

Хорошо, теперь обратное действие, нам надо дойти до реального объекта.
Убираем нашу единицу 0x00A03F51->0x00A03F50 = 0101 0000.

Именно тут очень важно, чтобы адрес был кратен 16, ведь если число будет меньше, то и свободных битов будет на конце меньше, а если будем брать кратность 32, то это слишком большое потребление по памяти и на мелких объектах память тратилась бы впустую. Но вот про smi(small integer) числа все немного интереснее.

Smi: число прямо в указателе

Если число уместилось в указателе, то его можно назвать smi (small integer).
Smi не занимает места в памяти напрямую, живет прямо в указателе, а значит искать его по адресу и убирать за ним не нужно. Однако сам указатель занимает 8 байт, поэтому можно считать, что любое smi занимает 8 байт.

Возьмем пример, число 7 = 111 (в битах)
Когда Dart упаковывает 7 в Smi, он сдвигает биты влево на 1 позицию. Сдвиг влево это умножение на два. Получаем 1110. Ноль на конце означает, что наш указатель будет распаковывать в будущем это значение как число smi, поделив число на 2. (1110 / 2 = 111). 

Handles: зачем нужен мостик для C++

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

Но вот что делать с кодом на C++, это сам движок и нативные библиотеки. Сборщик понятия не имеет где у этого кода лежат ссылки. Если объект переедет, C++ останется со старым адресом, и программа упадёт.
Для решения этой проблемы придумали handle. Handle это ссылка на ссылку. Код на C++ держит не сам объект, а handle с адресом объекта. Когда объект переезжает, то сборщик обновляет адрес внутри handle. А так как C++ всегда смотрит на ссылку, которая ссылается на ссылку, то мы исключаем проблемы с пропажей адреса.

Что же из первой части может быть полезно на практике

1. Числа почти бесплатны. Int: индексы, счетчики и т.д все это smi. В память ничего из этого не попадает, сборщик за ними не следит.
2. Любой новый созданный объект — это работа для сборщика. Чем больше бездумных объектов мы создаем, тем больше давим на память и работу сборщика.
В следующей части посмотрим, почему сборщик делит память на два поколения и почему временные объекты в Dart обходятся так дёшево.

Источники

— Vyacheslav Egorov. Introduction to Dart VM, раздел Garbage Collection: https://mrale.ph/dartvm/gc.html‑ Исходный код Dart SDK (runtime/vm/heap): scavenger, marker, sweeper, compactor.