为什么最大递归深度我可以达到非确定性?
我决定尝试一些实验,看看我能发现堆栈帧的大小,以及当前执行代码在堆栈中的距离。 我们可能会在这里调查两个有趣的问题:
- 当前代码的深度是多少级别?
- 当前方法遇到
StackOverflowError
之前可以达到多少级别的递归?
堆栈当前执行代码的深度
这是我能想到的最好的:
public static int levelsDeep() { try { throw new SomeKindOfException(); } catch (SomeKindOfException e) { return e.getStackTrace().length; } }
这看起来有点黑客。 它生成并捕获exception,然后查看堆栈跟踪的长度。
不幸的是,它似乎也有一个致命的限制,即返回的堆栈跟踪的最大长度为1024.除此之外的任何内容都被削减,因此此方法可以返回的最大值为1024。
题:
有没有更好的方法做到这一点,不是那么hacky并没有这个限制?
对于它的价值,我的猜测是没有: Throwable.getStackTraceDepth()
是一个本机调用,它建议(但不能certificate)它不能用纯Java完成。
确定我们剩下多少递归深度
我们可以达到的等级数量将由(a)堆栈帧的大小和(b)剩余堆栈量确定。 让我们不要担心堆栈帧的大小,只需看看在我们遇到StackOverflowError
之前我们可以达到多少级别。
这是我执行此操作的代码:
public static int stackLeft() { try { return 1+stackLeft(); } catch (StackOverflowError e) { return 0; } }
它的工作令人钦佩,即使它在堆栈剩余量方面是线性的。 但这是非常非常奇怪的部分。 在64位Java 7(OpenJDK 1.7.0_65)上,结果完全一致:9,923,在我的机器上(Ubuntu 14.04 64位)。 但Oracle的Java 8(1.8.0_25)给出了非确定性的结果 :我的记录深度在18,500到20,700之间。
现在为什么它是不确定的呢? 应该有一个固定的堆栈大小,不是吗? 并且所有代码对我来说都是确定性的。
我想知道错误捕获是否奇怪,所以我尝试了这个:
public static long badSum(int n) { if (n==0) return 0; else return 1+badSum(n-1); }
显然,这将返回给定的输入或溢出。
同样,我得到的结果在Java 8上是非确定性的。如果我调用badSum(14500)
,它将给我一个StackOverflowError
大约一半的时间,并返回14500另一半。 但是在Java 7 OpenJDK上,它是一致的: badSum(9160)
完成正常, badSum(9161)
溢出。
题:
为什么Oracle Java 8上的最大递归深度不确定? 为什么OpenJDK 7确定性?
观察到的行为受HotSpot优化器的影响,但它不是唯一的原因。 当我运行以下代码时
public static void main(String[] argv) { System.out.println(System.getProperty("java.version")); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); } static int countDepth() { try { return 1+countDepth(); } catch(StackOverflowError err) { return 0; } }
启用JIT后,我得到的结果如下:
> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -cp build\classes X 1.8.0_40-ea 2097 4195 4195 4195 12587 12587 12587 > f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -cp build\classes X 1.8.0_40-ea 2095 4193 4193 4193 12579 12579 12579 > f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -cp build\classes X 1.8.0_40-ea 2087 4177 4177 12529 12529 12529 12529
在这里,JIT的效果清晰可见,显然优化的代码需要更少的堆栈空间,并且显示分层编译已启用(实际上,使用-XX:-TieredCompilation
如果程序运行足够长则显示单个跳转)。
相反,对于禁用的JIT,我得到以下结果:
> f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -Xint -cp build\classes X 1.8.0_40-ea 2104 2104 2104 2104 2104 2104 2104 > f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -Xint -cp build\classes X 1.8.0_40-ea 2076 2076 2076 2076 2076 2076 2076 > f:\Software\jdk1.8.0_40beta02\bin\java -Xss68k -server -Xint -cp build\classes X 1.8.0_40-ea 2105 2105 2105 2105 2105 2105 2105
值仍然有所不同,但不在单个运行时线程内且幅度较小。
因此,如果优化器可以减少每个方法调用所需的堆栈空间(例如由于内联),则存在(相当小的)差异变得更大。
什么能造成这样的差异? 我不知道这个JVM是如何做到的,但是一种情况可能是强制执行堆栈限制的方式需要堆栈结束地址的某种对齐(例如匹配内存页面大小),而内存分配返回内存的起始地址对齐保证较弱。 将这种情况与ASLR结合起来可能总是存在差异,在对齐要求的大小范围内。
Why is the maximum recursion depth non-deterministic on Oracle's Java 8? And why is it deterministic on OpenJDK 7?
关于这一点,可能与垃圾收集的变化有关。 Java每次都可以为gc选择不同的模式。 http://vaskoz.wordpress.com/2013/08/23/java-8-garbage-collectors/
它已被弃用,但您可以尝试Thread.countStackFrames()
类的
public static int levelsDeep() { return Thread.currentThread().countStackFrames(); }
根据Javadoc,
不推荐 。 此调用的定义取决于不推荐使用的
suspend()
。 此外,这一呼吁的结果从未明确定义。计算此线程中的堆栈帧数。 线程必须暂停。
至于为什么你会观察到非确定性行为,我只能假设它是JIT和垃圾收集器的某种组合。
您不需要捕获exception,只需创建一个这样的:
new Throwable()。getStackTrace()
要么:
Thread.currentThread()。的getStackTrace()
它仍然是hacky,因为结果是特定于JVM实现。 JVM可能会决定调整结果以获得更好的性能。