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位Chars和Ints). 也就是说,不是为每个对象分配新指针,而是返回指向高速缓存对象的指针. 即使最初在堆上分配了对象,垃圾收集器也会在以后对它们进行重复删除(只有小Ints和Chars).由于对象是不可变的,因此这是安全的.

4. 有限逃脱分析.对于本地函数,可以在堆栈上传递一些参数,因为在外部函数返回时已知它们是死代码.

编辑:有关(更多)更多信息,请参阅"在库存硬件上实现懒惰功能语言:无脊椎无标签G机".本文使用"push/enter"作为调用约定.较新版本的GHC使用"eval/apply"调用约定.有关该转换的权衡和原因的讨论,请参阅"如何快速进行咖喱:推/输入vs eval/apply"