Есть ли алгоритм сбора мусора, который отвечает этим требованиям?

Я пишу компилятор для статически типизированного объектно-ориентированного языка. В настоящее время я изучаю алгоритмы сбора мусора. Мне интересно, есть ли коллекционер, который:

Открыть исходный код и задокументировать его, чтобы я мог его реализовать.
Acurrate
Generational
Глобальный, т.е. есть только один сборщик на процесс, а не один на поток.
Инкрементный и/или параллельный, чтобы избежать длинных пауз из основных коллекций.
Подходит для этой парадигмы программирования. Примером того, что не будет коллекционером, который становится очень медленным в присутствии деструктивного назначения.

Изменить: Чтобы уточнить, мне было интересно, если это реализуемый алгоритм, который делает это, а не если есть готовый сборщик.

Ответ 1

(я бы предпочел, чтобы это было как комментарий, но у меня не хватило репутации.)

Если вы ищете алгоритмы, а не код, я бы определенно взглянул на научные статьи. Я наткнулся на Труды OOPSLA 2003 и сразу вспомнил ваш вопрос: у них было две сессии по сборке мусора:

http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-1.html
http://www.oopsla.org/oopsla2003/files/pap-session-garbage-collection-2.html

Преимущество этих моментов "большого взрыва" для начала вашего исследования заключается в том, что вы можете затем использовать Google Scholar для любой статьи, которая выглядит многообещающей, и посмотреть, есть ли более современные наблюдения, ища название а затем нажмите ссылку "процитировано", например:

http://scholar.google.com/scholar?cites=11437015034573374705&as_sdt=2005&sciodt=0,5&hl=en

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

Ответ 2

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

Одна проблема заключается в том, что все еще очищаются циркулярные ссылки, которые вы, по крайней мере, можете оставить крайне редко; разработчики приложений, которые заботятся о скорости, могут просто явно разрывать петли, когда им нужно, чтобы объекты уходили.

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

Refcounting не очень эффективен для сильно многопоточных систем, поскольку вам нужно приобретать блокировки каждый раз, когда вы касаетесь refcount. Но если вы все-таки разрабатываете новый язык, вы можете сделать одну огромную вещь, чтобы повысить производительность и надежность на всем вашем языке: предотвращать совместное использование практически всех объектов между потоками. то есть. сделать обмен явным. Если вы это сделаете, вы узнаете, какие объекты против них не являются совместно, и поэтому какие из них нужно блокировать при добавлении/уменьшении количества ссылок и которые могут быть оставлены разблокированными. Когда нет блокировки, производительность перекомпоновки может быть действительно отличной.

Ответ 3

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

Ответ 4

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

Mono
Ocaml
Python
...

Ответ 5

Это (очевидно) трудно ответить без какой-либо лучшей идеи о языке, на котором вы надеетесь разместить, но вы посмотрели на Parrot VM? PDD 9: Подсистема сбора мусора обсуждает свой GC и, кажется, поражает запрошенные вами ключевые слова и языки, для которых он был разработан (Perl6 в первую очередь, с lua и сильно типизированная javascript-ish вещь, называемая winxed как сильные секунды), безусловно, имеет деструктивное назначение и объекты.

Это цель виртуальной машины, но не отдельная GC. Я действительно сомневаюсь, что вы найдете GC (кроме консервативных коллекционеров, таких как Boehm), которые не связаны с каким-то типом VM, поскольку для получения точной информации требуется больше информации о фрейме стека, чем может быть разбор.

Ответ 6

Сборщик мусора Azul является запатентованным, но достаточно информации об их алгоритме, что вы должны иметь возможность реализовать что-то вроде этого: http://news.ycombinator.com/item?id=2022723

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