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

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

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

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

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

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

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

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

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

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

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

• The Memory Manager Reference: Beginner's Guide: Recycling: Reference Counts
• Minimizing Reference Count Updating with Deferred and Anchored Pointers for Functional Data Structures, Henry G. Baker
• Concurrent Cycle Collection in Reference Counted Systems, David F. Bacon
• An On-the-Fly Reference-Counting Garbage Collector for Java, Yossi Levanoni and Erez Petrank
• Atomic Reference Counting Pointers: A lock-free, async-free, thread-safe, multiprocessor-safe reference counting pointer, Kirk Reinholtz
• Extending and Embedding the Python Interpreter: Extending Python with C or C++: Reference Counts, Guido van Rossum
• Down for the count? Getting reference counting back in the ring, Rifat Shahriyar, Stephen M. Blackburn and Daniel Frampton