Подтвердить что ты не робот

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 2

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

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

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

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

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

  • Сохраняйте набор всех выделенных значений.

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

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

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

  • Установите квоту в два раза больше общего размера всех выделенных значений.

Ответ 4

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

Также появилась новая версия стандартной книги по сборке мусора: "Руководство по сборке мусора: искусство автоматического управления памятью" Джонса, Хоскинг, Мосс. (Сайт Amazon UK говорит 19 августа 2011 года.)

Ответ 5

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

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

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

Ответ 8

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