再帰関数を使うとき、ソフトウェアスタックはハードウェアスタックと比べてどれくらい遅い？

質問

再帰を使って関数を書こうと思うのですが、再帰する回数が不明なので、スタックオーバーフローを避けるためソフトウェアスタックを使おうと思っている者です。

ソフトウェアスタックはどれくらい遅いのでしょうか？
どう実装すれば速度が改善されるのでしょうか？

回答No.3

txrx · ベストアンサー

ハードウェアスタックって言うのが、スタックポインタ(レジスタ)を使用した物で、ソフトウェアスタックって言うのが、ハードウェアスタックを使用しない擬似スタック操作だとすると、その遅さは？

通常のスタック操作は、アセンブリ言語で１命令になります。
擬似的にソフトウェアでスタック操作を行うとなると、アセンブリレベルで何命令必要か？と言うことになります。
C言語で数命令でもアセンブリレベルだと数～数十命令になりますので、何十倍も遅くなると思います。

call命令等のスタック操作をソフトウェアで実現することはまず無意味なので、おそらくオート変数のみを別配列等で構築し、それを操作する？と言った意味ですか？

そうすると、それ程遅くはならないでしょう。
ポインタを上手く使えば、Cコンパイラの最適化処理が効率よくコンパイルしてくれると思います。
実装方法としては、必要な変数を構造体等にまとめ、その配列を構築し、それらをポインタで管理すればよいと思います。
オート変数の場合は、スタック上に構築した後、スコープを外れる時に破棄する無駄な動きが発生しますが、上記のようにすると、構築・破棄と言った無駄な処理がなくなるので、オート変数を使用した再帰より速くなる可能性が十分あります。
そしてオーバーフローも簡単に管理できますね。

お礼

具体的な手続きを説明して下さり、ありがとうございます。

回答No.4

liar_adan

手元のアセンブラマニュアルを見てみると、
PUSH命令が1～4クロック、
POP命令が1～6クロックで、わりと遅いです。
もっとも、これは486時代のデータなので、古くてあてになりません。
最近のCPUはパイプライン処理とかややこしいことをしているので、
はっきりと「何倍遅い」とは計算できないと思います。

そこをあえて考えてみると…
まず、ソフトウェアスタックを実現するためには、
(1)ポインタの読み出し。
(2)スタックするデータを、ポインタが指すアドレスへ書き出す。
(3)ポインタをデータサイズ分加算。
(4)ポインタのメモリへの書き込み。
によってPUSH動作が行えます。(POPも同じようなもの)
これらはあまり重い処理ではない(読み出し・書き込みは
486でも1クロックで実現できる)ので、
「遅くなるにしても、せいぜい4倍程度」
ではないかと思います。

これに加えて、スタックオーバーフローのチェックをする場合、
・ポインタ制限値の読み込み。
・ポインタ制限値とポインタ値の比較。
・分岐命令。
などで、同じくらいかかる可能性があります。
これを考えに入れても
せいぜい8倍程度ではないでしょうか。
最適化が働けば(たとえばポインタ値をレジスタに置いておくなど)、
もっと早くなる可能性はあります。
逆に、最適化がうまく行かなければ遅くなる可能性もあります。
パイプライン処理がうまく行くか行かないかも関係してきます。

というわけで、おもいっきり自信なしですが、
「オーバーフローチェックを入れてもせいぜい一ケタ弱の差」
というあたりかなあ…と思います。

お礼

2ケタの速度差があるインタプリタがあることを考えれば、一ケタで収まるのは意外でした。ありがとうございます。

回答No.2

sha-girl

＞再帰する回数が不明なので
ある程度の最大数はわかるのでは？
65000個のデータをクイックソートしても16個
41憶のデータでも必要な領域は32個だけですよ？

回答No.1

επιστημη（@episteme）

> スタックオーバーフローを避けるためソフトウェアスタックを使おうと思っている者です。

ソフトウェアスタックってなんですか?
それだとオーバーフローしないのはナゼですか?