CUDAとBarnes-Hutアルゴリズムに関するビデオを見ていましたが、GPUのツリーに深度制限を設ける必要があると言われていました。ヒープ内で再帰を行います。メモリ割り当てを伴う再帰
基本的に、私はヒープからメモリを割り当てて、スタックオーバーフローをやや遅らせるために再帰関数の関数呼び出しを配置する一時的な "スタック"としてメモリを割り当てることは可能ですか？
もしそうなら、どのように実装することができますか？私たちは関数へのポインタのためのスペースを割り当てますか？私はそれがヒープに関数のアドレスを格納する必要があると思うが、私はあまり確かではない。
[編集]これは純粋に理論上の質問であり、これを行うとプログラムがヒープを使用して一度減速することになると思います。要求ごととして
[編集]、私が使用していますコンパイラは、Ubuntuの14.04（64ビット）
確かにGCC 4.8.4です。これを継承通過スタイルといいます。標準ライブラリーはsetjmp()とlongjmp()でそれをサポートし、制御をリストアするのに必要な情報をjmp_bufという構造の以前のポイントに保管します。 （どこから復元できるかにはいくつかの制限があります）スタックに格納するのはLIFOキューだけです。
さらに一般的なアプローチは、プログラムをステートマシンとして実行し、継続と呼ばれるプログラム状態をバックトラッキングするために必要な情報を、トランポリンと呼ばれるデータ構造に格納することです。これをしたい一般的な理由は、最適化されていない実装でtail-recursionと同等のものを取得し、たくさんのスタック領域を噛み砕く可能性があるためです。私が知っている誰かが現在トランポリンを書いている1つの現実的なアプリケーションは、文法が有向グラフとして表されるGLLパーサーであり、パース結果はパースされた共有パースフォレストであり、パーザはしばしば違うルール。
継続プログラミングとトランポリンは機能プログラミングの世界から来ていると思われているようですが、longjmp()は醜い低レベルのハックとみなされ、Linuxのマンページでも使用しないと言われています。
継続コードは、システムが後続の呼び出しのためにスタックに使用するものを変更せず、直接コードも継続的なものも変更しないので、疑問に提起された問題に実際には対処していないと思います。しかし、継続が望まれる場合、 'setjmp（）'/'longjmp（）'は制限された方法でしかそれらをサポートしないことに注意することが重要です。対応するlongjmpの動作はもはや定義されていません。 –
これは、関数呼び出しと戻り値からの制御フローの別の手段です。つまり、 'longjmp（）'についてのあなたのコメントは正しくありません。元の関数*が終了したら、動作は未定義です。 'setjmp（）'と呼ばれる関数から再帰的に呼び出される関数から 'longjmp（）'を呼び出すことは合法です。実際、それは 'goto'が十分ではなかったユースケースでした。 – Davislor
"control leaves"とは、（他の）関数を呼び出すのではなく、 'longjmp（）'を呼び出すことによって関数が返ったり終了したりすることを意味します。とにかく、OPの質問は、具体的には、コールスタックに異なるメモリ領域を使用することです。継続は、コール/リターンのための代替*です。その理由から、彼らはその問題に対処しません。 –
これは、独自のヒープベースのスタックを構造体の配列として実装することでシミュレーションできます。各構造体は、パラメータとローカル変数に相当するスタックフレームを表します。再帰的に呼び出す関数の代わりに、関数はループを起こし、各 "呼び出し"は明示的に新しいフレームをスタックにプッシュします。
シンプルなボードゲームを解決しようとしていますが、今年はまさにこの年でした。プログラムはもともと再帰的で、実行には永遠にかかりました。私は上記の構造に変更し、これはアプリケーションを中断/再開可能にすることが簡単になりました。中断されると、アプリケーションはその「スタック」を状態ファイルにダンプします。再起動すると、アプリは状態ファイルを読み込み、中断した場所から継続しました。
スタックフレーム構造に埋め込みポインタが含まれている場合、これは注意が必要ですが、克服できないものではありません。
Cはこのようなメカニズムを定義していません。実際には、これらの名前や他の名前の下で「スタック」や「ヒープ」を定義することはありません。それらはほとんどの*実装の側面の標準的な名前ですが、Cの範囲外です。つまり、役に立つ答えを得るためには、特定の実装を指定する必要があります。一方、それはまた、C自体があなたが何を記述することを禁じていないことを意味します。 3番目の手で、私はそれを提供する実装を認識していません。 –
@JohnBollinger申し訳ありませんが、特定の実装を指定する必要があると言ったときに、意味が分かりません。言語自体がどのようにメモリを扱うのかを意味しますか？私はこれまでにいくつかの入門コースしか取っておらず、Cコンパイラ（と私はほとんどのコンパイラが推測する）がメモリをどのように管理するかの基本以外のこの側面には入らない。 – Plopperzz
「特定の実装を指定する」とは、質問の範囲をLinuxのGCC 5/glibcやWindows 10のMS Visual C++ 2013に絞り込むことです。 –