Сжатие означает перемещение объектов в ОЗУ, в результате чего некоторые объекты удаляются (мертвые объекты, которые GC должен вернуть), а все оставшиеся объекты становятся смежными в ОЗУ.
Большинство компактных GC работают, выделяя объекты в одной непрерывной области, полученной из операционной системы. Сжатие тогда похоже на удаление мертвых объектов, а затем подталкивание всех оставшихся живых объектов «влево», выдавливая отверстия. Если GC работает с уплотнением, то распределение - это просто вопрос перемещения указателя «конец выделенной области». Синтетически, внутри области выделения есть указатель, так что свободная область состоит из байтов после этого указателя. Чтобы выделить место для объекта, указатель просто перемещается вверх на новый размер объекта. Иногда GC решает, что пора бежать, обнаруживает мертвый объект, выдавливает отверстия и таким образом понижает указатель выделения.
Прирост производительности от сжатия GC происходит из нескольких источников:
- Для выделения не нужно искать подходящую "дыру": по конструкции свободное пространство всегда представляет собой одну большую область, и достаточно просто переместить указатель вверх.
- Нет фрагментации: сжатие перемещает все живые объекты вместе, но это можно рассматривать как перемещение всех отверстий вместе в одно большое свободное пространство.
- Местность улучшена. Перемещая живые объекты в соседние области, улучшается поведение в отношении кэш-памяти. В частности, алгоритмы сжатия имеют тенденцию сохранять объекты в их соответствующем порядке размещения (объекты скользят, но не меняются местами), что, как сообщается, является эвристически хорошим для большинства приложений.
Если операционная система отказывается предоставить одну область выделения, вместо этого получая несколько блоков, то все становится немного более сложным и может начать выглядеть как проблема упаковки бина, потому что сжатие GC затем должен решить, в какой блок входит каждый живой объект. Однако сложность бин-упаковки заключается в поиске «идеального» соответствия в общем случае; приблизительное решение уже достаточно для распределителя памяти.
Алгоритмическая сложность алгоритма сжатия заключается в обновлении всех указателей, чтобы они указывали на новое местоположение объекта. Посредством строгой типизации виртуальная машина .NET может однозначно решить, является ли каждое слово в ОЗУ указателем или нет, но эффективное обновление всех указателей без использования слишком большого количества ОЗУ может быть затруднительным. H.B.M. Джонкерс описал удивительно умный алгоритм для этого в «Алгоритме быстрого сжатия мусора» (Письма обработки информации, том 9, номер 1, 1979, стр. 26-30). Я не смог найти копию этой статьи в обширном Интернете, но алгоритм описан в книге Джоунса и Линса "Сборка мусора" (раздел 5.6). Я настоятельно рекомендую эту книгу всем, кто интересуется пониманием сборщиков мусора. Алгоритм Джонкерса требует двух линейных проходов для живых объектов и оказывается простым в реализации (несколько десятков строк кода, не более; самая сложная часть - понять, почему он работает).
Дополнительная сложность исходит от коллекционеров поколений , которые пытаются большую часть времени оставлять нетронутыми большинство объектов, работая преимущественно только с молодыми объектами. Здесь это означает сжатие только конца кучи; полное уплотнение применяется редко. Дело в том, что полное уплотнение, хотя и линейное, все же может вызвать заметную паузу. Поколение GC пытается сделать такие паузы реже. И снова книгу Джоунса и Линса нужно обязательно прочитать.