Подсчет ссылок: техника отслеживания ресурсов в программировании

Введение

Техника отслеживания ресурсов программного обеспечения

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

Интерпретация графика

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

Решение проблемы неэффективности обновлений

Увеличение и уменьшение счетчиков ссылок при каждом создании или уничтожении ссылки может существенно снизить производительность. Эти операции не только занимают время, но и ухудшают производительность кэша и могут приводить к задержкам в конвейере. Даже операции только для чтения, такие как вычисление длины списка, требуют большого количества операций чтения и записи для обновления ссылок при наивном подсчете ссылок. Один из простых приемов – компилятору объединять несколько соседних обновлений счетчиков ссылок в одно. Это особенно эффективно для ссылок, которые создаются и быстро уничтожаются. Однако необходимо следить за тем, чтобы объединенное обновление было выполнено в правильном месте, чтобы избежать преждевременного освобождения памяти. Метод подсчета ссылок Deutsch Bobrow основан на том, что большинство обновлений счетчиков ссылок генерируются ссылками, хранящимися в локальных переменных. Он игнорирует эти ссылки, подсчитывая только ссылки в структурах данных, но перед удалением объекта с нулевым счетчиком ссылок система должна убедиться путем сканирования стека и регистров, что других ссылок на него не существует. Другой метод, разработанный Генри Бейкером, использует отложенные инкременты, при которых ссылки, хранящиеся в локальных переменных, не увеличивают соответствующий счетчик ссылок немедленно, а откладывают это до тех пор, пока это не станет необходимым. Если такая ссылка быстро уничтожается, то нет необходимости обновлять счетчик. Это устраняет большое количество обновлений, связанных с кратковременными ссылками (например, в примере с вычислением длины списка). Однако, если такая ссылка копируется в структуру данных, то отложенный инкремент должен быть выполнен в этот момент. Также важно выполнить отложенный инкремент до того, как счетчик объекта упадет до нуля, чтобы избежать преждевременного освобождения памяти. Значительное снижение накладных расходов на обновление счетчиков было достигнуто Леванони и Петранком. Они представили метод коалесценции обновлений, который объединяет многие избыточные обновления счетчиков ссылок. Рассмотрим указатель, который в течение определенного интервала времени выполнения обновляется несколько раз. Сначала он указывает на объект O1, затем на объект O2 и так далее, пока в конце интервала он не указывает на объект On. Алгоритм подсчета ссылок обычно выполняет rc(O1), rc(O2)++, rc(O2), rc(O3)++, rc(O3), ..., rc(On)++. Но большинство этих обновлений избыточны. Чтобы правильно оценить счетчик ссылок в конце интервала, достаточно выполнить rc(O1) и rc(On)++. Остальные обновления избыточны. Леванони и Петранк в 2001 году показали, как использовать такую коалесценцию обновлений в сборщике мусора с подсчетом ссылок. При использовании коалесценции обновлений с соответствующей обработкой новых объектов более 99% обновлений счетчиков устраняются для типичных тестов Java. Интересно, что коалесценция обновлений также устраняет необходимость использования атомарных операций при обновлении указателей в многопоточной среде, тем самым решая проблемы подсчета ссылок в многопоточной среде. Таким образом, коалесценция обновлений решает третью проблему наивного подсчета ссылок (то есть высокую накладную стоимость в многопоточной среде). Леванони и Петранк представили усовершенствованный алгоритм, который может выполняться параллельно с многопоточными приложениями, используя только тонкую синхронизацию. Метод отложенного подсчета ссылок Блэкберна и Маккинли в 2003 году сочетает отложенный подсчет ссылок с копирующим питомником, отметив, что большинство изменений указателей происходят в молодых объектах. Этот алгоритм достигает пропускной способности, сравнимой с самыми быстрыми генерационными копирующими сборщиками мусора, с низкими ограниченными временами пауз подсчета ссылок.

Incrementing and decrementing reference counts every time a reference is created or destroyed can significantly impede performance. Not only do the operations take time, but they damage cache performance and can lead to pipeline bubbles. Even read only operations like calculating the length of a list require a large number of reads and writes for reference updates with naive reference counting. One simple technique is for the compiler to combine a number of nearby reference updates into one. This is especially effective for references which are created and quickly destroyed. Care must be taken, however, to put the combined update at the right position so that a premature free can be avoided. The Deutsch Bobrow method of reference counting capitalizes on the fact that most reference count updates are in fact generated by references stored in local variables. It ignores these references, only counting references in data structures, but before an object with reference count zero can be deleted, the system must verify with a scan of the stack and registers that no other reference to it still exists. Another technique devised by Henry Baker involves deferred increments, in which references which are stored in local variables do not immediately increment the corresponding reference count, but instead defer this until it is necessary. If such a reference is destroyed quickly, then there is no need to update the counter. This eliminates a large number of updates associated with short lived references (such as the above list length counting example). However, if such a reference is copied into a data structure, then the deferred increment must be performed at that time. It is also critical to perform the deferred increment before the object's count drops to zero, to avoid a premature free. A dramatic decrease in the overhead on counter updates was obtained by Levanoni and Petrank. They introduce the update coalescing method which coalesces many of the redundant reference count updates. Consider a pointer that in a given interval of the execution is updated several times. It first points to an object O1, then to an object O2, and so forth until at the end of the interval it points to some object On. A reference counting algorithm would typically execute rc(O1) , rc(O2)++, rc(O2) , rc(O3)++, rc(O3) , , rc(On)++. But most of these updates are redundant. In order to have the reference count properly evaluated at the end of the interval it is enough to perform rc(O1) and rc(On)++. The rest of the updates are redundant. Levanoni and Petrank showed in 2001 how to use such update coalescing in a reference counting collector. When using update coalescing with an appropriate treatment of new objects, more than 99% of the counter updates are eliminated for typical Java benchmarks. Interestingly, update coalescing also eliminates the need to employ atomic operations during pointer updates in a concurrent setting, this solving reference counting issues in a concurrent setting. Therefore, update coalescing solves the third problem of naive reference counting (i. e., a costly overhead in a concurrent setting). Levanoni and Petrank presented an enhanced algorithm that may run concurrently with multithreaded applications employing only fine synchronization. Blackburn and McKinley's ulterior reference counting method in 2003 combines deferred reference counting with a copying nursery, observing that the majority of pointer mutations occur in young objects. This algorithm achieves throughput comparable with the fastest generational copying collectors with the low bounded pause times of reference counting.

Обращение с эталонными циклами

Возможно, наиболее очевидный способ обработки циклов ссылок — это проектирование системы таким образом, чтобы избегать их создания. Система может явно запрещать циклы ссылок; файловые системы с жесткими ссылками часто поступают именно так. Разумное использование "слабых" (не подсчитываемых) ссылок также может помочь избежать циклов удержания; например, в Cocoa framework рекомендуется использовать "сильные" ссылки для отношений "родитель-потомок" и "слабые" ссылки для отношений "потомок-родитель". Системы также могут быть разработаны для того, чтобы допускать или исправлять создаваемые ими циклы. Разработчики могут проектировать код для явного "разрыва" ссылок в структуре данных, когда она больше не нужна, хотя это требует от них ручного отслеживания времени жизни этой структуры данных. Этот метод можно автоматизировать, создав "владеющий" объект, который разрывает ссылки при своем уничтожении; например, деструктор объекта Graph может удалять ребра его GraphNodes, тем самым разрывая циклы ссылок в графе. Циклы могут даже игнорироваться в системах с коротким временем жизни и небольшим количеством циклического мусора, особенно если система была разработана с использованием методологии избегания циклических структур данных, где это возможно, обычно за счет производительности. Компьютерные ученые также разработали способы автоматического обнаружения и сбора циклов ссылок без необходимости изменения конструкции структуры данных. Одно из простых решений — периодически использовать трассирующий сборщик мусора для освобождения циклов; поскольку циклы обычно составляют относительно небольшую часть освобождаемого пространства, сборщик может выполняться гораздо реже, чем обычный трассирующий сборщик мусора. Бэкон описывает алгоритм сбора циклов для подсчета ссылок, имеющий сходство с трассирующими сборщиками, включая те же теоретические временные ограничения. Он основан на наблюдении, что цикл можно изолировать только тогда, когда счетчик ссылок уменьшается до ненулевого значения. Все объекты, для которых это происходит, помещаются в список корней, а затем программа периодически ищет циклы среди объектов, достижимых из корней. Алгоритм определяет, что найден цикл, который можно собрать, когда уменьшение всех счетчиков ссылок в цикле приведет их все к нулю. Улучшенная версия этого алгоритма, разработанная Пазом и др., может выполняться параллельно с другими операциями и повышать свою эффективность за счет использования метода объединения обновлений Леванони и Петранка, а также Уотсона и Уотсона (1987).

Perhaps the most obvious way to handle reference cycles is to design the system to avoid creating them. A system may explicitly forbid reference cycles; file systems with hard links often do this. Judicious use of "weak" (non counted) references may also help avoid retain cycles; the Cocoa framework, for instance, recommends using "strong" references for parent to child relationships and "weak" references for child to parent relationships. Systems may also be designed to tolerate or correct the cycles they create in some way. Developers may design code to explicitly "tear down" the references in a data structure when it is no longer needed, though this has the cost of requiring them to manually track that data structure's lifetime. This technique can be automated by creating an "owner" object that does the tearing down when it is destroyed; for instance, a Graph object's destructor could delete the edges of its GraphNodes, breaking the reference cycles in the graph. Cycles may even be ignored in systems with short lives and a small amount of cyclic garbage, particularly when the system was developed using a methodology of avoiding cyclic data structures wherever possible, typically at the expense of efficiency. Computer scientists have also discovered ways to detect and collect reference cycles automatically, without requiring changes in the data structure design. One simple solution is to periodically use a tracing garbage collector to reclaim cycles; since cycles typically constitute a relatively small amount of reclaimed space, the collector can be run much less often than with an ordinary tracing garbage collector. Bacon describes a cycle collection algorithm for reference counting with similarities to tracing collectors, including the same theoretical time bounds. It is based on the observation that a cycle can only be isolated when a reference count is decremented to a nonzero value. All objects which this occurs on are put on a roots list, and then periodically the program searches through the objects reachable from the roots for cycles. It knows it has found a cycle that can be collected when decrementing all the reference counts on a cycle of references brings them all down to zero. An enhanced version of this algorithm by Paz et al. is able to run concurrently with other operations and improve its efficiency by using the update coalescing method of Levanoni and Petrank. and Watson & Watson in 1987.

Косвенное подсчет

При подсчете косвенных ссылок необходимо отслеживать источник ссылки. Это означает, что для объекта поддерживаются две ссылки: прямая, используемая для вызовов, и косвенная, которая является частью дерева распространения, как, например, в алгоритме Дикстры — Шольтена, позволяющем сборщику мусора определять недостижимые объекты. Такой подход предотвращает преждевременное удаление объекта.

Сбор мусора

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

Модель объекта компонента

Microsoft Component Object Model (COM) и WinRT широко используют подсчет ссылок. Фактически, два из трех методов, которые все объекты COM обязаны предоставлять (в интерфейсе IUnknown), инкрементируют или декрементируют счетчик ссылок. Большая часть Windows Shell и многие приложения Windows (включая MS Internet Explorer, MS Office и бесчисленное количество продуктов сторонних разработчиков) построены на COM, что демонстрирует эффективность подсчета ссылок в крупных системах. Одной из основных причин использования подсчета ссылок в COM является обеспечение взаимодействия между различными языками программирования и средами выполнения. Клиенту достаточно знать, как вызывать методы объекта, чтобы управлять его жизненным циклом; таким образом, клиент полностью абстрагирован от используемого реализацией COM-объекта распределителя памяти. В качестве типичного примера, программа Visual Basic, использующая COM-объект, не учитывает, был ли этот объект выделен (и должен ли впоследствии быть освобожден) распределителем C++ или другим компонентом Visual Basic.

C++

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

Какао (цель C)

Фреймворки Apple Cocoa и Cocoa Touch (и связанные с ними фреймворки, такие как Core Foundation) используют ручное подсчета ссылок, подобно COM. Традиционно это достигалось программистом путем ручной отправки сообщений `retain` и `release` объектам, но в iOS 5 и Mac OS X 10.7 была добавлена автоматическая подсчет ссылок (Automatic Reference Counting), функция компилятора Clang, которая автоматически вставляет эти сообщения по мере необходимости. Mac OS X 10.5 представила сборщик мусора с трассировкой как альтернативу подсчету ссылок, но он был объявлен устаревшим в OS X 10.8 и удален из библиотеки времени выполнения Objective-C в macOS Sierra. iOS никогда не поддерживала сборщик мусора с трассировкой.

Гобъект

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

Перл

Perl также использует подсчет ссылок, без какой-либо специальной обработки циклических ссылок, хотя (как и в Cocoa и C++ выше), Perl поддерживает слабые ссылки, что позволяет программистам избегать образования циклов.

PHP (англ.)

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

Python (англ.)

Python также использует подсчет ссылок и предлагает обнаружение циклов (и может освободить циклические ссылки).

Белокочанная

Squirrel использует подсчет ссылок с обнаружением циклов. Этот крошечный язык относительно неизвестен за пределами индустрии видеоигр, однако он является конкретным примером того, как подсчет ссылок может быть практичным и эффективным (особенно в средах реального времени).

Стрелец

Swift использует подсчет ссылок для отслеживания и управления памятью экземпляров классов и предоставляет ключевое слово `weak` для создания слабых ссылок. Экземпляры типов-значений не используют подсчет ссылок.

Т. кл.

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

Ходжо

Xojo также использует подсчет ссылок, не предусматривая специальной обработки циклических ссылок, хотя (как и в Cocoa и C++ выше), Xojo поддерживает слабые ссылки, позволяющие программистам избегать образования циклов.

Файловые системы

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