Насколько отличается сборка мусора на чистых языках?

26

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

Какие стратегии и методы используют сборщики мусора перед лицом чистоты, что иначе они бы не сделали? Что работает очень хорошо в GC нечистого языка, который не в чистом контексте? Какие еще новые проблемы создают чистые языки для GC?

Джек
источник
1
Вы можете прочитать этот wiki.haskell.org/GHC/Memory_Management
Матеуш К.

Ответы:

13

Текущая реализация ghc использует стратегию, которая работает только потому, что язык является чисто функциональным, а данные неизменяемыми: поскольку ни одна переменная не может быть изменена для ссылки на что-то более новое, объекты содержат ссылки только на более старые объекты, поэтому он запускает сборщик мусора поколений ; поскольку объект, на который ссылается более высокое поколение, не может быть удален до тех пор, пока это поколение не станет GCd, он охотно продвигает объекты в более высокие поколения; и поскольку ничто не изменит ссылок во время их очистки GC, он может работать параллельно.

Вот статья с более подробной информацией .

Davislor
источник
4
Стремительное продвижение опирается на лень - обновление бандита в старом поколении может создать указатель на новое поколение, но бандиты мутируют только один раз, поэтому этого достаточно для продвижения молодого объекта. Другие старые ссылки на молодых (например, из изменяемых массивов) отслеживаются с использованием «запоминаемых наборов», которые также используются в случае неудачного продвижения по службе.
Джон Пурди
1

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

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

Какие стратегии и методы используют сборщики мусора перед лицом чистоты, что иначе они бы не сделали?

Единственное, о чем я могу думать, это черные дыры . Я не помню, чтобы видел что-то новое со стороны GC в исследовательских работах на Haskell.

Что работает очень хорошо в GC нечистого языка, который не в чистом контексте?

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

Другие алгоритмы GC, такие как mark-region, гораздо более жизнеспособны в контексте нечистых языков, потому что они могут иметь гораздо более низкие скорости выделения, чем чистые языки.

Какие еще новые проблемы создают чистые языки для GC?

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

Джон Харроп
источник
«Когда требуется, выражение вычисляется, и преобразование преобразуется в результирующее значение». Это внутренняя деталь реализации для пользователя Haskell. Нет способа наблюдать мутацию, поэтому это не мутация с точки зрения пользователя.
Джек
Кроме того, для чистого языка вполне возможно быть строгим - см. Идрис для примера.
Джек