Для программирования в режиме реального времени подсчет ссылок имеет преимущество перед сборкой "мусора" с точки зрения детерминизма?
Если Вы разрабатывали язык программирования, что функции, автоматическое управление памятью, с помощью подсчета ссылок будет допускать гарантии детерминизма, которые не возможны со сборщиком "мусора"?
Был бы другой ответ на этот вопрос для функционального по сравнению с императивными языками?
5 ответов
Будет ли использование подсчета ссылок обеспечивать гарантии детерминизма, которые невозможны с помощью сборщика мусора?
Слово гарантия является сильным. Вот гарантии, которые вы можете предоставить с помощью подсчета ссылок:
Постоянные накладные расходы при назначении для корректировки счетчиков ссылок.
Постоянное время для освобождения объекта, счетчик ссылок которого обнуляется. (Суть в том, что вы не должны сразу же декрементировать дочерние элементы этого объекта; вместо этого вы должны делать это лениво , когда объект используется для удовлетворения будущего запроса на выделение.)
Постоянное время для выделения нового объекта , когда соответствующий список свободных мест не пуст .Эта гарантия условна и не стоит многого.
Вот некоторые вещи, которые вы не можете гарантировать при подсчете ссылок:
Постоянное время для выделения нового объекта. (В худшем случае куча может увеличиваться, и в зависимости от системы задержка для организации новой памяти может быть значительной. Или, что еще хуже, вы можете заполнить кучу и быть не в состоянии выделить.)
Все недостижимые объекты являются недоступными. утилизируется и используется повторно, сохраняя при этом постоянное время для других операций. (Стандартный счетчик ссылок не может собирать циклический мусор. Существует множество хитроумных обходных решений, но обычно они сводят на нет гарантии постоянного времени для простых операций.)
Теперь есть несколько сборщиков мусора в реальном времени, которые предоставляют довольно интересные гарантии о времени паузы, и за последние 5 лет произошли довольно интересные изменения как в подсчете ссылок, так и в сборке мусора. С моей точки зрения, как информированного аутсайдера, очевидного победителя нет.
Некоторые из лучших недавних работ по подсчету ссылок написаны Дэвидом Бэконом из IBM и Эрезом Петранком из Техниона. Если вы хотите узнать, на что способна сложная современная система подсчета ссылок, посмотрите их статьи. Помимо прочего, они удивительным образом используют несколько процессоров.
Для получения информации об управлении памятью и гарантиях в реальном времени в целом, посетите Международный симпозиум по управлению памятью .
Будет ли другой ответ на этот вопрос для функциональных и императивных языков?
Поскольку вы спросили о гарантиях , нет. Но для управления памятью в целом компромиссы производительности совершенно разные для императивного языка (много мутаций, но низкая скорость распределения), нечистого функционального языка (почти никаких мутаций, но высокая скорость распределения) и чистого, ленивого функционального языка (много мутации - все они думают, что обновляются - и высокие показатели распределения).
При программировании сборки мусора в реальном времени может быть вредно, потому что вы не знаете , когда сборщик мусора будет собирать ... так что да, подсчет ссылок определенно лучше в этот контекст.
В качестве примечания: обычно в системе реального времени только некоторые части требуют обработки в реальном времени, поэтому вы можете избежать сборки мусора только в чувствительных компонентах. Пример из реальной жизни - программа на C #, работающая на целевой машине Windows CE.
Из-за некоторого участия в различных проектах по переносу значительных фрагментов кода с C ++ (с различными классами интеллектуальных указателей, включая подсчет ссылок) на Java / C # со сборкой мусора, я заметил, что все самые большие проблемы, похоже, связаны с классами с непустые деструкторы (особенно при использовании для RAII). Это довольно серьезный признак того, что ожидается детерминированная очистка.
Проблема, безусловно, одинакова для любого языка с объектами; Я не думаю, что гибридные OO-функциональные языки, такие как Scala или Ocaml, обладают какими-либо особыми преимуществами в этой области. Для более «чистых» функциональных языков ситуация может быть иной.
Если вы посмотрите на спецификацию RTSJ (JSR-1), то увидите, что они обошли эту проблему, предусмотрев потоки реального времени без кучи. Имея отдельную категорию потоков, которым не разрешается касаться любых объектов, которые могут потребовать остановки потока для сбора мусора, JSR-1 обошел проблему стороной. В настоящее время существует не так много реализаций RTSJ, но область сборки мусора в реальном времени является горячей темой в этом сообществе.
может ли использование подсчета ссылок обеспечивать гарантии детерминизма, которые невозможны с помощью сборщика мусора?
Я не понимаю, как это сделать. Процесс уменьшения счетчика ссылок объекта не ограничен по времени , так как этот объект может быть единственным корнем для произвольного графа больших объектов.
Единственный способ подойти к проблеме GC для систем реального времени - использовать либо параллельный сборщик, либо инкрементный - независимо от того, использует ли система подсчет ссылок или нет; на мой взгляд, ваше различие между подсчетом ссылок и "коллекцией" в любом случае неточно, например системы, использующие подсчет ссылок, могут все же время от времени выполнять некоторое сканирование памяти (например, для обработки циклов).
Возможно, вас заинтересует IBM Metronome , и я также знаю, что Microsoft провела некоторые исследования в направлении эффективного управления памятью в реальном времени.