30

Haskell は明示的なメモリ管理機能を備えておらず、すべてのオブジェクトが値渡しであるため、明らかな参照カウントやガベージ コレクションもありません。Haskell コンパイラは通常、特定の変数に対してスタックに割り当てるコードを生成するか、ヒープに割り当てるコードを生成するかをどのように決定しますか? 同じ関数の異なる呼び出しサイトに同じ変数を一貫してヒープまたはスタックに割り当てますか? また、メモリを割り当てるとき、いつメモリを解放するかをどのように決定しますか? スタックの割り当てと割り当て解除は、C と同じ関数の入口/出口パターンで引き続き実行されますか?

4

2 に答える 2

37

このような関数を呼び出すと

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)

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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"

于 2011-02-27T11:12:25.620 に答える
2

GHC がスタックに置くのは評価コンテキストだけです。let/where バインディングで割り当てられたもの、およびすべてのデータ コンストラクターと関数は、ヒープに格納されます。遅延評価により、厳密な言語での実行戦略について知っていることはすべて無関係になります。

于 2011-02-27T09:36:25.977 に答える