Как быстро выполняется сжатие кучи?

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

Ответ 1

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

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

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

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

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

Алгоритмическая сложность алгоритма уплотнения заключается в обновлении всех указателей, так что они указывают на новое местоположение объекта. Благодаря строгой типизации виртуальная машина .NET может однозначно решить, является ли каждое слово в ОЗУ указателем или нет, но эффективное обновление всех указателей без использования слишком большого количества ОЗУ может быть сложным. H.B.M. Йонкерс описал удивительно умный алгоритм для этого в "Алгоритме уплотнения быстрого мусора" ( "Обработка информации", том 9, номер 1, 1979, стр. 26-30). Я не мог найти копию этой статьи в Vast Internet, но алгоритм описан в "Коллекция мусора" от Jones and Lins ( раздел 5.6). Я горячо рекомендую эту книгу всем, кто заинтересован в понимании сборщиков мусора. Алгоритм Йонкерса требует двух линейных проходов на живых объектах и оказывается легко реализуемым (несколько десятков строк кода, не более, самая сложная часть - понимание того, почему он работает).

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