递归方法的间歇性堆栈溢出

Question

我为课堂作业编写了一个简单的方法，该方法使用递归(是的，它必须使用递归)来计算分形模式中的三角形数量：

public static BigInteger triangleFract(int layer) {
if(layer < 0) {
throw new IllegalArgumentException("Input must be >= 0");
} else if(layer == 0) {
return new BigInteger("0");
} else if (layer == 1) {
return new BigInteger("1");
} else {
return triangleFract(layer - 1)
.multiply(new BigInteger("3"))
.add(new BigInteger("2"));
}
}

我一直在尝试了解int层的大小，以便限制用户输入。经过一些测试，我得到了大约6700+的堆栈溢出，这很好。

让我困扰的是，如果层是数千层，该方法通常会运行，但它仍然可以随机遇到StackOverflowError。

例如，我选择将层限制为4444，它似乎总是能够处理这个问题，但每隔一段时间它似乎仍然会溢出。

它为什么要这样做？对此我能做些什么吗？

Answer 1

也许JVM已经确定(通过转义分析)BigInteger可以在堆栈上而不是堆上分配。根据何时实现此优化，所需的堆栈大小会有所不同。

也就是说，可能还有许多其他原因，行为可能取决于您使用的JVM。

Answer 2

考虑转移到迭代版本。我认为，如果您开发递归算法，则必须控制级别深度，否则根本不使用递归。

Answer 3

实际上您可以做一些事情：增加最大堆栈大小。这是在JVM启动时使用-Xss选项完成的，如下所示：

java -Xss40m MainClass

注意不要设置过高的值。如果你必须超过60M-70M，那么建议重新设计你的代码。

Answer 4

我无法重现你的"波动"效果。这是非常具有确定性的代码，所以每次都应该得到相同的结果(包括堆栈溢出错误)。

你是怎么测试的？您是否为4444测试的每次尝试都运行了一个新的jvm？(或者它只是三角Frac(4444)；循环调用？)。

你的操作系统、java版本等是什么…

我之所以这么问，是因为我真的不喜欢这样尚未解决的问题——这样的事情可能会在哪里(什么时候)刺痛你；)。

哦。。。顺便说一句，值得一提的是，你应该使用BigInteger中的1和ZERO常量(并为2和3创建自己的常量)。这应该会节省你相当多的内存(是的，我知道，这不是你的问题)。

Answer 5

允许递归到深度是一种设计气味。

试试这个迭代版本：

public static BigInteger triangleFract(int layer) {
if (layer < 0) {
throw new IllegalArgumentException("Input must be >= 0");
}
if (layer == 0) {
return BigInteger.ZERO;
}
BigInteger result = BigInteger.ONE;
BigInteger two = new BigInteger("2");
BigInteger three = new BigInteger("3");
for (int i = 1; i < layer; i++) {
result = result.multiply(three).add(two);
}
return result;
}

注：

• 使用BigInteger.ZERO和BigInteger.ONE，而不是为这些值创建新实例
• 删除了冗余的else-在终止语句(例如return)之后没有else
• 重新使用new BigInteger("2")和new BigInteger("3")，而不是每次迭代都创建新实例

Answer 6

对于那些无法重现这种波动的人。从哪个方法可靠地抛出StackOverflowError开始，查找layer值。该值越接近实际阈值越好。现在从循环内部调用这个方法(在我的机器maxLayer = 11500上)：

int i = 11500;
while (true) {
System.out.println(i);
triangleFract(i++);
}

它将抛出StackOverflowError。现在稍微降低这个值(看起来5-10%就足够了)：

int i = 10500;
while (true) {
System.out.println(i);
triangleFract(i++);
}

在我的机器上，这不会引发任何错误，并且成功地跳过了11500。事实上，它一直工作到16000。

因此，不管是什么，都可能涉及JVM优化。我试着用-XX:+PrintCompilation运行一个程序。我看到JIT如何在循环时完成它的工作：

117   1       java.lang.String::hashCode (64 bytes)
183   2       java.lang.String::charAt (33 bytes)
189   3       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
201   4       java.math.BigInteger::mulAdd (81 bytes)
205   5       java.math.BigInteger::multiplyToLen (219 bytes)
211   6       java.math.BigInteger::addOne (77 bytes)
215   7       java.math.BigInteger::squareToLen (172 bytes)
219   8       java.math.BigInteger::primitiveLeftShift (79 bytes)
224   9       java.math.BigInteger::montReduce (99 bytes)
244  10       sun.security.provider.SHA::implCompress (491 bytes)
280  11       sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (490 bytes)
282  12       java.lang.String::equals (88 bytes) 11400
289  13       java.lang.String::indexOf (151 bytes)
293  14       java.io.UnixFileSystem::normalize (75 bytes)
298  15       java.lang.Object::<init> (1 bytes)
298  16       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
299  17       java.lang.CharacterDataLatin1::getProperties (11 bytes)
300  18       NormalState::triangleFract (74 bytes)
308  19       java.math.BigInteger::add (178 bytes)
336  20       java.lang.String::lastIndexOf (151 bytes)
337  21       java.lang.Number::<init> (5 bytes)
338  22       java.lang.Character::digit (6 bytes)
340  23       java.lang.Character::digit (168 bytes)
342  24       java.lang.CharacterDataLatin1::digit (85 bytes)
343  25       java.math.BigInteger::trustedStripLeadingZeroInts (37 bytes)
357  26       java.lang.String::substring (83 bytes)
360  27       java.lang.String::lastIndexOf (10 bytes)
360  28       java.lang.String::lastIndexOf (29 bytes)
361  29       java.math.BigInteger::<init> (24 bytes)
361  30       java.lang.Integer::parseInt (269 bytes)
361  31       java.math.BigInteger::<init> (8 bytes)
362  32       java.math.BigInteger::<init> (347 bytes)
404  33       java.math.BigInteger::multiply (72 bytes)
404  34       java.math.BigInteger::add (123 bytes)

可能是编译吗？让我们试着推迟编译，以便它尽可能晚地影响我们。我尝试使用-XX:CompileThreshold标志，很快就找到了一个值(-XX:CompileThreshold=1000000)，它不会让我的循环跳过11500。

更新

我终于在没有任何编译阈值调整的情况下复制了它。对我来说，它看起来只有当我在IDE(IntelliJ IDEA)中运行程序时才会发生。因此，这可能与IDEA的发射器有关。我复制了它的命令行，并在一个小脚本中使用它：

for I in `seq 1 100`; do 
java ... com.intellij.rt.execution.application.AppMain 
Triangle 2>&1| grep Stack; done | wc -l

我发现它通常打印出不到100(95-98)的东西。这与我手动操作时看到的一致。当我跳过启动器时：

for I in `seq 1 100`; do 
java 
Triangle 2>&1| grep Stack; done | wc -l

它总是打印出100。