Что касается разметки (ленивый подход) для сборки мусора в C ++?

Question

Я знаю технику счетчика ссылок, но никогда не слышал о технике меток, пока не прочитал книгу под названием «Концепции языка программирования».
По книге:

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

Из моего ограниченного понимания, умные указатели в библиотеках C ++ используют технику подсчета ссылок. Интересно, есть ли в C ++ библиотека, использующая такого рода реализацию для smart-указателей? И поскольку книга носит чисто теоретический характер, я не мог представить, как осуществляется реализация. Пример для демонстрации этой идеи был бы очень ценным. Пожалуйста, поправьте меня, если я ошибаюсь.

Спасибо

Answer 1

Существует одна сложность использования сборки мусора в C ++, это определить, что является указателем, а что нет.

Если вы можете настроить компилятор для предоставления этой информации для каждого типа объекта, то все готово, но если вы не можете, то вам нужно использовать консервативный подход: это сканирование памяти в поисках любого шаблона, который может выглядеть как указатель Здесь также есть сложность «вставки битов», когда люди вставляют биты в указатели (старшие биты в основном не используются в 64-битном формате) или XOR два разных указателя для «экономии места».

Теперь в C ++ 0x Комитет по стандартизации ввел стандартный ABI, чтобы помочь в реализации сборки мусора. В n3225 вы можете найти его в 20.9.11 Безопасность указателя [util.dynamic.safety] . Это предполагает, что люди будут реализовывать эти функции для своих типов, конечно:

void declare_reachable(void* p); // throw std::bad_alloc
template <typename T> T* undeclare_reachable(T* p) noexcept;

void declare_no_pointers(char* p, size_t n) noexcept;
void undeclare_no_pointers(char* p, size_t n) noexcept;

pointer_safety get_pointer_safety() noexcept;

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

Наконец, существует множество стратегий для сбора мусора: подсчет ссылок (с алгоритмами обнаружения циклов) и Mark And Sweep - это основные разные системы, но они бывают разных типов (поколение или нет, копирование / сжатие или нет, .. .).

Answer 2

Несмотря на то, что они, возможно, уже обновили его, Mozilla Firefox использовал гибридный подход, при котором интеллектуальные указатели с подсчетом ссылок использовались, когда это было возможно, с сборщиком мусора с разметкой и уборкой, работающим параллельно для очистки циклов ссылок. Возможно, другие проекты приняли этот подход, хотя я не совсем уверен.

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

Другая сложность этого подхода заключается в том, что C ++ допускает необработанные арифметические операции с указателями, что значительно усложняет реализацию любого сборщика мусора. Эту проблему можно решить консервативно (например, посмотрите на GC Boehm), хотя это является серьезным препятствием для создания системы такого рода.