Как реализовать сборщик мусора?

Question

Может кто-нибудь указать мне хороший источник о том, как реализовать сборку мусора? Я делаю подобный языку интерпретируемый язык. В настоящее время он использует подсчет ссылок, но, конечно, он не может освободить циклически зависимые объекты.

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

Я читал некоторые языки с подсчетом ссылок, использующие круговое обнаружение ссылок, которое я мог бы использовать. Я знаю, что могу использовать свободно доступные коллекционеры, такие как Boehm, но я бы хотел научиться делать это сам.

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

Answer 1

Может ли кто-нибудь указать мне хороший источник информации о том, как реализовать сборку мусора?

Есть много продвинутых материалов о сборке мусора. Сборник мусора великолепен. Но я обнаружил, что там было очень мало базовой вводной информации, поэтому я написал несколько статей об этом. Создание прототипа сборщика мусора с разметкой описывает минимальный сборщик мусора с разметкой, написанный на F #. Совместный сборщик мусора описывает более продвинутый параллельный сборщик. HLVM - это написанная мною виртуальная машина, включающая сборщик остановок, который обрабатывает потоки.

Самый простой способ реализовать сборщик мусора:

1. Убедитесь, что вы можете сопоставить глобальные корни. Это локальные и глобальные переменные, которые содержат ссылки в куче. Для локальных переменных поместите их в теневой стек на время их действия.

2. Убедитесь, что вы можете пройти через кучу, например, каждое значение в куче является объектом, который реализует метод Visit, который возвращает все ссылки из этого объекта.

3. Сохранить набор всех присвоенных значений.

4. Выделите, вызвав malloc и вставив указатель в набор всех выделенных значений.

5. Когда общий размер всех выделенных значений превышает квоту, снимите отметку, а затем разверните фазы. Это рекурсивно пересекает кучу, накапливая набор всех достижимых значений.

6. Установленная разница назначенных значений за вычетом достижимых значений является набором недоступных значений. Итерируйте их, вызывая free и удаляя их из набора выделенных значений.

7. Установите квоту, равную удвоенному общему размеру всех выделенных значений.

Answer 2

Проверьте следующую страницу.У него много ссылок.http://lua -users.org / вики / GarbageCollection

Answer 3

Как предположил Делнан, я начал с очень наивного алгоритма трехцветной метки и развертки Stop-the-World. Мне удалось сохранить объекты в наборах, сделав их узлами связанного списка, но он добавляет много данных к каждому объекту (виртуальный указатель, два указателя на узлы, одно перечисление для хранения цвета). Это работает отлично, без потери памяти на valgrind :) Отсюда я мог бы попытаться добавить бесплатный список для переработки, или что-то вроде того, что определяет, когда удобно остановить мир, или постепенный подход, или специальный распределитель для избегать фрагментации или чего-то еще. Если вы можете указать мне, где найти информацию или совет (я не знаю, можете ли вы прокомментировать ответ на вопрос) о том, как делать эти вещи или что делать, я был бы очень благодарен. Тем временем я проверю GC Луа.

Answer 4

Одна вещь, о которой я еще не упоминал, это использование дескрипторов памяти. Можно избежать необходимости удваивать память (как это было бы необходимо для алгоритма копирования в стиле Чейни), если каждая ссылка на объект является указателем на структуру, которая содержит реальный адрес рассматриваемого объекта. Использование дескрипторов для объектов памяти сделает некоторые процедуры немного медленнее (необходимо перечитывать адрес памяти объекта каждый раз, когда что-то могло случиться, что могло бы его переместить), но для однопоточных систем, где сборка мусора будет происходить только в предсказуемые моменты времени, это не является большой проблемой и не требует специальной поддержки компилятора (многопоточные системы GC, вероятно, потребуют метаданных, сгенерированных компилятором, независимо от того, используют ли они дескрипторы или прямые указатели).

Если используются дескрипторы и используется один связанный список для живых дескрипторов (одно и то же хранилище можно использовать для хранения связанного списка для мертвых дескрипторов, нуждающихся в перераспределении), можно, отметив основную запись для каждого дескриптора, пройти список дескрипторов в порядке размещения и скопировать блок, указанный этим дескриптором, в начало кучи. Поскольку дескрипторы будут скопированы по порядку, не будет необходимости использовать вторую область кучи. Кроме того, поколения могут поддерживаться путем отслеживания некоторых указателей вершины кучи. При уплотнении памяти начните с компактификации элементов, добавленных с момента последнего ГХ. Если это не освобождает достаточно места, компактифицируйте предметы, добавленные с последнего уровня 1 GC. Если это не освобождает достаточно места, компактифицируйте все. Фаза маркировки, вероятно, должна была бы воздействовать на объекты всех поколений, но дорогостоящая стадия уплотнения не будет.

На самом деле, используя подход, основанный на дескрипторе, если кто-то маркирует вещи всех поколений, можно при желании вычислить на каждом ГХ пропускную способность, сколько места может быть освобождено в каждом поколении. Если половина объектов в Gen2 мертва, возможно, стоит сделать коллекцию Gen2, чтобы уменьшить частоту коллекций Gen1.

Answer 5

Я реализовал копирующий сборщик мусора в стиле Чейни в C примерно в 400 SLOC. Я сделал это для статически типизированного языка, и, к моему удивлению, более сложная часть заключалась в передаче информации о том, что является указателем, а что нет. В динамически типизированном языке это, вероятно, проще, поскольку вы уже должны использовать некоторую форму схемы тегирования.

Выходит также новая версия стандартной книги по сбору мусора: «Справочник по сбору мусора: искусство автоматического управления памятью», автор Jones, Hosking, Moss . (Сайт Amazon UK сообщает 19 августа 2011 года.)

Answer 6

Реализация сборки мусора в Лиспе

Здание ЛИСП | http://www.lwh.jp/lisp/

Аркадия | https://github.com/kimtg/arcadia

Answer 7

Чтение Управление памятью: алгоритмы и реализации на C / C ++ . Это хорошее место для начала.

Answer 8

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