Почему максимальная глубина рекурсии я могу достичь недетерминированной?

Я решил попробовать несколько экспериментов, чтобы узнать, что я могу узнать о размере фреймов стека, и о том, как далеко через стек выполнялся текущий исполняемый код. Здесь есть два интересных вопроса:

  • Сколько уровней в стеке является текущим кодом?
  • Сколько уровней рекурсии может достичь текущего метода до того, как он достигнет значения StackOverflowError?

Глубина стека текущего исполняемого кода

Вот лучшее, что я мог бы придумать для этого:

public static int levelsDeep() {
    try {
        throw new SomeKindOfException();
    } catch (SomeKindOfException e) {
        return e.getStackTrace().length;
    }
}

Это кажется немного взломанным. Он генерирует и ловит исключение, а затем смотрит, какая длина трассировки стека.

К сожалению, у него также есть фатальное ограничение, которое заключается в том, что максимальная длина возвращаемой трассировки стека равна 1024. Все, что выходит за рамки этого, опускается, поэтому максимум, который может вернуть этот метод, равен 1024.

Вопрос:

Есть ли лучший способ сделать это, что не так хаки и не имеет этого ограничения?

Для чего я думаю, что нет: Throwable.getStackTraceDepth() - это родной вызов, который предлагает (но не доказывает), что это невозможно сделать в чистой Java.

Определение того, насколько мы оставили оставшуюся глубину рекурсии

Количество уровней, которые мы можем достичь, будет определяться (а) размером кадра стека и (б) количеством оставшегося стека. Давайте не будем беспокоиться о размере фрейма стека и просто посмотрим, сколько уровней мы можем достичь, прежде чем мы нажмем 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-bit). Но 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?

Ответы

Ответ 1

Наблюдаемое поведение зависит от оптимизатора 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

Значения по-прежнему изменяются, но не в пределах одного потока выполнения и с меньшей величиной.

Таким образом, существует (довольно небольшая) разница, которая становится намного больше, если оптимизатор может уменьшить пространство стека, необходимое для вызова метода, например. из-за inlining.

Что может вызвать такую ​​разницу? Я не знаю, как это работает JVM, но один сценарий может заключаться в том, что способ ограничения стека требует определенного выравнивания конечного адреса стека (например, соответствующего размера страницы памяти), в то время как распределение памяти возвращает память с начальным адресом, который имеет более слабая гарантия выравнивания. Объедините такой сценарий с ASLR, и в пределах размера требования выравнивания всегда может быть разница.

Ответ 2

Why is the maximum recursion depth non-deterministic on Oracle Java 8? And why is it deterministic on OpenJDK 7?

Об этом, возможно, относится к изменениям в сборке мусора. Java может выбирать другой режим для gc каждый раз. http://vaskoz.wordpress.com/2013/08/23/java-8-garbage-collectors/

Ответ 3

Это устарело, но вы можете попробовать Thread.countStackFrames(), например

public static int levelsDeep() {
    return Thread.currentThread().countStackFrames();       
}

В Javadoc,

Устаревшие. Определение этого вызова зависит от suspend(), который устарел. Кроме того, результаты этого вызова никогда не были четко определены.

Подсчитывает количество кадров стека в этом потоке. Нить должна быть приостановлена.

Что касается того, почему вы наблюдаете недетерминированное поведение, я могу только предположить, что это некоторая комбинация JIT и сборщика мусора.

Ответ 4

Вам не нужно улавливать исключение, просто создайте его вот так:

new Throwable(). getStackTrace()

Или:

Thread.currentThread(). GetStackTrace()

Он по-прежнему взломан, поскольку результат специфичен для JVM. И JVM может решить обрезать результат для лучшей производительности.