Про boehm-gc

если в объекте есть ссылки на другие объекты

Ну то есть интересно, как этот boehm-gc по одной лишь своей функции malloc и таинственному сборщику мусора этот факт узнает.

man precise gc man conservative gc

Что прям так и смотрит во все регистры, которые могут содержать указатели и догадывается, его ли это клиент?

Да.

Если у меня такой код:

Если массив глобальный, то он находится в области памяти глобальных переменных, и GC это видит; если массив локальный, то GC это тоже видит, а ты ССЗБ.

А если у меня есть объект, который доступен только из другого? Например, я сделал списки на основе cons-ячеек. Как он поймет, что они достижимы?

Boehm GC сканирует память, достижимую из roots, ищет в ней слова, которые могут быть указателями. и сканирует память дальше. Как он разбирается, действительно ли является указателем похожее на указатель слово, я не знаю - видимо, есть у него эвристики; но очевидно, что он не всегда может решить правильно, поэтому он и консервативный.

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

Он просто считает что угодно указателем, если оно выглядит как адрес внутри его кучи. Там есть специальные средства, чтобы указать ему для конкретных кусков памяти, что в ней адрес, а что не адрес. Но если их не использовать, а просто тупо в программе заменить все вызовы обычного malloc на вызовы его malloc, то он будет будет считать указателем всё подряд.

Он просто считает что угодно указателем, если оно выглядит как адрес внутри его кучи

Если бы он считал _всё_ указателем, он не был бы консервативным.

Ну здрасти...

Conservative collectors assume that any bit pattern in memory could be a pointer if, interpreted as a pointer, it would point into an allocated object. Conservative collectors may produce false positives, where unused memory is not released because of improper pointer identification.

Наоборот, ведь такое поведение может привести к тому, что некоторые недостижимые объекты он посчитает достижимыми и оставит.

Эксперты с мировым именем из википедии:

Some collectors can correctly identify all pointers (references) in an object; these are called precise (also exact or accurate) collectors, the opposite being a conservative or partly conservative collector. Conservative collectors assume that any bit pattern in memory could be a pointer if, interpreted as a pointer, it would point into an allocated object. Conservative collectors may produce false positives, where unused memory is not released because of improper pointer identification.

Опередил

Conservative collectors assume that any bit pattern in memory could be a pointer if, interpreted as a pointer, it would point into an allocated object

Мое «как он разбирается» относилось именно к тому, как он понимает, что «bit pattern» относится к размещенному объекту.

Яничонипонял, ну да ладно.

И вот как же оно поддерживает это самое корневое множество?

Оно и так есть в виде стека и регистров, таки да, догадывается.

Если у меня такой код:

Этот код ub и сборщик тут ни при чем. malloc/free его область.

А если у меня есть объект, который доступен только из другого?

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

Boehm может увидеть где-нибудь инт, похожий на указатель (по его критериям), и не станет собирать блок под таким указателем. Всем пофиг. Кстати с ним нельзя использовать кодирование указателей, например xor-linked lists.

Яничонипонял

http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html

Mark phase

Boehm GC - плохой сборщик. Вернее, другого сборщика для С/С++ и «обычных» указателей и не сделать(можно сделать любой нормальный сборщик, если завести свои типы указателей).

А так, если хочешь изучить именно GC, то смотри их реализацию для нормальных языков/платформ. Например, посмотри на открытые явы машины, вроде Jikes RVM и пр.

Boehm — ненадёжен. Например, есть такая оптимизация двусвязного списка: вместо двух пойнтеров вперёд и назад хранить только их XOR (поскольку мы всегда знаем тот из них, по которому нашли этот элемент). Boehm совершенно спокойно удалит нафиг весь список — ссылок-то нет (кроме как на первый элемент).

Очевидно, вы просто не будете применять boehm для данных с такого рода оптимизациями.

Я знаю, но boehm тут не виноват, а виноват такой кодер

Какой «такой»? Вполне нормальная оптимизация.

Что не понятно-то? boehm-gc, как сказали, ищет в потенциальных местах то, что похоже на указатели. Он не знает про такие хитрые списки, ведь для этого нужно было бы хотя бы как-то их специально помечать. Вот что я имел в виду

Очевидно, вы просто не будете применять boehm для данных с такого рода оптимизациями.

Угу. Просто GC предназначен, в общем-то, для того, чтобы у программера голова не болела об освобождении памяти, а тут вместо этого голова болит о взаимодействии GC с оптимизациями.

Нет, я понимаю, что для C или C++ лучше не написать, и что Boehm GC — пожалуй, лучшее, что тут может быть. Просто просвещаю ТС-а.

Просто GC предназначен, в общем-то, для того, чтобы у программера голова не болела об освобождении памяти

Ну еще в некоторых алгоритмах просто гораздо удобнее с GC, чем без него.

а тут вместо этого голова болит о взаимодействии GC с оптимизациями.

Ну так С/С++ же. Как иначе?

Вообще в С++ сборщик для того же связного списка не нужен. Там семантики владения более чем достаточно. Подозреваю, что та же ситуация и с другими местами, где возможно мешающие сборщику оптимизации.

для C или C++ лучше не написать

Написать, если создать специальные типы указателей и аллокаторы. В C++/CLI, например, так и сделано - ссылки для дотнетовского сборщика имеют свой тип и свои операции создания объекта.

Кстати, в языках с нормальными сборщиками описанные вами оптимизации не сделать=)

Написать, если создать специальные типы указателей и аллокаторы.

Э... нет. Написать, если административными методами запретить использование обычных указателей и энфорсить это глобальным код-ревью. И то где-нибудь просочится.

Кстати, в языках с нормальными сборщиками описанные вами оптимизации не сделать

Дык никто и не спорит.

Э... нет. Написать, если административными методами запретить использование обычных указателей и энфорсить это глобальным код-ревью. И то где-нибудь просочится.

Достаточно просто не обеспечивать возможность неявных преобразования в обычные указатели. И ситуация будет аналогичной с std::unique_ptr, std::shared_ptr и std::weak_ptr.

А так-то при желании можно и vtbl затереть=)

Достаточно просто не обеспечивать возможность неявных преобразования в обычные указатели. И ситуация будет аналогичной с std::unique_ptr, std::shared_ptr и std::weak_ptr.

Оператор & куда денем?

А куда вы его дели для случая std::unique_ptr, std::shared_ptr и std::weak_ptr?

А куда вы его дели для случая std::unique_ptr, std::shared_ptr и std::weak_ptr?

А что это за случай?

Так те же самые. Висячие ссылки и удаление уже удаленного(руками) объекта.

Так те же самые.

Те же самые кто?

Да, я немного не так выразился. В случае использования std::unique_ptr, std::shared_ptr и std::weak_ptr вы получаете те же потенциальные проблемы, что и в случае гипотетического вида указателей для полноценного GC.

Поскольку использование стандартных «умных» указателей не является какой-то проблемой на практике, то можно ожидать, что проблем не будет и при использовании умного указателя(и аллокатора) для полноценного сборщика.

Я имею в виду что-то вроде такого:

template<typename T>
class gc_ptr
{
    // ...
};

template<typename T, typename... Args>
gc_ptr<T> gc_new(Args&&... args)
{
   // ...
}

И используем как-то так:

auto obj = gc_new<MyClass>(10, "str", 2.0);
obj->foo();

В этом случае наш сборщик будет работать только со специальными видами умных указателей, получая возможность использовать любую стратегию сборки. Если нужно получить сырой указатель на такой объект(например, для передачи в сишную функцию), можно сделать как в C++/CLI - еще один умный указатель - pin_ptr<T>, что предотвратит(временно) перемещение объекта сборщиком мусора.

Как наличие отдельного типа позволит сборщику находить рутовые объекты? Да и дальше тоже не понятно как это упростит построение графа. У тебя тут те же проблемы, что и у Boehm. Нормальный сборщик в виде библиотеки не сделать для нативного языка без интроспекции(да даже если делать через нее - получим тормоза).

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

Boehm консервативный, он вообще любое слово считает указателем.

Ждем нового стандарта?=) А в clang случаем не собираются запиливать? У них и в llvm есть зачаточная поддержка gc.

Кстати, а как jvm/.net ищут корневые ссылки и отличают их от int'ов с тем же значением, например? jit составляет карты корневых ссылок?

Так в JVM типизированная куча и типизированный стек - всегда известно в рантайме, что есть указатель, а что есть просто число.

Разве примитивные типы тегируются в рантайме?

Как наличие отдельного типа позволит сборщику находить рутовые объекты?

Очевидно, gc_ptr будет каким-то образом брать на себя функции построения «карты» рутовых ссылок. Думаю, что если как следует подумать, то это можно сделать достаточно эффективно.

Кстати, кто-нибудь знает, как ищут рутовые ссылки нативные языки со сборкой мусора? Оберон какой-нибудь, например.

так jit по инструкциям строит карту рутовых ссылок, насколько я понимаю.

gc_ptr будет каким-то образом брать на себя функции построения «карты» рутовых ссылок.

Он тогда будет тормозным. Еще более, чем shared_ptr.

Кстати, кто-нибудь знает, как ищут рутовые ссылки нативные языки со сборкой мусора? Оберон какой-нибудь, например.

SBCL по тегу. И есть такой storage class:

  ;; pointer descriptor objects -- must be seen by GC
  (descriptor-reg registers
                  :locations #.*qword-regs*
                  :element-size 2
; :reserve-locations (#.eax-offset)
                  :constant-scs (constant immediate)
                  :save-p t
                  :alternate-scs (control-stack))

Т.е. тоже ищет, в частности, в регистрах