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

Question

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

Answer 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 эти объекты могут представлять приостановленные вычисления, или thunks , такие как (g x y / p2 ) в нашем примере. Без оптимизации эта модель выполнения довольно неэффективна, но есть способы избежать многих из этих накладных расходов.

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

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

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

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

Редактировать : (более) более подробную информацию см. В «Внедрение ленивых функциональных языков на стандартном оборудовании: G-машина без меток Spineless» . Этот документ использует «push / enter» в качестве соглашения о вызовах. В новых версиях GHC используется соглашение о вызовах eval / apply. Для обсуждения компромиссов и причин этого переключения см. «Как сделать быстрое карри: push / enter vs eval / apply»

Answer 2

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