Подсчёт ссылок

Подсчёт ссылок (англ. reference counting) — техника хранения количества ссылок, указателей, или хендлеров на какой-то ресурс, например на объект или на блок памяти. Обычно используется как средство освобождения объектов, которые больше не нужны и на них больше нет ссылок.

Использование в сборке мусора

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

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

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

Достоинства и недостатки

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

Счетчики ссылок также полезны в качестве входной информации для различных оптимизаторов времени исполнения. Например системы сильно зависимые от неизменяемых объектов(многие функциональные языки) могут проигрывать в производительности из-за частых операций копирования. Однако, если мы знаем что какой-то объект имеет только одну ссылку (Это верно для большинства разных систем), и эта ссылка потеряна а в то же время создан похожий новый объект (как в выражении по прибавлению строки str ← str + "a"), мы можем заменить эту операцию модификацией (mutation) исходного объекта.

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

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

Представление в виде графа

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

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