Haskell编译器如何决定是在堆还是堆上分配？ [英] How do Haskell compilers decide whether to allocate on the heap or the stack?

问题描述

Haskell没有显式内存管理，所有对象都是通过值传递的，所以没有明显的引用计数或垃圾回收。 Haskell编译器通常决定是否生成在堆栈上分配的代码，而不是为给定变量在堆上分配的代码？它会一直堆或堆栈分配相同的变量跨不同的调用站点为相同的功能？当它分配时，它如何决定什么时候释放内存？ C：

解决方案

当你调用一个函数时，这

  f 42（gxy）
  

那么运行时行为类似如下：

  p1 = malloc （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  as（ gxy  /  p2 ）。没有优化，这个执行模型效率很低，但是有很多方法可以避免这些开销。
 
 
 
的内联和拆箱。内联消除了函数调用开销，并且经常启用进一步的优化。取消装箱意味着改变调用约定，在上面的例子中，我们可以直接传递 42 ，而不是创建堆对象 p1 。 
 
 
 
 
严格性分析会确定参数是否被保证被求值。在这种情况下，我们不需要创建thunk，而是完全评估表达式，然后将最终结果作为参数传递。
 
 
 
 
目前只缓存8位 Char  s和 Int  s）。 也就是说，不是为每个对象分配一个新的指针，而是返回指向缓存的对象的指针。即使对象最初分配在堆上，垃圾回收器将在以后解除重复只有小 Int  s和 Char  s）。由于对象是不可变的，因此这是安全的。
 
 
 
 
有限的转义分析。对于局部函数，一些参数可能在栈上传递，因为它们在外部函数返回时是已知的死代码。
 
 
 
 编辑：有关（详细信息），请参阅在库存硬件上实现延迟功能语言：无纺标签G机器。本文使用push / enter作为调用约定。较新版本的GHC使用eval / apply调用约定。有关权衡取舍和原因的讨论，请参阅如何制作快速咖喱：push / enter vs eval / apply 
 
Haskell doesn't feature explicit memory management, and all objects are passed by value, so there's no obvious reference counting or garbage collection either. How does a Haskell compiler typically decide whether to generate code that allocates on the stack versus code that allocates on the heap for a given variable? Will it consistently heap or stack allocate the same variables across different call sites for the same function? And when it allocates, how does it decide when to free memory? Are stack allocations and deallocations still performed in the same function entrance/exit pattern as in C?
解决方案
When you call a function like this
f 42 (g x y)
then the runtime behaviour is something like the following:
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)
That is, arguments are usually passed as pointers to objects on the heap like in Java, but unlike Java these objects may represent suspended computations, a.k.a. thunks, such as (g x y/p2) in our example.  Without optimisations, this execution model is quite inefficient, but there are ways to avoid many of these overheads.

GHC does a lot of inlining and unboxing.  Inlining removes the function call overhead and often enables further optimisations.  Unboxing means changing the calling convention, in the example above we could pass 42 directly instead of creating the heap object p1.
Strictness analysis finds out whether an argument is guaranteed to be evaluated.  In that case, we don't need to create a thunk, but evaluate the expression fully and then pass the final result as an argument.
Small objects (currently only 8bit Chars and Ints) are cached.  That is, instead of allocating a new pointer for each object, a pointer to the cached object is returned.  Even though the object is initially allocated on the heap, the garbage collector will de-duplicate them later (only small Ints and Chars).  Since objects are immutable this is safe.
Limited escape analysis.  For local functions some arguments may be passed on the stack, because they are known to be dead code by the time the outer function returns.
Edit: For (much) more information see "Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine".  This paper uses "push/enter" as the calling convention.  Newer versions of GHC use the "eval/apply" calling convention.  For a discussion of the trade-offs and reasons for that switch see "How to make a fast curry: push/enter vs eval/apply"

                        
这篇关于Haskell编译器如何决定是在堆还是堆上分配？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！