Что вы покупаете?

Я чувствую, что мне не хватает чего-то больно простого, но я пытаюсь понять, как пометить и собрать мусорную сборку в проекте Andrew Appel Modern Compiler в книге ML, и там есть небольшой абзац внутри раздела Mark and Sweep под названием "Сторнирование указателя" (270).

В этот момент я думаю, что понимаю, как это работает. В двух словах, когда вы пересекаете график, вы переворачиваете все указатели, чтобы ваш предшественник находился внутри вашего набора полей. Затем, когда вы закончите с заданным элементом, вы переверните указатели назад, чтобы они снова указывали в нужное место.

Если это правильно, что именно он вас купит? Аппель пытается объяснить это, но я не полностью понимаю его формулировку.

Ответы

Ответ 1

При маркировке объекты делятся на три категории:

  • Объекты, которые не были отмечены
  • Объекты, которые были помечены, но могут указывать на немаркированные объекты
  • Объекты, отмеченные и указывающие только на отмеченные объекты

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