#common

Сборщики мусора 1/2.

По чуть-чуть начал разбираться со сборкой мусора, так что накидаю вам немного инфы о ней.

Есть несколько базовых алгосов, которые в разных вариациях юзаются в большинстве промышленных garbage collector'ах. В основном они делятся на трассирующие (которые отслеживают достижимость объекта) и прямые. И параллельно делятся на перемещающие и не перемещающие (в моей вольной интерпретации).

Mark-and-sweep.
Самый дефолтный алгоритм. Для каждого объекта хранится бит достижимости. Изначально он ноль. Все объекты указывают друг на друга. Есть специальные корневые объекты. На этапе mark дфсом обходим все объекты, достижимые из корневых, и устанавливаем им бит достижимости в 1. На этапе sweep обходим все объекты и проверяем, если бит достижимости 1, то просто его сбрасываем. Если же он 0, то объект помечается удалённым (обычно пихают его во freelist). Проблемой такого подхода является stop the world -- всё выполнение программы останавливается, пока сборка на закончится.
Есть ещё вариация mark-and-compact, где вместо помечания участка памяти свободным объекты в памяти как-то перемещаются, чтобы немного её дефрагментировать.

Существует улучшенная версия этого алгоритма под названием BF Mark, которая избавлена от этих недостатков.
Вместо двух "цветов" достижим/нет объект используется 3: чёрный, серый и белый. Чёрные объекты доступны из корней и не имеют исходящих ссылок на белые объекты, белые -- кандидаты на удаление, серые -- объекты доступные из корней, но пока не проверенные на наличие ссылок на белые объекты. Алгоритм состоит из трёх шагов: выбрать объект из серого множества и переместить его в чёрное; поместить все белые объекты, на которые есть ссылки из нового чёрного в серое множество; повторять прошлые два шага, пока серое множество не станет пустым. Когда серый набор пуст, сканирование завершено: черные объекты доступны из корней, в то время как белые объекты недоступны и могут быть собраны мусором. Поскольку все объекты, до которых невозможно добраться сразу из корней, добавляются к белому набору, а объекты могут перемещаться только от белого к серому и от серого к черному, алгоритм сохраняет важный инвариант - никакие черные объекты не ссылаются на белые объекты. Это гарантирует, что белые объекты могут быть освобождены после того, как серый набор станет пустым. Такой метод удобен, потому что его можно выполнять на лету.

Ещё популярна копирующая сборка (semispace/Lisp 2/алгоритм Чейни). Алгоритм основывается на том, что выделяется две области памяти одинакового размера. Все объекты создаются в одной из них, вторая при этом содержится пустой. Как и в прошлом алгоритме, есть несколько корневых объектов, которые ссылаются на другие. В некоторый момент все объекты проверяются на достижимость. В случае, если объект валиден, он дублируется во вторую пустую область памяти, иначе удаляется. В итоге все достижимые объекты скопированы в новое место. Произошла очистка ненужных объектов и уплотнение для избежания фрагментации.