¿Cómo aumentar el tamaño de la pila de Java?

Question

Hice esta pregunta para saber cómo aumentar el tamaño de la pila 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 pila de tiempo de ejecución. He extendido mi pregunta con el resumen de las respuestas.

Originalmente quería aumentar el tamaño de la pila JVM, por lo que los programas funcionan 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)); 
    } 
} 

el ajuste de configuración correspondiente es la bandera java -Xss... de línea de comandos con un valor suficientemente grande. Para el programa TT anteriormente, funciona así con JVM de OpenJDK:

$ javac TT.java 
$ java -Xss4m TT 

Una de las respuestas también ha señalado que las banderas son -X... depende de la implementación. Yo 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 pila solo para una cadena (ver en una de las respuestas cómo). Se recomienda esto sobre java -Xss... para evitar desperdiciar memoria para hilos que no lo necesitan.

Tenía curiosidad por lo grande que una pila del programa anterior exactamente necesita, por lo que me he encontrado que el aumento n:

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

De los números anteriores parece que Java está utilizando alrededor de 16 bytes por marco de pila para la función anterior, que es razonable.

La enumeración anterior contiene puede ser suficiente en lugar de es suficiente, ya que el requisito de pila no es determinista: se ejecutan varias veces con el mismo archivo de origen y el mismo -Xss... veces tiene éxito y, a veces se obtiene un StackOverflowError. P.ej. 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 pila impreso en StackOverflowError (y posiblemente también en otras excepciones) muestra solo los 1024 elementos más recientes de la pila 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 codificación considerar implementaciones alternativas, menos aptas para la pila, del mismo algoritmo. En general, es posible convertir un conjunto de funciones recursivas en funciones iterativas (utilizando un objeto por ejemplo Stack, que se rellena en el montón en lugar de en la pila de tiempo de ejecución). Para esta función particular fact, 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 < 2) return 1; 
    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)); 
    } 
} 

su información, como la solución iterativa anterior muestra que, la función fact no puede calcular el factorial exacta de los números por encima de 65 (en realidad, incluso por encima de 20), debido a que el Java incorporado tipo long se desbordará. Refactorizar fact para que devuelva BigInteger en lugar de long también daría resultados exactos para grandes entradas.

Answer 1

Hmm ... que funciona para mí y con mucho menos de 999 MB de pila: el cliente

> java -Xss4m Test 
0 

(JDK de Windows 7, la construcción 17,0 b05-VM y Linux JDK 6 - misma información de la versión a medida que publicado)

Answer 2

Si quieres jugar con el tamaño de la pila de subprocesos, deberás consultar la opción -Xss en la zona de acceso compartido JVM. 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 el punto de acceso, esto se ve como java -Xss16M si quiere 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 la pena, 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 recursividad final (consulte Does the JVM prevent tail call optimizations?). Intente refactorizar su código factorial anterior para usar un ciclo while en lugar de llamadas a métodos recursivos.

Answer 3

Supongo que calculó la "profundidad de 1024" por las líneas recurrentes en el seguimiento de la pila?

Obviamente, la pila de traza longitud de la matriz en Throwable parece estar limitada a 1024. Pruebe el siguiente programa:

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); 
    } 
} 

Answer 4

extraño! Usted está diciendo que desea generar una recursión de 1 < < 15 profundidad ??? !!!!

Sugeriría NO lo intente. El tamaño de la pila será 2^15 * sizeof(stack-frame). No sé qué tamaño de marco de pila 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.

Answer 5

La única manera de controlar el tamaño de la pila dentro del proceso es iniciar una nueva Thread. Pero también puede controlar creando un proceso de autovocación sub Java 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); 
     } 
    } 

} 

Answer 6

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 pila 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); 
} 

cada respuesta para n> 127 es 0. Esto evitará cambiar el código fuente.

Answer 7

Otros carteles han señalado cómo aumentar la memoria y que 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.

echar un vistazo a este post, que tiene un cierto análisis de la función y el código:

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

Answer 8

lo hice Anagram excersize, que es como Count Change problema, pero con 50 000 denominaciones (monedas). Soy not sure that it can be done iteratively, no me importa. Solo sé que la opción -xss no tuvo ningún efecto. Siempre fallaba después de 1024 fotogramas de pila (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 pila). 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) 

se ve que la pila puede crecer exponencialmente más profunda con exponencialmente más pila asignado a la rosca.

Answer 9

Añadir esta opción

--driver-java-opciones -Xss512m

a su chispa presentar comando solucionar este problema.