Существует ли алгоритм сбора мусора, который отвечает этим требованиям? - PullRequest
16 голосов
/ 01 февраля 2011

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

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

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

Ответы [ 6 ]

5 голосов
/ 05 февраля 2011

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

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

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

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

2 голосов
/ 11 февраля 2011

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

Если вы ищете алгоритмы вместо кода , я бы определенно взглянул на научные статьи. Я наткнулся на материалы 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

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

0 голосов
/ 05 февраля 2011

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

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

0 голосов
/ 04 февраля 2011

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

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

0 голосов
/ 03 февраля 2011

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

  • Mono
  • Ocaml
  • Python
  • ...
0 голосов
/ 03 февраля 2011

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

...