¿Cómo boost el tamaño de la stack de Java?

Hice esta pregunta para saber cómo boost el tamaño de la stack de llamadas en tiempo de ejecución en la JVM. Tengo una respuesta a esto, y también tengo muchas respuestas útiles y comentarios relevantes sobre cómo maneja Java la situación donde se necesita una gran stack de tiempo de ejecución. He extendido mi pregunta con el resumen de las respuestas.

Originalmente quería boost el tamaño de la stack JVM para que los progtwigs se ejecuten sin StackOverflowError .

 public class TT { public static long fact(int n) { return n < 2 ? 1 : n * fact(n - 1); } public static void main(String[] args) { System.out.println(fact(1 << 15)); } } 

La configuración de configuración correspondiente es java -Xss... indicador de línea de comando con un valor suficientemente grande. Para el progtwig TT anterior, funciona así con OpenJDK’s JVM:

 $ javac TT.java $ java -Xss4m TT 

Una de las respuestas también ha señalado que las banderas -X... dependen de la implementación. Estaba usando

 java version "1.6.0_18" OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1~8.04.3) OpenJDK 64-Bit Server VM (build 16.0-b13, mixed mode) 

También es posible especificar una gran stack solo para una cadena (ver en una de las respuestas cómo). Esto se recomienda sobre java -Xss... para evitar desperdiciar memoria para hilos que no lo necesitan.

Tenía curiosidad por la cantidad de una stack que el progtwig de arriba necesita exactamente, así que la he ejecutado n aumentado:

  • -Xss4m puede ser suficiente para los fact(1 << 15)
  • -Xss5m puede ser suficiente para los fact(1 << 17)
  • -Xss7m puede ser suficiente para los fact(1 << 18)
  • -Xss9m puede ser suficiente para los fact(1 << 19)
  • -Xss18m puede ser suficiente para los fact(1 << 20)
  • -Xss35m puede ser suficiente por fact(1 << 21)
  • -Xss68m puede ser suficiente para los fact(1 << 22)
  • -Xss129m puede ser suficiente para los fact(1 << 23)
  • -Xss258m puede ser suficiente para los fact(1 << 24)
  • -Xss515m puede ser suficiente para los fact(1 << 25)

A partir de los números anteriores, parece que Java está utilizando alrededor de 16 bytes por marco de stack para la función anterior, lo cual es razonable.

La enumeración anterior puede ser suficiente en lugar de suficiente porque el requisito de la stack no es determinista: ejecutarlo varias veces con el mismo archivo fuente y el mismo -Xss... veces tiene éxito y algunas veces genera un StackOverflowError . Por ejemplo, para 1 << 20, -Xss18m fue suficiente en 7 carreras de 10, y -Xss19m tampoco siempre fue suficiente, pero -Xss20m fue suficiente (en todas las 100 carreras de las 100). ¿La recolección de basura, el JIT, o algo más causa este comportamiento no determinista?

El seguimiento de stack impreso en StackOverflowError (y posiblemente en otras excepciones también) muestra solo los 1024 elementos más recientes de la stack de tiempo de ejecución. Una respuesta a continuación demuestra cómo contar la profundidad exacta alcanzada (que podría ser mucho mayor que 1024).

Muchas personas que respondieron han señalado que es una buena y segura práctica de encoding considerar implementaciones alternativas, menos aptas para la stack, del mismo algoritmo. En general, es posible convertir un conjunto de funciones recursivas a funciones iterativas (usando un objeto Stack , por ejemplo, que se rellena en el montón en lugar de en la stack de tiempo de ejecución). Para esta función de fact particular, es bastante fácil de convertir. Mi versión iterativa se vería así:

 public class TTIterative { public static long fact(int n) { if (n  65) return 0; // Enough powers of 2 in the product to make it (long)0. long f = 2; for (int i = 3; i <= n; ++i) { f *= i; } return f; } public static void main(String[] args) { System.out.println(fact(1 << 15)); } } 

FYI, como lo muestra la solución iterativa anterior, la función de fact no puede calcular el factorial exacto de números superiores a 65 (en realidad, incluso por encima de 20), porque el tipo incorporado de Java se desbordará long . Refactorizar el fact para que devuelva un BigInteger vez de long daría resultados exactos para grandes entradas.

Hmm … funciona para mí y con mucho menos de 999MB de stack:

 > java -Xss4m Test 0 

(Windows JDK 7, comstackción 17.0-b05 cliente VM, y Linux JDK 6 – la misma información de versión que ha publicado)

Supongo que calculó la “profundidad de 1024” por las líneas recurrentes en el rastro de la stack.

Obviamente, la longitud del conjunto de trazas de stack en Throwable parece estar limitada a 1024. Pruebe el siguiente progtwig:

 public class Test { public static void main(String[] args) { try { System.out.println(fact(1 < < 15)); } catch (StackOverflowError e) { System.err.println("true recursion level was " + level); System.err.println("reported recursion level was " + e.getStackTrace().length); } } private static int level = 0; public static long fact(int n) { level++; return n < 2 ? n : n * fact(n - 1); } } 

Si desea jugar con el tamaño de la stack de subprocesos, querrá ver la opción -Xss en la JVM de zona activa. Puede ser algo diferente en máquinas virtuales no Hotspot ya que los parámetros -X para la JVM son específicos de la distribución, IIRC.

En Hotspot, esto se ve como java -Xss16M si quieres hacer el tamaño de 16 megas.

Escriba java -X -help si desea ver todos los parámetros de JVM específicos de distribución que puede pasar. No estoy seguro de si esto funciona igual en otras JVM, pero imprime todos los parámetros específicos de Hotspot.

Por lo que vale, recomendaría limitar el uso de métodos recursivos en Java. No es demasiado bueno para optimizarlos; por un lado, la JVM no es compatible con la recursión de cola (consulte ¿Evita la JVM las optimizaciones de cola? ). Intente refactorizar su código factorial anterior para usar un ciclo while en lugar de llamadas a métodos recursivos.

La única forma de controlar el tamaño de la stack dentro del proceso es iniciar un nuevo Thread . Pero también puede controlar creando un proceso de sub-llamada auto-llamada con el parámetro -Xss .

 public class TT { private static int level = 0; public static long fact(int n) { level++; return n < 2 ? n : n * fact(n - 1); } public static void main(String[] args) throws InterruptedException { Thread t = new Thread(null, null, "TT", 1000000) { @Override public void run() { try { level = 0; System.out.println(fact(1 << 15)); } catch (StackOverflowError e) { System.err.println("true recursion level was " + level); System.err.println("reported recursion level was " + e.getStackTrace().length); } } }; t.start(); t.join(); try { level = 0; System.out.println(fact(1 << 15)); } catch (StackOverflowError e) { System.err.println("true recursion level was " + level); System.err.println("reported recursion level was " + e.getStackTrace().length); } } } 

Agrega esta opción

 --driver-java-options -Xss512m 

a su comando spark-submit solucionará este problema.

Es difícil dar una solución sensata ya que desea evitar todos los enfoques sanos. Refactorizar una línea de código es la solución sensible.

Nota: Usar -Xss establece el tamaño de la stack de cada hilo y es una muy mala idea.

Otro enfoque es la manipulación del código de bytes para cambiar el código de la siguiente manera;

 public static long fact(int n) { return n < 2 ? n : n > 127 ? 0 : n * fact(n - 1); } 

dado que cada respuesta para n> 127 es 0. Esto evita cambiar el código fuente.

¡Extraño! ¿Estás diciendo que quieres generar una recursión de 1 < < 15 de profundidad ??? !!!!

Sugeriría que NO lo intentes. El tamaño de la stack será de 2^15 * sizeof(stack-frame) . No sé qué tamaño de marco de stack es, pero 2 ^ 15 es 32.768. Más o menos … Bueno, si se detiene en 1024 (2 ^ 10), tendrás que hacerlo 2 ^ 5 veces más grande, es decir, 32 veces más grande que con tu ajuste real.

Otros carteles han señalado cómo boost la memoria y que usted puede memorizar llamadas. Sugeriría que para muchas aplicaciones, puedes usar la fórmula de Stirling para aproximar n grande. muy rápido y casi sin huella de memoria.

Eche un vistazo a esta publicación, que tiene algunos análisis de la función y el código:

http://threebrothers.org/brendan/blog/stirlings-approximation-formula-clojure/

Hice Anagram excersize , que es como el problema Count Change pero con 50 000 denominaciones (monedas). No estoy seguro de que se pueda hacer de forma iterativa , no me importa. Solo sé que la opción -xss no tuvo ningún efecto. Siempre fallaba después de 1024 fotogtwigs de stack (podría ser que Scala haga un mal trabajo en Java o en la limitación de printStackTrace. No lo sé). Esta es una mala opción, como se explica de todos modos. No quieres que todos los hilos en la aplicación sean monstruosos. Sin embargo, hice algunos experimentos con Thread nuevo (tamaño de la stack). Esto funciona de hecho,

  def measureStackDepth(ss: Long): Long = { var depth: Long = 0 val thread: Thread = new Thread(null, new Runnable() { override def run() { try { def sum(n: Long): Long = {depth += 1; if (n== 0) 0 else sum(n-1) + 1} println("fact = " + sum(ss * 10)) } catch { case e: StackOverflowError => // eat the exception, that is expected } } }, "deep stack for money exchange", ss) thread.start() thread.join() depth } //> measureStackDepth: (ss: Long)Long for (ss < - (0 to 10)) println("ss = 10^" + ss + " allows stack of size " -> measureStackDepth((scala.math.pow (10, ss)).toLong) ) //> fact = 10 //| (ss = 10^0 allows stack of size ,11) //| fact = 100 //| (ss = 10^1 allows stack of size ,101) //| fact = 1000 //| (ss = 10^2 allows stack of size ,1001) //| fact = 10000 //| (ss = 10^3 allows stack of size ,10001) //| (ss = 10^4 allows stack of size ,1336) //| (ss = 10^5 allows stack of size ,5456) //| (ss = 10^6 allows stack of size ,62736) //| (ss = 10^7 allows stack of size ,623876) //| (ss = 10^8 allows stack of size ,6247732) //| (ss = 10^9 allows stack of size ,62498160) 

Ves que la stack puede crecer exponencialmente más profundo con una stack exponencialmente más asignada al hilo.