Как компиляторы Haskell решают, следует ли выделять кучу или стек?

В Haskell нет явного управления памятью, и все объекты передаются по значению, поэтому нет очевидного подсчета ссылок или сборки мусора. Как компилятор Haskell обычно решает, следует ли генерировать код, который выделяется в стеке, и код, который выделяет кучу для данной переменной? Будут ли последовательно куча или стек выделять одни и те же переменные на разных сайтах для одной и той же функции? И когда он выделяет, как он решает, когда освобождать память? Выделены ли стеки и освобождения от деления в том же шаблоне ввода/вывода функции, что и в C?

Ответы

Ответ 1

Когда вы вызываете такую ​​функцию

f 42 (g x y)

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

p1 = malloc(2 * sizeof(Word))
p1[0] = &Tag_for_Int
p1[1] = 42
p2 = malloc(3 * sizeof(Word))
p2[0] = &Code_for_g_x_y
p2[1] = x
p2[2] = y
f(p1, p2)

То есть аргументы обычно передаются как указатели на объекты в куче, как в Java, но в отличие от Java эти объекты могут представлять собой приостановленные вычисления, a.k.a. thunks, такие как (g x y/p2) в нашем примере. Без оптимизаций эта модель исполнения довольно неэффективна, но есть способы избежать многих из этих накладных расходов.

  • GHC делает много вложений и распаковки. Inlining удаляет служебные вызовы функции и часто позволяет продолжить оптимизацию. Unboxing означает изменение соглашения о вызове, в приведенном выше примере мы могли бы передать 42 непосредственно вместо создания объекта кучи p1.

  • Анализ жесткости выясняет, будет ли оцениваться аргумент. В этом случае нам не нужно создавать thunk, но полностью оценивайте выражение, а затем передавайте конечный результат в качестве аргумента.

  • Малые объекты (в настоящее время только 8 бит Char и Int s) кэшируются. То есть вместо выделения нового указателя для каждого объекта возвращается указатель на кешированный объект. Даже если объект изначально выделен в куче, сборщик мусора будет дедуплицировать их позже ( только малые Int и Char s). Поскольку объекты неизменяемы, это безопасно.

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

Изменить. Более подробную информацию см. в "Внедрение" ленивых функциональных языков на складе ":" Бесконечная безматрица "G-machine" . В этом документе термин "push/enter" используется как соглашение о вызове. В более новых версиях GHC используется соглашение об использовании "eval/apply". Для обсуждения компромиссов и причин этого переключателя см. "Как сделать быстрое карри: push/enter vs eval/apply"

Ответ 2

Единственные вещи, которые GHC ставит в стек, - это контексты оценки. Все, что выделяется связыванием let/where, и все конструкторы и функции данных, хранятся в куче. Ленивая оценка делает все, что вы знаете о стратегиях исполнения в строгих языках, не имеет значения.