Підрахунок посилань

В інформатиці, підрахунок посилань — техніка зберігання кількості посилань, вказівників або хендлерів на ресурс такий як об'єкт, ділянка пам'яті, простір диску або інший ресурс. Також це може означати алгоритм прибирання сміття, який використовує знання кількості посилань для знищення об'єктів на які більше не посилаються.

Використання в прибиранні сміття

Як одна з форм алгоритму прибирання сміття, підрахунок посилань слідкує за кількістю посилань на кожний об'єкт з боку інших об'єктів. Якщо кількість посилань об'єкта досягає нуля, об'єкт стає недосяжним, і може бути знищеним.

Коли об'єкт знищений, всі об'єкти на які він посилався зменшують свої лічильники посилань. Тобто вилучення одного посилання може викликати звільнення великої кількості об'єктів. Зазвичай використовується підхід за яким замість негайного знищення об'єкта при досягненні його лічильником посилань нуля, він додається до списку недоступних об'єктів, і через певні проміжки часу (або за потребою) один або більше елементів з цього списку знищуються.

Простий підрахунок посилань вимагає частих оновлень. Щоразу, коли посилання знищується або змінюється лічильник посилань об'єкта на який воно вело зменшується, і щоразу, коли посилання створюється або копіюється лічильник посилань відповідного об'єкта збільшується.

Підрахунок посилань також використовується в дискових операційних системах і розподілених системах, де прибирання сміття відстеженням із негайним видаленням вивільнених об'єктів також поглинає багато часу через великий розмір графу об'єктів і повільний доступ.

Переваги і недоліки

Головною перевагою підрахунку посилань над прибиранням сміття відстеженням (англ. tracing garbage collection) є те, що об'єкт утилізується одразу ж як на нього перестають посилатися, і в кроковому (англ. incremental) підході, без довгих перерв для циклів прибирання і з чіткою тривалістю життя кожного об'єкта. В реальночасових застосунках або системах з обмеженою пам'яттю, це важливо для підтримки реактивності (здатності до реагування). Підрахунок посилань також одна з найпростіших для здійснення форм прибирання сміття. Він також дозволяє ефективно керувати не тільки ресурсами пам'яті, а й об'єктами операційної системи, які набагато дефіцитніші ніж пам'ять (системи прибирання сміття використовують завершувачі (англ. finalizers) для цього, але відкладена утилізація може викликати проблеми). Зважений підрахунок посилань це хороший вихід в розподілених системах.

Цикли прибирання сміття відстеженням запускаються надто часто, якщо набір живих об'єктів займає більшу частину вільної пам'яті; така техніка потребує більше місце для ефективності. Видатність підрахунку посилань не погіршується із зменшенням вільного місця.

Кількість посилань також є корисною інформацією для інших оптимізацій часу виконання. Наприклад, системи, які активно використовують незмінні об'єкти, такими є багато функціональних мов програмування, можуть зменшити негативний вплив на ефективність через часті копіювання. Однак, якщо ми знаємо, що об'єкт має лише одне посилання (як це буває у більшості в багатьох системах), і це посилання втрачається одночасно зі створенням нового об'єкта (як в додаванні до рядка str ← str + "a"), ми можемо просто замінити цю операцію зміною первісного об'єкта.

Підрахунок посилань має два головні недоліки порівняно з прибиранням сміття відстеженням, обидві вимагають додаткові механізми для поліпшення:

• Часті оновлення які він вимагає є причиною неефективності. Хоча прибирання сміття відстеженням сильно впливає на ефективність через перемикання контексту і похибки кешу, але саме прибирання відбувається нечасто, в той час як доступ до об'єктів постійно. Також, менш важливо, підрахунок посилань вимагає від кожного об'єкта виділення місця від кількість посилань. В прибиранні сміття відстеженням, цю інформацію неявно несуть самі посилання на цей об'єкт, зберігаючи місце, хоча прибиральники сміття відстеженням, особливо кроковий, може вимагати додаткове місця для інших цілей.
• Простий алгоритм описаний вище не може обробити циклічні посилання, тобто об'єкт, який прямо або непрямо посилається на себе. Механізм, що покладається виключно на кількість посилань ніколи не розпізнає циклічні ланцюги об'єктів для вилучення через те, що їхні кількості посилань гарантовано будуть ненульовими. Підхід для цієї ситуації існує, але також збільшує накладні витрати і складність підрахунку посилань — з іншого боку, цей підхід має бути застосований лише для даних, які можуть утворювати цикли, часто це мала підмножина всіх даних. Один з таких підходів це використання слабких посилань.

Представлення графом

При роботі з прибиранням сміття, часто корисно думати про граф посилань, який є орієнтованим графом де вершинами є об'єкти і існує ребро від об'єкта A до об'єкта B якщо A містить посилання на B. Ми також маємо особливі вершини, що представляють локальні змінні і посилання, які утримує рантайм система, ніякі ребра не ведуть до цих вершин, хоча можуть вести з них до інших вузлів.

У цьому припущенні, проста кількість посилань об'єкта це вхідна степінь вершини. Вилучення вершини схоже на прибирання об'єкта. Це може відбутись лише якщо немає вхідних ребер, тобто це не впливає на кількість вихідних ребер будь-якої іншої вершини, але може вплинути на вхідну степінь інших вершин, спричиняючи їх можливе прибирання.

Одна з компонент зв'язності графу містить об'єкти, що не можуть бути прибраними, в той час як інші компоненти зв'язності містять сміття. За природою підрахунку посилань, кожна з компонент зі сміттям має містити не менше одного циклу.

Обробка неефективності через оновлення

Збільшення і зменшення кількості посилань щоразу, коли посилання створюється або знищується може значно зашкодити видатності. Виконання цих операцій не тільки поглинає час, але ще й шкодить видатності кешу і може призвести до конфліктів в конвеєрі. Навіть дії тільки на читання як-от підрахунок довжини списку вимагає великої кількості читань і записів для оновлення посилань при простому підрахунку посилань.

Один простий підхід для компілятора це об'єднати кілька сусідніх оновлень посилань в одне. Це особливо ефективно для посилань, які створюються і швидко знищуються. Однак, треба бути обережним і помістити об'єднане оновлення в потрібне місце задля уникнення передчасного вивільнення.

Метод відкладеного підрахунку посилань Дойтча-Боборова (англ. Deutsch-Bobrow)отримує зиск з того, що більшість оновлень кількість посилань насправді відбувається через посилання збережені в локальних змінних. Алгоритм ігнорує ці посилання, але перед тим як видалити об'єкт з нульовою кількістю посилань, система має перевірити чи немає посилань на цей об'єкт зі стека і регістрів. Перевірка відбувається коли таблиця об'єктів з нульовою кількістю посилань (англ. zero count table) заповнюється. В цій таблиці знаходять об'єкти двох типів: ті, на які посилаються лише локальні зміні і ті, на які ніхто не посилається.

Робота з циклічними посиланнями

Існує багато шляхів виконання задачі знайдення і прибирання циклічних посилань. Один з них це пряма заборона таких циклів. В деяких системах подібних до файлової системи це загальновживане рішення. Іноді, в системах з коротким часом життя і маленькою кількістю циклічного сміття, на цикли просто не звертають уваги, особливо коли система була розроблена використовуючи підхід, який уникає циклічних структур даних коли це можливо.

Інший підхід покладається на періодичне використання прибирання сміття відстеженням для утилізації циклів. Оскільки цикли зазвичай складають відносно малу частину звільненого місця, прибирання циклів може відбуватись нечасто порівняно зі звичайним прибиранням сміття відстеженням.