Почему количество вызовов рекурсивного метода, вызывающего StackOverflowError, различается между прогонами программы?

Ответ 1

Наблюдаемая дисперсия вызвана базой JIT-компиляцией.

Вот как выглядит процесс:

• Метод f() запускает выполнение в интерпретаторе.
• После нескольких вызовов (около 250) метод запланирован для компиляции.
• Поток компилятора работает параллельно с потоком приложения. Тем временем метод продолжает выполнение в интерпретаторе.
• Как только компилятор завершит компиляцию, точка входа метода будет заменена, поэтому следующий вызов f() вызовет скомпилированную версию метода.

Существует обычная гонка между потоком applcation и потоком компилятора JIT. Интерпретатор может выполнять различное количество вызовов до того, как скомпилированная версия метода будет готова. В конце есть сочетание интерпретируемых и скомпилированных кадров.

Неудивительно, что скомпилированная структура фрейма отличается от интерпретируемой. Скомпилированные фреймы обычно меньше; им не нужно сохранять весь контекст выполнения в стеке (ссылка на метод, постоянная ссылка пула, данные профилировщика, все аргументы, переменные выражения и т.д.)

Более того, существует еще больше возможностей гонки с многоуровневой компиляцией (по умолчанию с JDK 8). Может быть комбинация из трех типов фреймов: интерпретатор, C1 и C2 (см. Ниже).

Пусть у нас есть интересные эксперименты для поддержки теории.

• Чистый интерпретируемый режим. Нет компиляции JIT.
  Нет расов = > стабильные результаты.

  $ java -Xint Main
  11895
  11895
  11895
  

• Отключить компиляцию фона. JIT включен, но синхронизирован с потоком приложения.
  Нет гонок снова, но количество вызовов теперь выше из-за скомпилированных кадров.

  $ java -XX:-BackgroundCompilation Main
  23462
  23462
  23462
  

• Скомпилируйте все с C1 перед выполнением. В отличие от предыдущего случая, в стеке не будет интерпретированных фреймов, поэтому число будет немного выше.

  $ java -Xcomp -XX:TieredStopAtLevel=1 Main
  23720
  23720
  23720
  

• Теперь скомпилируйте все с C2 перед выполнением. Это создаст наиболее оптимизированный код с самым маленьким фреймом. Количество вызовов будет наивысшим.

  $ java -Xcomp -XX:-TieredCompilation Main
  59300
  59300
  59300
  

  Поскольку размер стека по умолчанию равен 1M, это означает, что теперь размер кадра составляет всего 16 байтов. Это?

  $ java -Xcomp -XX:-TieredCompilation -XX:CompileCommand=print,Main.f Main
  
    0x00000000025ab460: mov    %eax,-0x6000(%rsp)    ; StackOverflow check
    0x00000000025ab467: push   %rbp                  ; frame link
    0x00000000025ab468: sub    $0x10,%rsp            
    0x00000000025ab46c: movabs $0xd7726ef0,%r10      ; r10 = Main.class
    0x00000000025ab476: addl   $0x2,0x68(%r10)       ; Main.counter += 2
    0x00000000025ab47b: callq  0x00000000023c6620    ; invokestatic f()
    0x00000000025ab480: add    $0x10,%rsp
    0x00000000025ab484: pop    %rbp                  ; pop frame
    0x00000000025ab485: test   %eax,-0x23bb48b(%rip) ; safepoint poll
    0x00000000025ab48b: retq
  

  Фактически, кадр здесь составляет 32 байта, но JIT имеет один уровень рекурсии.

• Наконец, рассмотрим трассировку смешанного стека. Чтобы получить его, мы будем разбивать JVM на StackOverflowError (опция доступна в отладочных сборках).

  $ java -XX:AbortVMOnException=java.lang.StackOverflowError Main
  

  Дамп аварийного останова hs_err_pid.log содержит подробную трассировку стека, в которой мы можем найти интерпретированные фреймы внизу, рамки C1 в середине и, наконец, C2-фреймы сверху.

  Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
  J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5958 [0x00007f21251a5900+0x0000000000000058]
  J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5920 [0x00007f21251a5900+0x0000000000000020]
    // ... repeated 19787 times ...
  J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5920 [0x00007f21251a5900+0x0000000000000020]
  J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
  J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
    // ... repeated 1866 times ...
  J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
  j  Main.f()V+8
  j  Main.f()V+8
    // ... repeated 1839 times ...
  j  Main.f()V+8
  j  Main.main([Ljava/lang/String;)V+0
  v  ~StubRoutines::call_stub
  

Ответ 2

Прежде всего, не было исследовано следующее. Я не "глубоко погрузился" в исходный код OpenJDK для проверки любого из следующего, и у меня нет доступа к каким-либо внутренним знаниям.

Я попытался проверить ваши результаты, выполнив тест на своей машине:

$ java -version
openjdk version "1.8.0_71"
OpenJDK Runtime Environment (build 1.8.0_71-b15)
OpenJDK 64-Bit Server VM (build 25.71-b15, mixed mode)

Я получаю "счет", изменяющийся в диапазоне ~ 250. (Не так много, как вы видите)

Сначала немного фона. Стек потока в типичной реализации Java представляет собой смежную область памяти, которая выделяется до начала потока, и которая никогда не выращивается и не перемещается. Переполнение стека происходит, когда JVM пытается создать фрейм стека для вызова метода, и кадр выходит за пределы области памяти. Тест может быть сделан путем тестирования SP явно, но я понимаю, что он обычно реализуется с помощью умного трюка с настройками страницы памяти.

Когда выделена область стека, JVM делает syscall, чтобы сообщить OS отметить страницу "красной зоны" в конце области стека, доступной только для чтения или не доступной. Когда поток выполняет вызов, который переполняет стек, он обращается к памяти в "красной зоне", которая вызывает ошибку памяти. ОС сообщает JVM через "сигнал", а обработчик сигнала JVM сопоставляет его с StackOverflowError, который "бросается" в стек потока.

Итак, вот несколько возможных объяснений изменчивости:

• Зеркальность аппаратной защиты памяти - это граница страницы. Поэтому, если поток потока был выделен с помощью malloc, начало области не будет выравниваться по странице. Поэтому расстояние от начала кадра стека до первого слова "красной зоны" (которое > выравнивается по странице) будет переменной.

• "Основной" стек потенциально особенный, поскольку этот регион может использоваться, когда JVM является начальной загрузкой. Это может привести к тому, что некоторые "вещи" останутся в стеке до того, как был вызван main. (Это не убедительно... и я не уверен.)

Сказав это, "большая" изменчивость, которую вы видите, озадачивает. Размеры страниц слишком малы, чтобы объяснить разницу в 7000 в подсчетах.

UPDATE

Когда JIT отключен (-Djava.compiler = NONE), я всегда получаю тот же номер (11907).

Интересно. Помимо прочего, это может привести к тому, что проверка ограничения стека будет выполняться по-разному.

Это имеет смысл, поскольку оптимизация JIT, вероятно, влияет на размер кадров стека, и работа, выполняемая JIT, определенно должна варьироваться между исполнениями.

правдоподобно. Размер стекового кадра может быть различным после того, как метод f() был скомпилирован JIT. Предполагая, что f() был JIT, скомпилированный в какой-то момент, у вас будет смесь "старых" и "новых" фреймов. Если компиляция JIT произошла в разных точках, тогда отношение будет отличаться... и, следовательно, count будет отличаться при достижении предела.

Тем не менее, я думаю, было бы полезно, если бы эта теория была подтверждена ссылками на некоторую документацию о теме и/или конкретными примерами работы, выполненной JIT в этом конкретном примере, что приводит к изменениям размера кадра.

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

1) Нет такой (общедоступной) справочной документации, AFAIK. По крайней мере, я никогда не мог найти окончательного источника для такого рода вещей... кроме глубокого погружения исходного кода.

2) Глядя на скомпилированный код JIT, вы ничего не знаете о том, как интерпретатор байт-кода обрабатывал вещи до того, как код был скомпилирован JIT. Таким образом, вы не сможете увидеть, изменился ли размер фрейма.

Ответ 3

Точное функционирование Java-пакета недокументировано, но оно полностью зависит от памяти, выделенной этому потоку.

Просто попробуйте использовать конструктор Thread со стекированием и посмотрите, будет ли он постоянным. Я не пробовал это, поэтому, пожалуйста, поделитесь результатами.