Когда сборщик мусора сжимает объекты в куче, он изменяет ссылки в стеке?

18

Это кажется простым вопросом, но после долгих чтений на эту тему я так и не нашел однозначного ответа (возможно, потому, что это так просто).

У меня такой вопрос: когда сборщик мусора сжимает объекты в куче, как обновляются ссылки на эти объекты в стеке? Я могу придумать два возможных решения:

  1. Пройдите через стек (и ссылки в куче) и обновите ссылку, чтобы указать новое местоположение объекта. По аналогии с переездом это похоже на отправку письма всем, у кого есть ваш адрес, и просьбу обновить адресную книгу на ваш новый адрес.
  2. Обеспечить какую-то таблицу поиска. Это все равно, что оставить адрес пересылки в местном почтовом отделении.

Сборщики мусора преимущественно используют один из этих двух методов? Какой-то другой метод? И то и другое?

garbage-collection todorojo
источник
См. Stackoverflow.com/questions/3799203/… и en.wikipedia.org/wiki/…
Gort the Robot
@ StevenBurnap поправьте меня, если я ошибаюсь, но я верю, что у темы, на которую вы ссылались, не было однозначных ответов. Похоже, они тоже размышляли над этим вопросом. Возможно, я неправильно прочитал. Если бы они дали ответ на вопрос, если вы не возражаете, я думаю, что было бы полезно обобщить здесь ответ для будущих пользователей SE (и меня!)
todorojo
Термин для того, о чем вы говорите, это «движущийся сборщик мусора». Честно говоря, я не знаю, насколько они обычно используются.
Gort the Robot

Ответы:

9

У меня нет конкретных знаний по этому вопросу, но я понимаю, что обычно используется первый метод.

Сборщик мусора должен в любом случае проанализировать стек, чтобы найти, какие вещи в куче упоминаются из стека. Как только он решает что-то переместить, ему все равно приходится исправлять ссылки на него, и нет никакой причины различать кучу и стек в этой точке.

Подход таблицы поиска в принципе может работать. Однако для этого все обращения к указателю должны быть выполнены в 2 этапа. Это будет иметь огромное влияние на производительность при нормальном времени выполнения. Особенно для случая использования многих мелких предметов. (Это тот случай, когда современные программы GC обычно бьют счетчик ссылок.)

btilly
источник
3
Я хотел бы добавить, что я думаю, что GC, вероятно, стараются не перемещать вещи в кучу, если они не должны. В современном многопроцессорном мире это должно быть кошмаром синхронизации, когда им нужно обновить все ссылки на что-то в куче, пока работает программа, использующая эти ссылки. Таблица поиска упростила бы это, но я думаю, что это скорее исключение, чем норма, поэтому большинству сборщиков мусора, вероятно, придется заблокировать некоторые ссылки, переместить память, а затем обновить ссылки. +1 интересный вопрос, +1 хороший ответ.
ГленПетерсон
3
@GlenPeterson Многие GC действительно не перемещают вещи в кучу, и не сталкиваются с этой проблемой. Но компактный GC по определению перемещает живые объекты вокруг, чтобы дефрагментировать память.
Btilly
@GlenPeterson - это хорошее наблюдение, что перемещение объектов в куче - огромная проблема с синхронизацией, это часто упускается из виду, хотя сжатие GC из-за этого оказывает огромное волновое воздействие на рабочий процесс. Это единственная причина, по которой людям говорят делать все возможное, чтобы объекты были как можно более кратковременными, чтобы избежать больших обновлений кучи, приводящих к сжатию с сохранением длинного мьютекса. Незнание поведения этих вещей может привести к тому, что с любовью называют GC Freakout Mode.
Джимми Хоффа
2
Оригинальный Macintosh и Palm OS использовали подход таблицы поиска для управления памятью. Указатели на стол назывались ручками. Перемещающийся GC должен знать местонахождение абсолютно положительно каждой ссылки на любой объект, который он перемещает; использование одной таблицы для таких целей значительно упрощает работу.
Суперкат