49

再帰メソッドが特定の量のメモリで達成できる最大呼び出し深度を推定する目的で、スタック オーバーフロー エラーが発生する可能性が高くなる前に使用されるメモリを計算するための (概算) 式は何ですか?

編集：

多くの人が「場合による」と答えていますが、これは合理的です。そのため、些細だが具体的な例を使用して、いくつかの変数を削除しましょう。

public static int sumOneToN(int n) {
    return n < 2 ? 1 : n + sumOneToN(n - 1);
}

私の Eclipse IDE でこれを実行すると、n1000 をわずかに下回ります (私には驚くほど低い) ことは簡単に示せます。この呼び出しの深さ制限は、実行せずに見積もることができますか?

998編集: Eclipse の最大呼び出し深度は 1000 に固定されていると思わずにはいられません1000。これは「丸すぎる」数字であり、偶然とは言えません。さらに調査します。-Xss vm パラメータの Dux オーバーヘッドがあります。これは最大スタック サイズであるため、Eclipse ランナーは-Xss1000どこかに設定されている必要があります

4

6 に答える 6

25

これは明らかに JVM 固有であり、おそらくアーキテクチャ固有でもあります。

以下を測定しました。

  static int i = 0;
  public static void rec0() {
      i++;
      rec0();
  }

  public static void main(String[] args) {
      ...
      try {
          i = 0; rec0();
      } catch (StackOverflowError e) {
          System.out.println(i);
      }
      ...
  }

使用して

Java(TM) SE Runtime Environment (build 1.7.0_09-b05)
Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode)

x86 で動作します。

20MB の Java スタック ( -Xss20m) では、償却コストは呼び出しごとに約 16 ～ 17 バイト変動しました。私が見た最低は 16.15 バイト/フレームでした。したがって、コストは 16 バイトで、残りはその他の (固定) オーバーヘッドであると結論付けます。

シングルを取る関数は、int基本的に同じコストで、16 バイト/フレームです。

興味深いことに、10 をints要する関数には 32 バイト/フレームが必要です。なぜこんなにコストが安いのかわからない。

上記の結果は、コードが JIT コンパイルされた後に適用されます。コンパイル前のフレームあたりのコストは、はるかに高くなります。私はまだそれを確実に推定する方法を考え出していません。ただし、これは、再帰関数が JIT コンパイルされているかどうかを確実に予測できるまで、再帰の最大深度を確実に予測できる見込みがないことを意味します。

ulimitこれらはすべて、 128K および 8MBのスタック サイズでテストされました。どちらの場合も結果は同じでした。

于 2012-12-21T19:24:12.270 に答える
10

部分的な回答のみ: JVM Spec 7, 2.5.2から、スタック フレームをヒープに割り当てることができ、スタック サイズは動的である可能性があります。確かなことは言えませんが、スタックサイズをヒープサイズのみに制限することは可能であるようです:

Java 仮想マシン スタックは、フレームのプッシュとポップを除いて直接操作されることはないため、フレームがヒープに割り当てられる場合があります。

と

この仕様では、Java 仮想マシン スタックを固定サイズにすることも、計算の必要に応じて動的に拡張および縮小することもできます。Java 仮想マシン スタックのサイズが固定されている場合、各 Java 仮想マシン スタックのサイズは、スタックの作成時に個別に選択できます。

Java 仮想マシンの実装では、プログラマーまたはユーザーが Java 仮想マシン スタックの初期サイズを制御できるほか、Java 仮想マシン スタックを動的に拡張または縮小する場合は、最大サイズと最小サイズを制御できます。

したがって、それはJVMの実装次第です。

于 2012-12-21T19:20:37.043 に答える
4

NPEの回答に追加：

最大スタック深度は柔軟なようです。次のテスト プログラムは、大きく異なる数値を出力します。

public class StackDepthTest {
    static int i = 0;

    public static void main(String[] args) throws Throwable {
        for(int i=0; i<10; ++i){
            testInstance();
        }
    }

    public static void testInstance() {
        StackDepthTest sdt = new StackDepthTest();
        try {
            i=0;
            sdt.instanceCall();
        } catch(StackOverflowError e){}
        System.out.println(i);
    }

    public void instanceCall(){
        ++i;
        instanceCall();
    }
}

出力は次のとおりです。

10825
10825
59538
59538
59538
59538
59538
59538
59538
59538

この JRE のデフォルトを使用しました。

java version "1.7.0_09"
OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu1~12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

結論は: 膿が十分に (つまり、2 回以上) ある場合は、2 回目のチャンスがあります ;-)

于 2012-12-21T20:14:38.297 に答える
3

答えは、すべて依存するということです。

まず、Java スタックのサイズを変更できます。

第 2 に、特定のメソッドのスタック フレーム サイズは、さまざまな変数に基づいて変化する可能性があります。詳細については、コール スタック - ウィキペディアの「コール スタック フレーム サイズ」セクションを参照してください。

于 2012-12-21T19:21:10.030 に答える
2

経験的な道をたどって、コードと-Xss設定を試すことができます。詳細については、こちらを参照してください: JVM オプション -Xss - 正確には何をしますか?

于 2012-12-21T19:29:10.140 に答える
2

システムアーキテクチャ（32または64ビットアドレス）、ローカル変数の量、およびメソッドのパラメーターによって異なります。末尾再帰の場合 、コンパイラがループに最適化する場合、オーバーヘッドはありません。

ほら、簡単な答えはありません。

于 2012-12-21T19:21:35.870 に答える