Как быстро работает сжатие кучи?

Сжатие означает перемещение объектов в ОЗУ таким образом, что некоторые объекты удаляются (мертвые объекты, которые должен восстанавливать сборщик мусора), а все оставшиеся объекты становятся смежными в ОЗУ.

В большинстве своем уплотняющая сборка мусора распределяет объекты в единственной непрерывной области, полученной из операционной системы. В этом случае уплотнение похоже на удаление мертвых объектов, а затем выталкивание всех оставшихся живых объектов «влево», выдавливание отверстий. Если сборщик мусора работает путем уплотнения, то выделение - это просто вопрос перемещения указателя «конца выделенной области». Синтетически внутри области выделения есть указатель, так что свободная область состоит из байтов после этого указателя. Чтобы выделить место для объекта, указатель просто перемещается вверх на новый размер объекта. Иногда сборщик мусора решает, что пора запускать, обнаруживает мертвый объект, выжимает дыры и, таким образом, опускает указатель выделения.

Прирост производительности от уплотнения GC происходит из нескольких источников:

• Для распределения нет необходимости находить подходящую «дыру»: по конструкции свободное пространство всегда представляет собой одну большую область, и достаточно просто переместить указатель вверх.
• Отсутствует фрагментация: уплотнение перемещает все живые объекты вместе, но это можно рассматривать как перемещение всех отверстий вместе в единое большое свободное пространство.
• Местоположение улучшено. Перемещение живых объектов в соседние области улучшает поведение кэш-памяти.В частности, алгоритмы уплотнения, как правило, сохраняют объекты в их соответствующем порядке размещения (объекты сдвигаются, но не меняются местами), что, как сообщается, эвристически хорошо подходит для большинства приложений.

Если операционная система отказывается предоставить одну область распределения, вместо этого выдавая несколько блоков, тогда все становится немного сложнее и может начать выглядеть как проблема упаковки в контейнеры, потому что уплотняющий GC должен решить, в какой блок помещается каждый живой объект. Однако сложность упаковки в контейнеры заключается в нахождении «идеального» соответствия в общем случае; приблизительное решение уже достаточно для распределителя памяти.

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

Дополнительная сложность исходит от коллекционеров поколений , которые большую часть времени стараются оставить большинство объектов нетронутыми, работая преимущественно только с молодыми объектами. Здесь это означает уплотнение только конца кучи; полное уплотнение применяется редко. Дело в том, что полное уплотнение, хотя и линейное, все же может вызвать заметную паузу. Generation GC старается делать такие паузы реже. И снова книгу Джонса и Линса нужно прочитать.