В информатике подсчет ссылок — это программный метод хранения количества ссылок , указателей или дескрипторов ресурса, такого как объект, блок памяти, дисковое пространство и другие .
В алгоритмах сборки мусора счетчики ссылок могут использоваться для освобождения объектов, которые больше не нужны.
Главное преимущество подсчета ссылок перед отслеживанием сборки мусора заключается в том, что объекты удаляются, как только на них больше нельзя ссылаться, и в инкрементном режиме, без длительных пауз для циклов сбора и с четко определенным временем жизни каждого объекта. В приложениях реального времени или системах с ограниченной памятью это важно для поддержания отзывчивости. Подсчет ссылок также является одной из самых простых форм управления памятью для реализации. Он также позволяет эффективно управлять ресурсами, не относящимися к памяти, такими как объекты операционной системы, которые часто намного более дефицитны, чем память (системы отслеживания сборки мусора используют для этого финализаторы , [ требуется цитата ], но отложенное удаление может вызвать проблемы). Взвешенные подсчеты ссылок являются хорошим решением для сбора мусора в распределенной системе.
Циклы сбора мусора трассировки запускаются слишком часто, если набор живых объектов заполняет большую часть доступной памяти; [ требуется цитирование ] для эффективности требуется дополнительное пространство. [ требуется цитирование ] Производительность подсчета ссылок не ухудшается при уменьшении общего объема свободного пространства. [2]
Счетчики ссылок также являются полезной информацией для использования в качестве входных данных для других оптимизаций времени выполнения. Например, системы, которые сильно зависят от неизменяемых объектов, таких как многие функциональные языки программирования, могут страдать от потери эффективности из-за частых копий. [ необходима цитата ] Однако, если компилятор (или система времени выполнения ) знает, что конкретный объект имеет только одну ссылку (как это происходит во многих системах) и что ссылка теряется в то же время, когда создается аналогичный новый объект (как в операторе добавления строки str ← str + "a"), он может заменить операцию мутацией исходного объекта.
Подсчет ссылок в наивной форме имеет три основных недостатка по сравнению со сборкой мусора с трассировкой, для устранения обоих из которых требуются дополнительные механизмы:
В дополнение к этому, если память выделяется из свободного списка, подсчет ссылок страдает от плохой локальности. Подсчет ссылок сам по себе не может перемещать объекты для повышения производительности кэша, поэтому высокопроизводительные сборщики также реализуют отслеживающий сборщик мусора. Большинство реализаций (например, в PHP и Objective-C) страдают от плохой производительности кэша, поскольку они не реализуют копирование объектов. [3]
При работе со схемами сборки мусора часто бывает полезно вспомнить граф ссылок , представляющий собой направленный граф , вершинами которого являются объекты, и существует ребро от объекта A к объекту B, если A содержит ссылку на B. У нас также есть специальная вершина или вершины, представляющие локальные переменные и ссылки, хранящиеся в системе выполнения, и никакие ребра никогда не ведут к этим узлам, хотя ребра могут идти от них к другим узлам.
В этом контексте простой счетчик ссылок объекта — это входящая степень его вершины. Удаление вершины похоже на сбор объекта. Это можно сделать только тогда, когда вершина не имеет входящих ребер, поэтому это не влияет на исходящую степень других вершин, но это может повлиять на входящую степень других вершин, заставляя их соответствующие объекты также быть собранными, если их входящая степень также станет равной 0.
Связанный компонент, содержащий специальную вершину, содержит объекты, которые не могут быть собраны, в то время как другие связанные компоненты графа содержат только мусор. Если реализован алгоритм сборки мусора с подсчетом ссылок, то каждый из этих компонентов мусора должен содержать по крайней мере один цикл; в противном случае они были бы собраны, как только их счетчик ссылок (т. е. количество входящих ребер) упало бы до нуля.
Увеличение и уменьшение количества ссылок каждый раз, когда ссылка создается или уничтожается, может значительно снизить производительность. Операции не только занимают время, но и наносят ущерб производительности кэша и могут привести к пузырям конвейера . Даже операции только для чтения, такие как вычисление длины списка, требуют большого количества чтений и записей для обновления ссылок с наивным подсчетом ссылок.
Один из простых методов заключается в том, чтобы компилятор объединял несколько близлежащих обновлений ссылок в одно. Это особенно эффективно для ссылок, которые создаются и быстро уничтожаются. Однако следует соблюдать осторожность, чтобы поместить объединенное обновление в правильное положение, чтобы избежать преждевременного освобождения.
Метод подсчета ссылок Дойча-Боброва использует тот факт, что большинство обновлений счетчика ссылок фактически генерируются ссылками, хранящимися в локальных переменных. Он игнорирует эти ссылки, подсчитывая только ссылки в структурах данных, но прежде чем объект с нулевым счетчиком ссылок может быть удален, система должна проверить с помощью сканирования стека и зарегистрировать, что никаких других ссылок на него больше не существует.
Другой метод, разработанный Генри Бейкером, включает отложенные приращения [ 4] , в которых ссылки, которые хранятся в локальных переменных, не увеличивают немедленно соответствующий счетчик ссылок, а вместо этого откладывают это до тех пор, пока это не станет необходимым. Если такая ссылка быстро уничтожается, то нет необходимости обновлять счетчик. Это устраняет большое количество обновлений, связанных с кратковременными ссылками (такими как приведенный выше пример подсчета длины списка). Однако, если такая ссылка копируется в структуру данных, то отложенное приращение должно быть выполнено в это время. Также критически важно выполнить отложенное приращение до того, как счетчик объекта упадет до нуля, чтобы избежать преждевременного освобождения.
Резкое снижение накладных расходов на обновления счетчиков было получено Леванони и Петранком . [5] [6] Они вводят метод объединения обновлений , который объединяет многие избыточные обновления счетчика ссылок. Рассмотрим указатель, который в заданном интервале выполнения обновляется несколько раз. Сначала он указывает на объект O1, затем на объект O2и так далее, пока в конце интервала он не укажет на некоторый объект On. Алгоритм подсчета ссылок обычно выполняет rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Но большинство этих обновлений избыточны. Для того чтобы правильно оценить счетчик ссылок в конце интервала, достаточно выполнить rc(O1)--и rc(On)++. Остальные обновления избыточны.
В 2001 году Леванони и Петранк показали, как использовать такое объединение обновлений в коллекторе подсчета ссылок. При использовании объединения обновлений с соответствующей обработкой новых объектов более 99% обновлений счетчиков устраняются для типичных тестов Java.
Интересно, что объединение обновлений также устраняет необходимость использования атомарных операций во время обновления указателя в параллельной настройке, что решает проблемы подсчета ссылок в параллельной настройке. Таким образом, объединение обновлений решает третью проблему наивного подсчета ссылок (т. е. дорогостоящие накладные расходы в параллельной настройке). Леванони и Петран представили усовершенствованный алгоритм, который может работать одновременно с многопоточными приложениями, использующими только тонкую синхронизацию. [7]
Метод скрытого подсчета ссылок Блэкберна и МакКинли 2003 года [8] сочетает отложенный подсчет ссылок с копирующим питомником, отмечая, что большинство мутаций указателей происходит в молодых объектах. Этот алгоритм достигает пропускной способности, сравнимой с самыми быстрыми поколенческими копирующими сборщиками с низкими ограниченными временами пауз подсчета ссылок.
Возможно, наиболее очевидным способом обработки циклов ссылок является проектирование системы так, чтобы избежать их создания. Система может явно запрещать циклы ссылок; файловые системы с жесткими ссылками часто делают это. Разумное использование «слабых» (не учитываемых) ссылок также может помочь избежать циклов сохранения; например, фреймворк Cocoa рекомендует использовать «сильные» ссылки для отношений родитель-потомок и «слабые» ссылки для отношений потомок-родитель. [9]
Системы также могут быть спроектированы так, чтобы каким-то образом допускать или исправлять циклы, которые они создают. Разработчики могут разрабатывать код для явного «разрыва» ссылок в структуре данных, когда она больше не нужна, хотя это имеет цену, требующую от них вручную отслеживать время жизни этой структуры данных. Этот метод может быть автоматизирован путем создания объекта «владельца», который выполняет разрыв при его уничтожении; например, деструктор объекта Graph может удалить ребра его GraphNodes, нарушая циклы ссылок в графе. Циклы могут даже игнорироваться в системах с коротким сроком жизни и небольшим количеством циклического мусора, особенно когда система была разработана с использованием методологии избегания циклических структур данных везде, где это возможно, как правило, за счет эффективности.
Специалисты по информатике также открыли способы автоматического обнаружения и сбора циклов ссылок, не требуя изменений в структуре данных. Одним из простых решений является периодическое использование сборщика мусора трассировки для освобождения циклов; поскольку циклы обычно составляют относительно небольшой объем освобожденного пространства, сборщик может запускаться гораздо реже, чем обычный сборщик мусора трассировки.
Бэкон описывает алгоритм сбора циклов для подсчета ссылок, схожий с трассирующими коллекторами, включая те же теоретические временные ограничения. Он основан на наблюдении, что цикл может быть изолирован только тогда, когда счетчик ссылок уменьшается до ненулевого значения. Все объекты, с которыми это происходит, помещаются в список корней , а затем периодически программа просматривает объекты, достижимые из корней, на предмет циклов. Она знает, что нашла цикл, который может быть собран, когда уменьшение всех счетчиков ссылок в цикле ссылок сводит их все к нулю. [10] Улучшенная версия этого алгоритма Паза и др. [11] может работать одновременно с другими операциями и повышать свою эффективность, используя метод объединения обновлений Леванони и Петранка. [5] [6]
Хотя можно расширить простые подсчеты ссылок различными способами, часто лучшее решение можно найти, выполняя подсчет ссылок принципиально иным способом. Здесь мы описываем некоторые варианты подсчета ссылок, их преимущества и недостатки.
При взвешенном подсчете ссылок каждой ссылке назначается вес , и каждый объект отслеживает не количество ссылок, ссылающихся на него, а общий вес ссылок, ссылающихся на него. Первоначальная ссылка на вновь созданный объект имеет большой вес, например 2 16 . Всякий раз, когда эта ссылка копируется, половина веса переходит к новой ссылке, а половина веса остается у старой ссылки. Поскольку общий вес не меняется, счетчик ссылок объекта не нужно обновлять.
Уничтожение ссылки уменьшает общий вес на вес этой ссылки. Когда общий вес становится равным нулю, все ссылки уничтожены. Если делается попытка скопировать ссылку с весом 1, ссылка должна «получить больше веса», добавив к общему весу, а затем добавив этот новый вес к ссылке, а затем разделив ее. Альтернативой в этой ситуации является создание объекта косвенной ссылки, начальная ссылка на который создается с большим весом, который затем может быть разделен.
Свойство отсутствия необходимости доступа к счетчику ссылок при копировании ссылки особенно полезно, когда доступ к счетчику ссылок объекта является дорогостоящим, например, потому что он находится в другом процессе, на диске или даже в сети. Это также может помочь повысить параллелизм, избегая блокировки счетчика ссылок многими потоками для его увеличения. Таким образом, взвешенный подсчет ссылок наиболее полезен в параллельных, многопроцессорных, базах данных или распределенных приложениях.
Основная проблема с простым взвешенным подсчетом ссылок заключается в том, что уничтожение ссылки все еще требует доступа к счетчику ссылок, и если уничтожено много ссылок, это может вызвать те же узкие места, которых мы пытаемся избежать. Некоторые адаптации взвешенного подсчета ссылок стремятся избежать этого, перенося вес с умирающей ссылки на активную ссылку.
Метод взвешенного подсчета ссылок был независимо разработан Беваном [12] и Уотсоном и Уотсоном [13] в 1987 году.
При косвенном подсчете ссылок необходимо отслеживать источник ссылки. Это означает, что на объект сохраняются две ссылки: прямая, которая используется для вызовов; и косвенная, которая является частью дерева диффузии, например, в алгоритме Дейкстры–Шолтена , который позволяет сборщику мусора идентифицировать мертвые объекты. Такой подход предотвращает преждевременное удаление объекта.
Как алгоритм сбора, подсчет ссылок отслеживает для каждого объекта количество ссылок на него, хранящихся другими объектами. Если количество ссылок объекта достигает нуля, объект становится недоступным и может быть уничтожен.
Когда объект уничтожается, все объекты, на которые он ссылается, также уменьшают свои счетчики ссылок. Из-за этого удаление одной ссылки может потенциально привести к освобождению большого количества объектов. Распространенная модификация позволяет сделать подсчет ссылок инкрементным: вместо уничтожения объекта, как только его счетчик ссылок становится равным нулю, он добавляется в список неиспользуемых объектов, и периодически (или по мере необходимости) один или несколько элементов из этого списка уничтожаются.
Простые счетчики ссылок требуют частых обновлений. Всякий раз, когда ссылка уничтожается или перезаписывается, счетчик ссылок объекта, на который она ссылается, уменьшается, а всякий раз, когда она создается или копируется, счетчик ссылок объекта, на который она ссылается, увеличивается.
Подсчет ссылок также используется в файловых системах и распределенных системах, где полная неинкрементная трассировка сборки мусора занимает слишком много времени из-за размера графа объектов и низкой скорости доступа. [14]
Component Object Model (COM) и WinRT от Microsoft широко используют подсчет ссылок. Фактически, два из трех методов, которые должны предоставлять все объекты COM (в интерфейсе IUnknown ), увеличивают или уменьшают счетчик ссылок. Большая часть оболочки Windows и многих приложений Windows (включая MS Internet Explorer , MS Office и бесчисленное множество сторонних продуктов) построены на COM, что демонстрирует жизнеспособность подсчета ссылок в крупномасштабных системах. [ необходима цитата ]
Одной из основных причин подсчета ссылок в COM является обеспечение взаимодействия между различными языками программирования и системами времени выполнения. Клиенту нужно знать только, как вызывать методы объекта, чтобы управлять жизненным циклом объекта; таким образом, клиент полностью абстрагируется от любого распределителя памяти, который использует реализация объекта COM. В качестве типичного примера, программа Visual Basic, использующая объект COM, не зависит от того, был ли этот объект выделен (и должен быть впоследствии освобожден) распределителем C++ или другим компонентом Visual Basic.
C++ не выполняет подсчет ссылок по умолчанию, выполняя свою философию не добавлять функциональность, которая может повлечь за собой накладные расходы, если пользователь явно не запросил ее. Объекты, которые являются общими, но не принадлежащими, могут быть доступны через ссылку, необработанный указатель или итератор (концептуальное обобщение указателей).
Однако, по той же причине, C++ предоставляет пользователям собственные способы выбора такой функциональности: C++11 предоставляет подсчитываемые ссылки интеллектуальные указатели , через std::shared_ptrкласс, что позволяет автоматически управлять общей памятью динамически выделяемых объектов. Программисты могут использовать это в сочетании со слабыми указателями (через std::weak_ptr), чтобы разорвать циклические зависимости. Объекты, которые динамически выделяются, но не предназначены для совместного использования, могут автоматически управлять своим временем жизни с помощью std::unique_ptr.
Кроме того, семантика перемещения C++11 еще больше снижает необходимость изменения счетчиков ссылок за счет удаления глубокого копирования, которое обычно используется, когда функция возвращает объект, поскольку оно допускает простое копирование указателя указанного объекта.
Фреймворки Cocoa и Cocoa Touch от Apple (и связанные фреймворки, такие как Core Foundation ) используют ручной подсчет ссылок, во многом похожий на COM . Традиционно это выполнялось программистом, вручную отправляющим retainсообщения releaseобъектам, но Automatic Reference Counting , функция компилятора Clang , которая автоматически вставляет эти сообщения по мере необходимости, была добавлена в iOS 5 [15] и Mac OS X 10.7 [ 16] Mac OS X 10.5 представила трассирующий сборщик мусора в качестве альтернативы подсчету ссылок, но он был объявлен устаревшим в OS X 10.8 и удален из библиотеки времени выполнения Objective-C в macOS Sierra [ 17] [18] iOS никогда не поддерживала трассирующий сборщик мусора.
Delphi в основном не является языком сборки мусора, в котором пользовательские типы все еще должны быть вручную выделены и освобождены; однако он обеспечивает автоматический сбор с использованием подсчета ссылок для нескольких встроенных типов, таких как строки, динамические массивы и интерфейсы, для простоты использования и упрощения функциональности общей базы данных. Программист должен решить, использовать ли встроенные типы; программисты Delphi имеют полный доступ к низкоуровневому управлению памятью, как в C/C++. Таким образом, все потенциальные затраты на подсчет ссылок Delphi можно, при желании, легко обойти.
Вот некоторые из причин, по которым подсчет ссылок может быть предпочтительнее других форм сбора мусора в Delphi:
Объектно-ориентированная программная среда GObject реализует подсчет ссылок на своих базовых типах, включая слабые ссылки . Инкрементирование и декрементирование ссылок использует атомарные операции для безопасности потоков. Значительная часть работы по написанию привязок к GObject из языков высокого уровня заключается в адаптации подсчета ссылок GObject для работы с собственной системой управления памятью языка.
Язык программирования Vala использует подсчет ссылок GObject в качестве основной системы сборки мусора, а также обработку строк с интенсивным копированием. [19]
Perl также использует подсчет ссылок, без какой-либо специальной обработки циклических ссылок, хотя (как в Cocoa и C++ выше) Perl поддерживает слабые ссылки, что позволяет программистам избегать создания цикла.
PHP использует механизм подсчета ссылок для внутреннего управления переменными. [20] Начиная с PHP 5.3, он реализует алгоритм из вышеупомянутой статьи Бэкона. PHP позволяет включать и выключать циклическую коллекцию с помощью функций уровня пользователя. Он также позволяет вручную принудительно запускать механизм очистки.
Python также использует подсчет ссылок и предлагает обнаружение циклов (и может восстанавливать циклы ссылок). [21]
Как и другие низкоуровневые языки, Rust не обеспечивает подсчет ссылок по умолчанию. Вместо этого любой сконструированный тип будет отброшен , если он выйдет из области действия. Когда программисту нужно определить область действия сконструированного типа, они часто используют время жизни.
Однако язык также предлагает различные альтернативы сложным формам управления памятью. Функциональность подсчета ссылок обеспечивается типами Rcи Arc, которые являются неатомарными и атомарными соответственно.
Например, тип Rc<T>обеспечивает совместное владение значением типа T, выделенным в куче для множественных ссылок на его данные. [22]
использовать std :: rc :: Rc ; структура Cat { цвет : строка , } fn main () { let cat = Cat { color : "black" . to_string () }; let cat = Rc :: new ( cat ); } Использование этих конструкций позволяет программистам избегать жизней за небольшую стоимость выполнения. Оба счетчика ссылок отслеживают количество владельцев, поскольку они должны сбрасывать себя, когда не остается владельцев.
Один примечательный аспект этих типов связан с их использованием в качестве общей ссылки. В Rust общие ссылки не могут изменять свои удерживаемые данные, поэтому Rcчасто идут в комплекте с Cell, и Arcс Mutex, в контекстах, где необходима внутренняя изменчивость.
Внутренняя изменчивость без нее UnsafeCellтакже имеет издержки производительности, поэтому для достижения максимальной производительности некоторые приложения могут потребовать дополнительной сложности. [23]
Squirrel использует подсчет ссылок с обнаружением циклов. Этот крошечный язык относительно неизвестен за пределами индустрии видеоигр; однако, это конкретный пример того, как подсчет ссылок может быть практичным и эффективным (особенно в средах реального времени). [ необходима цитата ]
Swift использует подсчет ссылок для отслеживания и управления памятью экземпляров классов и предоставляет weakключевое слово для создания слабых ссылок. Экземпляры типов значений не используют подсчет ссылок. [24]
Tcl 8 использует подсчет ссылок для управления памятью значений ( структуры Tcl Obj ). Поскольку значения Tcl неизменяемы, циклы ссылок невозможно сформировать, и схема обнаружения циклов не требуется. Операции, которые заменяют значение измененной копией, обычно оптимизируются для изменения оригинала, когда его счетчик ссылок указывает, что он не является общим. Ссылки подсчитываются на уровне структуры данных, поэтому проблемы с очень частыми обновлениями, обсуждавшиеся выше, не возникают.
Xojo также использует подсчет ссылок, без какой-либо специальной обработки циклических ссылок, хотя (как в Cocoa и C++ выше) Xojo поддерживает слабые ссылки, что позволяет программистам избегать создания цикла.
Многие файловые системы поддерживают счетчики ссылок на любой конкретный блок или файл, например, счетчик ссылок inode в файловых системах в стиле Unix , которые обычно известны как жесткие ссылки . Когда счетчик достигает нуля, файл можно безопасно освободить. Хотя ссылки по-прежнему можно делать из каталогов , некоторые Unix допускают ссылки только из живых процессов, и могут быть файлы, которые существуют вне иерархии файловой системы.
{{cite conference}}: CS1 maint: multiple names: authors list (link){{cite journal}}: CS1 maint: multiple names: authors list (link)