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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки