- ベストアンサー
再帰関数を使うとき、ソフトウェアスタックはハードウェアスタックと比べてどれくらい遅い？
liar_adanの回答
- liar_adan
- ベストアンサー率48% (730/1515)
手元のアセンブラマニュアルを見てみると、 PUSH命令が1～4クロック、 POP命令が1～6クロックで、わりと遅いです。 もっとも、これは486時代のデータなので、古くてあてになりません。 最近のCPUはパイプライン処理とかややこしいことをしているので、 はっきりと「何倍遅い」とは計算できないと思います。 そこをあえて考えてみると… まず、ソフトウェアスタックを実現するためには、 (1)ポインタの読み出し。 (2)スタックするデータを、ポインタが指すアドレスへ書き出す。 (3)ポインタをデータサイズ分加算。 (4)ポインタのメモリへの書き込み。 によってPUSH動作が行えます。(POPも同じようなもの) これらはあまり重い処理ではない(読み出し・書き込みは 486でも1クロックで実現できる)ので、 「遅くなるにしても、せいぜい4倍程度」 ではないかと思います。 これに加えて、スタックオーバーフローのチェックをする場合、 ・ポインタ制限値の読み込み。 ・ポインタ制限値とポインタ値の比較。 ・分岐命令。 などで、同じくらいかかる可能性があります。 これを考えに入れても せいぜい8倍程度ではないでしょうか。 最適化が働けば(たとえばポインタ値をレジスタに置いておくなど)、 もっと早くなる可能性はあります。 逆に、最適化がうまく行かなければ遅くなる可能性もあります。 パイプライン処理がうまく行くか行かないかも関係してきます。 というわけで、おもいっきり自信なしですが、 「オーバーフローチェックを入れてもせいぜい一ケタ弱の差」 というあたりかなあ…と思います。
関連するQ&A
- C# 再帰よるスタックオーバーフローについて
VB2008 C# でプログラムしていますが、 プログラムで再帰を多く行わなくてはならず、 スタックオーバーフローが出てしまいます。 スタックオーバーフローを解決するためには、アルゴリズムを変更し、 再帰の回数を減らすしか方法はないのでしょうか？ もしスタックの上限を変更する方法などがありましたら教えてください。 VBは初心者なので、なるべく簡単にお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- VC++ 再帰呼び出しについて
VC++6.0にてプログラミングを行っているものですが、 関数の再帰呼び出しについて質問です。 再帰呼び出しの際にスタックに積まれる変数というのは、 再帰呼び出しをする関数に渡す引数のことですか？ スタックオーバーフローを起こさないために、 staticなポインタにHeap領域上の 変数を割り当てるとよい。 と分かったのですが、 この意味は、例えば static int *a = new int; ということなのですか？
- ベストアンサー
- C・C++・C#
- 再帰を非再帰に実装しなおしたいです。
odd-even merge ソートを、再帰を用いずに実装したいです。 再帰有りの処理は以下のとおりの実装となります。 http://ideone.com/mAYt61 これを再帰無しの処理に実装し直したいのですが、（odd_even_mergesort関数一つにまとめたい） 上手く書けません。良い書き方を教えていただけますでしょうか？？
- ベストアンサー
- その他([技術者向] コンピューター)
- 関数呼び出しでのスタック消費量
C++で関数を再帰呼び出しするとスタックオーバーフローとなりました。 それで、どれ位なら可能か調べるため、次の関数で試してみました。 int null(void) { int a; return null(); } 結果は次の通りでした。 １回目 &a 0x001cf9d4 ２回目 &a 0x001cf8f4 ３回目 &a 0x001cf814 よって、一回の呼び出しでスタックをe0(224)バイト使用してるようです。 なぜ（何に）こんなにも多く使うのでしょうか？ 環境は、Vista Home Premium、Microsoft Visual C++ 2010 Express です。
- ベストアンサー
- C・C++・C#
- 再帰呼び出しになってしまうのをループの形にしたい
VBで繰り返して実行するプログラムを作ったのですが、 スタック領域をオーバーしてしまいます。 再帰呼び出しになっているのはわかったのですが、 改善ができません。 簡略したら下記のような状態でした。 Sub test1() test2 End Sub Sub test2() test1 End Sub このtest1を実行して、繰り返し作動するようにしたのですが、 当然スタックオーバーフローになります。 簡単にループに変形できるのでしょうか?
- ベストアンサー
- Visual Basic
- 組み込みOSでスタックオーバーフローしたら？
マイコンにて組み込みOSでスタックオーバーフローするとその振る舞いはどうなるのでしょうか？ SH2を使っています。 組み込みOSはNorti4を使っています。 タスク作成したときにスタック容量を指定しています。 タスクはひとつです。 タスクのスタックより前の領域には定義メモリ（グローバルメモリ）の領域になっています。 タスクのスタックより後の領域は大きな領域（数Kbyte）ほどあいています。 この場合にタスクのある関数の動作中にスタックオーバーフローが起きた場合、どうなるのでしょうか？ 思いついた選択肢は以下のとおりです。 1.定義メモリ（グローバルメモリ）の領域をオーバーフロー分書き換えて、その関数が終了したら呼び出し元の関数に戻る。 その後、書き換えられた定義メモリ（グローバルメモリ）による影響で処理によってはマイコンが意図しない動作になる。 2.スタックオーバーフローした時点でアドレス例外などの例外処理に飛んでしまう。 3.スタックオーバーフローした時点で、暴走し戻れなくなる。 4.その以外 どんなことが考えられますでしょうか？
- ベストアンサー
- その他(OS)
- 最大スタックサイズを大きくすることの影響は？
再帰呼び出しを行うプログラムでスタックオーバーフローが発生するようになりました。 そこで最大スタックサイズを変更しようと考えていますが 最大スタックサイズを大きくすることで何か影響があることはあるのでしょうか？ 他アプリ等に影響が出ないかを懸念しています。 ※最大スタックサイズは最大で16Mらしく、現在は1Mです。 特に影響がないのであれば最初から16Mにしておけば良いような気もして疑問に思っています。
- ベストアンサー
- C・C++・C#
- javaの再帰関数を用いるプログラミング
1セント，10セント，25セントのコインを好きな枚数使う事ができる． 1234セントを支払う時最低何枚で払うことが出来るか？再帰関数を用いて現実的な速度で動くプログラムをjavaを使って作ってください！ どうぞ宜しくお願いします！
- ベストアンサー
- Java
- スタックを用いたプログラム
http://okwave.jp/qa4433705.html 先日教えて戴いた事でスタックがどういったものなのかは わかりましたが、実際にプログラムを作ってみると、 なかなかうまくいけません。再びアドバイスを戴ければと思ってます。 ＜プログラムの仕様＞ 入力数値をスタックに格納し'a'が入力されたら、 スタックに格納されている数値を全て取り出し、 平均値を出力するプログラム ・スタックは、push()関数およびpop()関数を実装する ・スタックへの要素の追加はpush()関数で行う ・スタックからの要素の取出はpop()関数で行う ・スタックのサイズは任意とする int push(int push_data); 引数: スタックに追加するデータ 戻り値: 成功の場合1、失敗の場合0を返す int pop(int *pop_data); 引数: スタックから取り出した値を格納するポインタ 戻り値: 成功の場合1、失敗の場合0を返す いざ、自分で作ってみると、 仕様通りには全く作れず、結局main関数ですべてを作って しまうことになってしまいます・・
- ベストアンサー
- C・C++・C#
- gccでスタックオーバーフローのチェック
OS:WindowsXP コンパイラ: MinGW gcc 3.3.3 gccで、スタックオーバーフローの検出を行いたいと思っています。 gcc -v --helpで見ると > -fstack-check Insert stack checking code into the program と書かれているので、そのように指定して、無限に自分を呼び続ける再帰のプログラムを走らせてみました。 gcc -fstack-check testS2.c ですが、オプションを指定しない時と同じように突然何の前触れもなく終了してしまいます。 このオプションはスタックを使い切るかどうかをチェックするオプションではないのでしょうか。 よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
お礼
2ケタの速度差があるインタプリタがあることを考えれば、一ケタで収まるのは意外でした。ありがとうございます。