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