Решит ли использование хеш-таблицы в сборщике мусора проблему мировой маркировки и очистки?

13

В алгоритме сборки мусора mark-sweep-compact вы должны останавливать мир при перемещении объектов, потому что ссылочный граф становится непоследовательным, и вы должны заменить значения всех ссылок, указывающих на объект.

Но что если бы у вас была хеш-таблица с идентификатором объекта в качестве ключа и указателем в качестве значения, а ссылки указывали бы на указанный идентификатор вместо адреса объекта ... тогда для исправления ссылок потребуется изменить только одно значение, а пауза потребуется только в том случае, если объект пытается быть записан во время копирования ...

Есть ли ошибка в моей мысли?

mrpyo
источник

Ответы:

19

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

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

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


источник
Что ж, у нас сегодня много памяти, так что мы можем иметь, скажем, таблицу 50 Мб и хеш может быть простым по модулю, поэтому только одна инструкция ...
mrpyo
3
@mrpyo извлечение размера хеш-таблицы, операция по модулю, разыменование из смещения хеш-таблицы для получения фактического указателя объекта, разыменование самого объекта. Плюс возможно какой-то регистр тасовок. Мы в конечном итоге на 4+ инструкции. Кроме того, у этой схемы есть проблемы, связанные с локальностью памяти: теперь и кеш-таблица, и сами данные должны помещаться в кеш.
amon
@mrpyo Вам нужна одна запись (идентификатор объекта -> текущий адрес) для каждого объекта, верно? И независимо от того, насколько дешева хеш-функция, у вас будут коллизии, и вам нужно их разрешать. Также то, что сказал Амон.
@amon Это только вопрос времени, когда процессоры имеют кэш-память объемом 50 МБ или более :)
Móż
1
@ Ӎσᶎ К тому времени, когда мы можем разместить 50 МБ транзисторов на чипе, при этом время задержки будет достаточно низким для того, чтобы он работал как кэш-память L1 или L2 (кэш-память L3 уже имеет размер до 15 МБ, но, как правило, вне чипа AFAIK и далеко с худшей задержкой, чем L1 и L2), у нас будет соответственно огромное количество основной памяти (и данных, которые будут в нее помещены). Таблица не может быть фиксированного размера, она должна расти вместе с кучей.
19

Все проблемы в информатике могут быть решены с помощью другого уровня косвенности ... за исключением проблемы слишком большого количества уровней косвенности

Ваш подход не сразу решает проблему сбора мусора, а только перемещает ее на один уровень вверх. И какой ценой! Теперь каждый доступ к памяти проходит через разыменование другого указателя. Мы не можем кэшировать местоположение результата, потому что оно могло быть перемещено в это время, мы всегда должны проходить через идентификатор объекта. В большинстве систем это косвенное обращение недопустимо, и предполагается, что остановка мира будет иметь более низкие общие затраты времени выполнения.

Я сказал, что ваше предложение только перемещает проблему, но не решает ее. Проблема заключается в повторном использовании идентификаторов объектов. Идентификаторы объектов теперь являются нашими эквивалентами указателей, а количество адресов ограничено. Возможно (особенно в 32-битной системе), что за время жизни вашей программы будет создано больше объектов INT_MAX, например, в цикле, подобном

while (true) {
    Object garbage = new Object();
}

Если мы просто увеличиваем ID объекта для каждого объекта, в какой-то момент у нас закончатся ID. Поэтому мы должны выяснить, какие идентификаторы все еще используются, а какие бесплатны, чтобы их можно было вернуть. Звучит знакомо? Теперь мы вернулись на круги своя.

Амон
источник
Можно предположительно использовать идентификаторы, которые являются просто «достаточно большими», скажем, 256-битными бигнумами? Я не говорю, что эта идея в целом хороша, но вы почти наверняка можете обойтись повторным использованием IDS.
Vality
@Vality реально да - насколько мы можем видеть, это обойдёт проблему повторного использования ID. Но это всего лишь еще один аргумент «640K должно хватить на всех», и он фактически не решает проблему. Более катастрофический аспект заключается в том, что размер всех объектов (и хеш-таблицы) должен был бы увеличиться, чтобы вместить эти негабаритные псевдо-указатели, и что во время хеш-доступа нам нужно сравнить этот bigint с другими идентификаторами, которые, вероятно, будут включать несколько регистров. и выполнить несколько инструкций для выполнения (на 64-битной версии: 8-кратная загрузка, 4-кратное сравнение, 3-кратное увеличение и увеличение в 5 раз по сравнению с исходными целыми числами).
Amon
Да, через некоторое время у вас закончатся идентификаторы, и вам потребуется изменить все из них, что потребует паузы. Но, возможно, это будет редкое событие ...
mrpyo
@amon Очень согласен, все очень хорошие моменты, гораздо лучше иметь действительно устойчивую систему, я согласен. Это будет невыносимо медленно, что бы вы ни делали, в любом случае это интересно только в теории. Лично я не большой поклонник сборщика мусора в любом случае: P
Vality
@amon: в мире существует больше кода, чем просто этот, который может работать не так, как только вы закроете 64-битный идентификатор (584 года наносекунд), и вы, вероятно, сможете организовать выделение памяти на 1 нс, особенно если вы не осколите глобальный счетчик что выплевывает идентификаторы!). Но, конечно, если вам не нужно полагаться на это, то вам не нужно.
Стив Джессоп
12

В вашей мысли нет ошибки, вы только что описали нечто очень близкое к тому, как работал оригинальный сборщик мусора Java

Исходная виртуальная машина Java [6] и некоторые виртуальные машины Smalltalk используют косвенные указатели, называемые дескрипторами в [6], для ссылки на объекты. Дескрипторы позволяют легко перемещать объекты во время сборки мусора, поскольку с помощью дескрипторов имеется только один прямой указатель на каждый объект: один в его дескрипторе. Все остальные ссылки на объект непрямы через хандл. В таких системах памяти, основанных на дескрипторах, в то время как адреса объектов меняются в течение времени жизни объектов и поэтому не могут использоваться для хеширования, адреса дескрипторов остаются постоянными.

Пространственное и временное хеширование объектов, собранных мусором

В текущей реализации Sun виртуальной машины Java ссылка на экземпляр класса представляет собой указатель на дескриптор, который сам является парой указателей: один на таблицу, содержащую методы объекта, и указатель на объект Class, который представляет тип объекта, а другой - память, выделенная из кучи Java для данных объекта.

Спецификация виртуальной машины Java (1997)

Так что это работает, это было опробовано, и его неэффективность привела к разработке систем меток и разверток поколений.

Пит Киркхэм
источник
Предположительно, эти ручки не были ключами в хеш-таблице (как в вопросе), хотя? Там нет необходимости, просто структура, содержащая указатель. Тогда все маркеры имеют одинаковый размер, поэтому они могут быть выделены из распределителя кучи. Который по своей природе не нуждается во внутреннем уплотнении, так как он не становится фрагментированным. Вы можете оплакивать неспособность больших блоков, используемых этим распределителем, быть перемещенными самим. Что может быть решено с помощью другого уровня косвенности ;-)
Стив Джессоп
@SteveJessop да, в реализации gc не было хеш-таблицы, хотя значением дескриптора было также значение, возвращаемоеObject.getHashCode()
Пит Киркхам