В информатике алгоритм mark-compact — это тип алгоритма сборки мусора, используемый для освобождения недоступной памяти . Алгоритмы Mark-Compact можно рассматривать как комбинацию алгоритма Mark-Sweep и алгоритма копирования Чейни . Сначала помечаются доступные объекты, затем на этапе сжатия доступные (отмеченные) объекты перемещаются в начало области кучи. Уплотнение сборки мусора используется современными JVM , Microsoft Common Language Runtime и компилятором Glasgow Haskell .
После маркировки живых объектов в куче тем же способом, что и при использовании алгоритма маркировки-очистки , куча часто оказывается фрагментированной . Цель алгоритмов mark-compact — сдвинуть живые объекты в памяти вместе, чтобы исключить фрагментацию. Задача состоит в том, чтобы правильно обновить все указатели на перемещенные объекты, большинство из которых после сжатия получат новые адреса в памяти. Проблема обработки обновлений указателя решается по-разному.
Алгоритм на основе таблиц был впервые описан Хэддоном и Уэйтом в 1967 году. [1] Он сохраняет относительное расположение живых объектов в куче и требует лишь постоянного объема накладных расходов.
Уплотнение происходит снизу вверх (низкие адреса) к верху (высокие адреса). При обнаружении живых (то есть помеченных) объектов они перемещаются по первому доступному младшему адресу, а запись добавляется в таблицу разрывов с информацией о перемещении. Для каждого действующего объекта запись в таблице разрывов состоит из исходного адреса объекта до уплотнения и разницы между исходным адресом и новым адресом после уплотнения. Таблица разрывов хранится в сжимаемой куче, но в области, помеченной как неиспользуемая. Чтобы гарантировать, что сжатие всегда будет успешным, минимальный размер объекта в куче должен быть больше или равен размеру записи таблицы разрывов.
По мере сжатия перемещенные объекты копируются в нижнюю часть кучи. В конце концов объект необходимо будет скопировать в пространство, занимаемое таблицей разрывов, которую теперь необходимо переместить в другое место. Эти перемещения таблицы разрывов ( авторы называют их перекатыванием таблицы ) приводят к тому, что записи о перемещении становятся неупорядоченными, что требует сортировки таблицы разрывов после завершения уплотнения. Стоимость сортировки таблицы разрывов равна O ( n log n ), где n — количество живых объектов, найденных на этапе маркировки алгоритма.
Наконец, записи перемещения таблицы разрывов используются для настройки полей указателей внутри перемещаемых объектов. Живые объекты проверяются на наличие указателей, которые можно найти в отсортированной таблице разрывов размера n за время O(log n ), если таблица разрывов отсортирована, при общем времени работы O ( n log n ). Затем указатели корректируются на величину, указанную в таблице перемещения.
Чтобы избежать сложности O ( n log n ), алгоритм LISP 2 использует три разных прохода по куче. Кроме того, объекты кучи должны иметь отдельный слот указателя пересылки, который не используется за пределами сборки мусора.
После стандартной маркировки алгоритм выполняется в следующие три прохода:
Этот алгоритм имеет размер O ( n ) в зависимости от размера кучи; его сложность выше, чем у табличного подхода, но n в табличном подходе — это размер только используемого пространства, а не всего пространства кучи, как в алгоритме LISP2. Однако алгоритм LISP2 проще реализовать.
Алгоритм сжатия Compressor [2] имеет наименьшую сложность среди известных сегодня алгоритмов сжатия. Он расширяет сборку мусора IBM для Java. [3] Последовательная версия Compressor поддерживает карту перемещения, которая сопоставляет старый адрес каждого объекта с его новым адресом (т. е. его адрес до сжатия сопоставляется с адресом после сжатия). На первом проходе сопоставление вычисляется для всех объектов в куче. На втором проходе каждый объект перемещается на новое место (сжимается до начала кучи), а все указатели внутри него изменяются в соответствии с картой перемещения.
Вычисление карты перемещения на первом проходе можно сделать очень эффективным, работая с небольшими таблицами, не требующими прохода по всей куче. Это позволяет снизить сложность компрессора, включая один проход по небольшим таблицам и один проход по всей куче. Это представляет собой наиболее известную сложность алгоритмов уплотнения.
У Compressor также есть параллельная версия, в которой несколько потоков сжатия могут работать вместе для параллельного сжатия всех объектов. У Compressor также есть параллельная версия, в которой потоки сжатия могут работать одновременно с программой, осторожно позволяя программе получать доступ к объектам по мере их перемещения к началу кучи. Параллельная и параллельная версии Compressor используют примитивы виртуальной памяти.