Scala 递归深度差异和低于允许深度的 StackOverflowError

Question

编写以下程序是为了检查 Scala 中的递归在我的机器上可以深入到什么程度。我认为这主要取决于分配给该程序的堆栈大小。但是，在计算了最大递归深度（出现异常时捕获异常）并尝试模拟该深度的递归后，我得到了奇怪的输出。

object RecursionTest {

  def sumArrayRec(elems: Array[Int]) = {

    def goFrom(i: Int, size: Int, elms: Array[Int]): Int = {
      if (i < size) elms(i) + goFrom(i + 1, size, elms)
      else 0
    }
    goFrom(0, elems.length, elems)
  }

  def main(args: Array[String]) {
    val recDepth = recurseTest(0, 0, Array(1))
    println("sumArrayRec = " + sumArrayRec((0 until recDepth).toArray))
  }

  def recurseTest(i: Int, j: Int, arr: Array[Int]): Int = {
    try {
      recurseTest(i + 1, j + 1, arr)
    } catch { case e: java.lang.WhosebugError =>
      println("Recursion depth on this system is " + i + ".")
      i
    }
  }

}

结果因程序的执行而异。

其中一个是理想的输出：

/usr/lib/jvm/java-8-oracle/bin/java

Recursion depth on this system is 7166.
sumArrayRec = 25672195

Process finished with exit code 0

然而，我得到的第二个可能的输出指示错误：

/usr/lib/jvm/java-8-oracle/bin/java

Recursion depth on this system is 8129.
Exception in thread "main" java.lang.WhosebugError
    at RecursionTest$.goFrom(lab44.scala:6)
    at RecursionTest$.goFrom(lab44.scala:6)
    at RecursionTest$.goFrom(lab44.scala:6)
    (...)
    at RecursionTest$.goFrom(lab44.scala:6)
    at RecursionTest$.goFrom(lab44.scala:6)

Process finished with exit code 1

我没有观察到它们之间有任何依赖或关系，我只是第一次得到第一个，其他时候得到第二个

所有这些让我想到了以下问题：

为什么我会收到错误消息？是什么原因导致的？
这是堆栈溢出错误吗，如果是...
为什么程序在运行时栈的大小会同时变化？有可能吗？

当我把println("sumArrayRec = " + sumArrayRec((0 until recDepth).toArray))改成 println("sumArrayRec = " + sumArrayRec((0 until recDepth - 5000).toArray))，更不用说了，行为保持不变。

Answer 1

你得到堆栈溢出是因为你导致了堆栈溢出
是
最大堆栈不变，JVM 对此进行设置。您的两种方法 recurseTest 和 sumArrayRec 将不同的数量压入堆栈。 recurseTest 基本上 在每次调用时添加 2 个整数，而 sumArrayRec 添加 3 个整数，因为您调用了 elms(i)，可能更多addition/ifelse（更多说明）。很难说清楚，因为 JVM 正在处理所有这些，它的目的是使您无法了解这一点。此外，谁知道 JVM 在幕后进行了哪些优化，这会极大地影响从每个方法调用创建的堆栈大小。在多个运行上，由于系统时序等原因，您将获得不同的堆栈深度，也许 jvm 会在程序具有运行的短时间内进行优化，也许不会，它是不确定的在这种情况下。如果您运行一些预热代码可能会使您的测试更具确定性，那么任何优化都会或不会发生。

您应该考虑使用 JMH 之类的东西进行测试，这将有助于确定性。

旁注：您还可以使用 -Xss2M 手动更改筹码量，这对于 SBT 用法很常见。

Scala 递归深度差异和低于允许深度的 StackOverflowError

Scala recursion depth differences and StackOverflowError below allowed depth

stack-overflow

recursion

jvm

scala