Циклические ссылки при подсчете ссылок

Кто он?

Region inference.

Вы какую из работ по этому вопросу имеете в виду?

Все. Region inference не работает и работать не может, потому что не может существовать алгоритма для корректного вывода регионов. Все работы в этой области сводятся к «давайте напихаем эвристик и будем надеяться на то, что оно будет не сильно плохо».

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

Да, это каким-то особым английским термином называлось, забыл точное название... Rubbish gathering вроде бы, так как-то.

Dross hoarding не подходит тем, кто хочет детерминированное управление временем жизни объектов (читай: RAII со всеми своими плюшками).

Region inference не работает и работать не может, потому что не может существовать алгоритма для корректного вывода регионов

Какие ваши доказательства?

Почему не может? Что значит «корректный»?

Region inference не работает и работать не может

У вас есть какие-то доказательства?

для корректного вывода регионов

Что значит «корректного»? Регионы могут не подходить для нашей задачи, это понятно. Но вот чтобы корректность была нарушена...

Все работы в этой области сводятся к «давайте напихаем эвристик и будем надеяться на то, что оно будет не сильно плохо».

Давайте вы приведете какую-нибудь работу и покажете это на ней?

У вас есть какие-то доказательства?

Задача алгоритмически неразрешима. Пример выше.

Что значит «корректного»?

Значит регионы соответствуют времени жизни объектов.

Давайте вы приведете какую-нибудь работу и покажете это на ней?

Давай лучше ты предъявишь мне работу, которая не удовлетворяет этому описанию? Потому что утверждение о том что все котики белые не подтверждается наличием белых котиков. Оно опдтверждается отсутствием котиков другого цвета.

Задача алгоритмически неразрешима.

Обычно такие заявления подкрепляют доказательствами.

Значит регионы соответствуют времени жизни объектов.

Хм... Сборщик мусора так же не обеспечивает удаления в то же время, как объект становится не нужен. Разве это причина отказываться от данного механизма?

Давай лучше ты предъявишь мне работу, которая не удовлетворяет этому описанию? Потому что утверждение о том что все котики белые не подтверждается наличием белых котиков. Оно опдтверждается отсутствием котиков другого цвета.

Я пока не понял, какое описание вам нужно, потому работу привести не могу=)

Пример выше.

Какой именно? Примеров с регионами я не помню.

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

Это было бы полезно в качестве отладочного инструмента. Всё таки при подсчёте ссылок циклов быть не должно, циклы портят весь смысл подсчёта ссылок. Их надо разрывать слабыми ссылками. А вот отыскивать циклы в отладочных сборках — милое дело.

Обычно такие заявления подкрепляют доказательствами.

Пример выше был.

Хм... Сборщик мусора так же не обеспечивает удаления в то же время, как объект становится не нужен. Разве это причина отказываться от данного механизма?

Тогда надо называть вещи своими именами, вывод регионов = сборка мусора.

Я пока не понял, какое описание вам нужно, потому работу привести не могу=)

Работу, в которых предоставлен алгоритм вывода регионов, которые бы соответствовали времени жизни объектов. Никакие другие регионы, понятное дело, никому не нужны.

Какой именно? Примеров с регионами я не помню.

Если нельзя вычислить время жизни объекта то и нельзя вычислить пул объектов, которые можно было бы вместе деаллоцировать. Это эквивалентые задача и одна тривиально сводится к другой.

Работу, в которых предоставлен алгоритм вывода регионов, которые бы соответствовали времени жизни объектов. Никакие другие регионы, понятное дело, никому не нужны.

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

Да, ты прав. Я подробнее почитал, что там умеет и неумеет ARC.

Считаю, что трейдофф все же адекватный.

Да он не будет чистить за тобой везде где ты накосячишь.

НО

Зато пауз нет.

Что в моих глазах поднимает ARC на божественную высоту, а GC в лужу с говном.

f x = if (pred x) then [] else (cons 0 x)

х - список. Как ты тут что отследишь если время жизни х зависит от pred x, то есть от вида самого х, которые нельзя определить до рантайма?

А почему нельзя вставить разный код в разные ветки?

А почему нельзя вставить разный код в разные ветки?

Да потому что он невнимательный, я про это в начале темы не один раз талдычил.

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

Так не может. И потому все время прикручивают сборщик к языкам с выводом регионов.

Мне бы очень хотелось иметь это в промышленных языках.

Зчем? чтобы тормозило? Сборщик _всегда_ лучше вывода регионов.

В какие разные ветки? f yoba - здесь нет никаких веток.

Зато пауз нет.

Вобщем-то перемещающий generational сборщик заставить работать без пауз довольно просто, надо только апи к сборщику, чтобы уметь останавливать сборку и запускать по требованию

Запускать по требованию и без пауз это вроде не одно и тоже? если все так просто, почему в мейнстриме нету гц без пауз?

Так не может

Почему нет?

Сборщик _всегда_ лучше вывода регионов.

пруф?

внутри f вставлять разный код в разные ветви if

И потому все время прикручивают сборщик к языкам с выводом регионов

Что за языки?

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

Да, это каким-то особым английским термином называлось, забыл точное название... Rubbish gathering вроде бы, так как-то.

Так вроде в том же Limbo, например, используется RC по умолчанию и нельзя определить рекурсивные или взаимоссылочные типы. Для этого нужно использовать ключевое слово cyclic или типа того и тогда уже эти объекты рулятся GC, а не RC.

У некоторых есть же.

Attempts to disallow garbage collection

Запретить == Отложить на потом?

Считаю, что трейдофф все же адекватный

Он замечательный, никаких претензий к нему не имею. Мне тож ARC нравится намного больше. Просто хотел развеять миф об автоотлове циклов.

Будь добр, дай ссылку на какое-нибудь исследование по теме. Мне, например, не понятно, где RC может быть медленнее.

Мне, например, не понятно, где RC может быть медленнее.

Он медленнее в плане работы с ссылками. В случае GC у тебя там фактически обычные указатели(ну почти, для сборки с поколениями требуется подпрыгивать), а в случае RC(и особенно atomic rc) ты платишь за каждое копирование ссылки. Если служебная структура со счетчиком и указателем лежит отдельно, ты платишь при этом и за косвенный доступ к объекту, а так же можешь получать лишние кэш-промахи. А копирующий сборщик тебе еще и объекты кладет в памяти правильно, что, кроме прочего, ускоряет выделение памяти(просто смещаем указатель в куче и все).

Нет у меня такой ссылки. Потому и написал «есть мнение».

На словах могу сказать вот что:

- движущий сборщик мусора не страдает от фрагментации памяти, поэтому не нужны и меры для борьбы с ней, которые усложняют менеджер памяти и которые поэтому могут замедлить выделение/освобождение памяти.

- при сборке мусора, копирование указателя - это просто копирование указателя. При RC нужно ещё счётчик поменять. А запись может подразумевать ещё и наложение блокировок при наличии тредов.

Видимо, поэтому _в_некотором_классе_приложений_ сборка мусора будет быстрее. Наверное, сказать, что она «вообще быстрее» нельзя. Наверняка найдутся примеры и за тот, и за другой вариант.

Есть мнение, что подсчёт ссылок медленнее сборки мусора. Сборка мусора бывает очень навороченная, с поколениями.

Так или иначе сборка мусора должна сама использовать подсчет ссылок в своей работе.

Она должна перебирать все (или некоторые) ссылки во время сборки мусора, но это не то, что называется «подсчёт ссылок».

Ну если делать заключение о нужности объекта в зависимости от его достижимости, то да, счетчик ссылок не требуется.

При RC нужно ещё счётчик поменять. А запись может подразумевать ещё и наложение блокировок при наличии тредов.

Только что проверил - boost::intrusive_ptr на std::atomic_int приблизительно в два раза медленней копируется чем обычный указатель. В итоге получаем вполне себе допустимый оверхед (если не копировать миллиарды указателей в секунду), и главное - прогнозируемый и без затыков. Ну и доступ по интрузивному указателю происходит вообще без оверхеда - т.к. в памяти он лежит ровно так же, как и обычный указатель.

Только что проверил - boost::intrusive_ptr на std::atomic_int приблизительно в два раза медленней копируется чем обычный указатель

Да, это вместе с освобождением указателя, т.е. скопировали/«забыли»/следующая итерация.

вывод регионов = сборка мусора.

Нет. Это разные механизмы. Вывод регионов, в основном, работает в статике.

алгоритм вывода регионов, которые бы соответствовали времени жизни объектов. Никакие другие регионы, понятное дело, никому не нужны.

Нужны=)

Так или иначе сборка мусора должна сама использовать подсчет ссылок в своей работе.

Нет. Сборщики работают иначе.

Это лишь до момента вызова сборщика. Потом же перебираются вообще все указатели на объекты для проверки достижимости. Так при частом вызове сборщика ты часто перебираешь ВСЮ память приложения. В то время как в RC имеет значение лишь счетчик ссылок одного объекта. Так что там все весьма спорно.

Потом же перебираются вообще все указатели на объекты для проверки достижимости.

Нет, все не перебираются. Перебираются только достижимые(т.е. не мусор), все остальное просто считается мусором, без перебора.

Так при частом вызове сборщика ты часто перебираешь ВСЮ память приложения.

Нет. Во-первых, есть поколения. Во-вторых, см. выше.

В то время как в RC имеет значение лишь счетчик ссылок одного объекта.

Есть ещё каскадное удаление. Обнулился счётчик какого-нибудь контейнера — поехали трогать, проверять и убивать всё его содержимое.

Запускать по требованию и без пауз это вроде не одно и тоже? если все так просто, почему в мейнстриме нету гц без пауз?

Если запускать по требованию, то можно запускать его в моменты, когда в молодом поколении 0 достижимых данных, то есть мусор будет собран практически мгновенно (порядка миллисекунд).

Почему нет?

потому что это алгоритмически неразрешимая задачА, сколько еще раз повторить?

внутри f вставлять разный код в разные ветви if

При чем тут вставка кода? Речь о статическом анализе, тебе надо знать освобождать переменную или нет. Что там происходит в рантайме не волнует никого.

Абсолютно все известные мне языки с выводом регионов. Если ты знаешь какой-то без gc - назови.

Мне, например, не понятно, где RC может быть медленнее.

Выделение памяти для перемещающего сборщика - это инкремент указателя, освобождение памяти - происходит практически мгновенно (по сравнению с деаллокацией для RC). С-но любая программа которая выделяет и освобождает большое количество памяти в случае GC будет работать сильно быстрее чем RC.

Мне, например, не понятно, где RC может быть медленнее.

Выделение памяти для перемещающего сборщика - это инкремент указателя, освобождение памяти - происходит практически мгновенно (по сравнению с деаллокацией для RC). С-но любая программа которая выделяет и освобождает большое количество памяти в случае GC будет работать сильно быстрее чем RC.

Мне, например, не понятно, где RC может быть медленнее.

Выделение памяти для перемещающего сборщика - это инкремент указателя, освобождение памяти - происходит практически мгновенно (по сравнению с деаллокацией для RC). С-но любая программа которая выделяет и освобождает большое количество памяти в случае GC будет работать сильно быстрее чем RC.

Нужны=)

Кому и зачем?

Нет. Это разные механизмы.

Я в курсе. Это ты начал про то, что оно одно и то же.

то есть мусор будет собран практически мгновенно (порядка миллисекунд).

Для игр, звука, графики и прочего это неадекватно.