Каковы преимущества и недостатки совместного и отдельного разделения битов для сбора мусора?

Question

я смотрел видео Google IO 2008 — Внутреннее устройство виртуальной машины Dalvik чтобы понять, как работает Dalvik VM и почему эти люди предпочитают Dalvik VM JVM для Android.Я обнаружил, что Android использует отдельную память для информации о мусоре об объектах, в отличие от JVM, где у нас есть биты метки (биты, сообщающие, способен ли объект собирать мусор или нет) вместе с объектами.

Может ли кто-нибудь подробно рассказать мне, каковы преимущества и недостатки наличия отдельной памяти для битов меток и отсутствия отдельной памяти для битов меток?

Я не смог увидеть эту разницу, просматривая видео.

Answer 1

Некоторые преимущества отдельного растрового изображения:

• Гораздо плотнее.Типичному сборщику мусора требуется около восьми бит метаданных сборщика мусора, но из-за выравнивания заголовок внутри объекта может округлить эту память до 32 битов.
• Некоторые операции, в частности подметание, становятся быстрее.Частично это связано с тем, что более плотное (см. выше) растровое изображение означает меньший трафик памяти и лучшее использование кэша, а также потому, что некоторые операции (например,обнуление всех битов метки) в этом формате можно векторизовать.(Другие части GC должны быть спроектированы так, чтобы использовать эту возможность.)
• Если вы fork() в системе Unix отдельный битовый знак позволяет лучше использовать копирование при записи:Страницы, содержащие объекты, могут оставаться общими.

Некоторые преимущества битов меток внутри объекта:

• В зависимости от схемы, используемой для связывания объектов с растровыми изображениями, получение бита метки для объекта и наоборот может быть довольно сложным и/или медленным.С другой стороны, доступ к заголовку внутри объекта тривиален.
• Упрощенное управление памятью:Нет необходимости создавать отдельный аллокатор нужного размера и поддерживать его синхронизацию.
• Многие быстрые схемы поиска растровых изображений объектов и наоборот весьма ограничительны в других отношениях.Например, если вы создаете растровое изображение для каждой страницы и сохраняете указатель растрового изображения в начале страницы, у вас возникает проблема с сохранением объектов, размер которых превышает страницу.

Answer 2

Отдельные биты метки работают за счет наличия массива битов, где каждый бит представляет адрес в куче, который может запустить объект.Например, предположим, что объем кучи равен 65536 байтам, и все объекты выровнены по 16-байтовым границам, тогда в куче имеется 4096 адресов, которые могут быть началом объекта.Это означает, что массив должен содержать 4096 бит, которые могут быть эффективно сохранены в виде 512 байт или 64 целых чисел без знака размером 64 бита.

Биты метки внутри объекта работают за счет того, что одному биту каждого заголовка каждого объекта присваивается значение 1, если объект помечен, и 0 в противном случае.Обратите внимание, что для этого требуется, чтобы у каждого объекта была выделенная область заголовка.Среды выполнения, такие как JVM и .NET, добавляют заголовки к объектам, так что вы, по сути, получаете место для бита метки бесплатно.

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

Сбор мусора Mark & sweep разделен на два этапа:разметка и подметание.Маркировка с использованием битов метки внутри объекта выполняется прямолинейно (псевдокод).:

if not obj.is_marked():
    obj.mark()
    mark_stack.append(obj)

Используя отдельный массив для хранения битов меток, мы должны преобразовать адрес и размер объектов в индексы в битовом массиве и установить соответствующие биты равными 1:

obj_bits = obj.size_in_bytes() / 16
bit_idx = (obj - heap.start_address()) / 16
if not bitarr.bit_set(bit_idx):
    bitarr.set_range(bit_idx, obj_bits)
    mark_stack.append(obj)

Итак, в нашем примере, если длина объекта составляет 128 байт, в массиве битов будет задано 8 бит.Очевидно, что использовать биты меток внутри объекта намного проще.

Но отдельные биты метки приобретают некоторый импульс при подметании.Очистка включает в себя сканирование всей кучи и поиск непрерывных областей памяти, которые не помечены и, следовательно, могут быть восстановлены.Используя биты меток внутри объекта, это примерно выглядело бы так:

iter = heap.start_address()
while iter < heap.end_address():
    # Scan til the next unmarked object
    while iter.is_marked():
        iter.unmark()
        iter += iter.size()
        if iter == heap.end_address():
            return
    # At an unmarked block
    start = iter
    # Scan til the next marked object
    while iter < heap.end_address() and not iter.is_marked():
        iter += iter.size()
    size = iter - start
    # Reclaim the block
    heap.reclaim(start, size)

Обратите внимание, как итерация переходит от объекта к объекту в iter += iter.size() линии.Это означает, что время выполнения фазы развертки пропорционально общему количеству активных объектов и объектов мусора.

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

Рассмотрим еще раз кучу 65536.Предположим, он содержит 4096 объектов, которые все являются мусором.Перебираем 64 64-битных целых числа в массиве mark bits и видим, что все они равны 0, очевидно, что это очень быстро.Следовательно, фаза подметания потенциально может быть намного быстрее при использовании отдельных битов метки.

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