1

末尾呼び出しの最適化にガベージ コレクションが必要なのはなぜですか? テールコールを実行したい関数にメモリを割り当てた場合、テールコールを実行してそのメモリを取り戻す方法がないからですか? (したがって、末尾呼び出しの後にメモリを再利用できるように、スタックを保存する必要があります。)

4

4 に答える 4

9

ほとんどの神話と同様に、これにも一片の真実があるかもしれません。テール コールの最適化にGC は必須ではありませんが、GC が役立つ場合もあります。C++ で次のようなものがあるとします。

int foo(int arg) {
    // Base case.

    vector<double> bar(10);
    // Populate bar, do other stuff.

    return foo(someNumber);
}

この場合、 foo(someNumber); を返します。テール コールのように見えますが、RAII メモリ管理を使用しており、バーを解放する必要があるため、この行は次のように下位レベルに変換されます (非公式の擬似コード):

ret = foo(someNumber);
free(bar);
return ret;

GC がある場合、コンパイラがフリー バーに命令を挿入する必要はありません。したがって、この関数はテール コールに最適化できます。

于 2008-12-12T18:27:51.500 に答える
7

どこで聞いた？

ガベージ コレクタをまったく持たない C コンパイラでさえ、末尾再帰呼び出しを反復等価物に最適化できます。

于 2008-12-05T17:27:33.023 に答える
4

末尾呼び出しの最適化では、ガベージ コレクションは必要ありません。

コール スタックに割り当てられた変数は再帰呼び出しで再利用されるため、メモリ リークは発生しません。

ヒープに割り当てられ、テール コールの前に解放されないローカル変数は、テール コールの最適化が使用されているかどうかにかかわらず、メモリ リークを起こします。ヒープに割り当てられ、テール コールの前に解放されたローカル変数は、テール コールの最適化が使用されているかどうかに関係なく、メモリ リークしません。

于 2008-12-05T17:39:54.497 に答える
2

確かに、末尾呼び出しの最適化にはガベージコレクションは実際には必要ありません。

ただし、1 GBのRAMがあり、900 MBの整数リストをフィルタリングして、正の整数のみを保持するとします。約半分が正で、半分が負であると仮定します。

GCを使用する言語では、関数を記述するだけです。GCは何度も発生し、最終的には450MBのリストになります。コードは次のようになります。

list *result = filter(make900MBlist(), funcptr);

make900MBlistは、パーツフィルタが通過した後、何からも参照されなくなるため、増分GCdになります。

GCのない言語では、末尾再帰を保持するには、次のようなことを行う必要があります。

list *srclist = make900MBlist();
list *result = filter(srclist, funcptr);
freelist(srclist);

これにより、最終的にsrclistを解放する前に900MB + 450MBを使用する必要が生じるため、プログラムはメモリを使い果たして失敗します。

独自のfilter_reclaimを作成すると、入力リストが不要になったため、次のように解放されます。

list *result = filter_reclaim(make900MBlist(), funcptr);

末尾再帰ではなくなり、スタックがオーバーフローする可能性があります。

于 2008-12-06T20:53:16.307 に答える