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

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 Java maneja la situación en la que se necesita una gran pila de tiempo de ejecución. He ampliado mi pregunta con el resumen de las respuestas.

Originalmente quería aumentar el tamaño de la pila de JVM para que los programas se ejecuten sin un 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 valor de configuración correspondiente es el java -Xss...indicador de la línea de comandos con un valor suficientemente grande. Para el programa TTanterior, funciona así con la JVM de OpenJDK:

$ javac TT.java
$ java -Xss4m TT

Una de las respuestas también ha señalado que las -X...banderas 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 pila grande solo para un hilo (vea en una de las respuestas cómo). Esto se recomienda java -Xss...para evitar desperdiciar memoria en subprocesos que no la necesitan.

Tenía curiosidad por saber qué tamaño de pila necesita exactamente el programa anterior, así que lo he ejecutado naumentado:

• -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 suficiente 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á usando aproximadamente 16 bytes por marco de pila para la función anterior, lo cual es razonable.

La enumeración anterior contiene puede ser suficiente en lugar de es suficiente , porque el requisito de la pila no es determinista: ejecutarlo varias veces con el mismo archivo fuente y el mismo a -Xss...veces tiene éxito y a veces produce un archivo StackOverflowError. Por ejemplo, para 1 << 20, -Xss18mfue suficiente en 7 carreras de 10, y -Xss19mtampoco siempre fue suficiente, pero -Xss20mfue suficiente (en todas las 100 carreras de 100). ¿La recolección de basura, la activación del JIT o algo más causan este comportamiento no determinista?

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

Muchas personas que respondieron han señalado que es una práctica de codificación buena y segura considerar implementaciones alternativas del mismo algoritmo que requieren menos pilas. En general, es posible convertir a un conjunto de funciones recursivas en funciones iterativas (usando un Stackobjeto, por ejemplo , que se llena en el montón en lugar de en la pila en tiempo de ejecución). Para esta factfunción en particular , es bastante fácil convertirlo. 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));
  }
}

Para su información, como lo muestra la solución iterativa anterior, la factfunción no puede calcular el factorial exacto de números por encima de 65 (en realidad, incluso por encima de 20), porque el tipo integrado de Java longse desbordaría. La refactorización factpara que devuelva un en BigIntegerlugar de longtambién produciría resultados exactos para entradas grandes.

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

> java -Xss4m Test
0

(Windows JDK 7, compilación 17.0-b05 cliente VM y Linux JDK 6: la misma información de versión que publicó)

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

Obviamente, la longitud de la matriz de seguimiento de pila 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);
    }
}

Si desea jugar con el tamaño de la pila de subprocesos, querrá mirar la opción -Xss en Hotspot JVM. Puede ser algo diferente en las VM que no sean Hotspot, ya que los parámetros -X de la JVM son específicos de la distribución, IIRC.

En Hotspot, esto parece java -Xss16Msi quieres que el tamaño sea de 16 megas.

Tipo java -X -help si desea ver todos los parámetros de JVM específicos de la 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 admite la recursividad de cola (consulte ¿La JVM evita las optimizaciones de llamadas de cola? ). Intente refactorizar su código factorial anterior para usar un ciclo while en lugar de llamadas de método recursivas.

La única forma de controlar el tamaño de la pila dentro del proceso es comenzar de nuevo Thread. Pero también puede controlar mediante la creación de un subproceso Java de auto-llamada con el -Xssparámetro.

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

}

Agregar 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 cuerdos. Refactorizar una línea de código es la solución más sencilla.

Nota: El uso de -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); 
}

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 recursividad de 1 << 15 de profundidad ??? !!!!

Sugiero que NO lo intentes. 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. Básicamente ... Bueno, si se detiene en 1024 (2 ^ 10), tendrá que hacerlo 2 ^ 5 veces más grande, es decir, 32 veces más grande que con su configuración real.

Otros carteles han señalado cómo aumentar la memoria y que se pueden memorizar las llamadas. ¡Sugeriría que para muchas aplicaciones, puede usar la fórmula de Stirling para aproximar n grande! muy rápidamente sin apenas huella de memoria.

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

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

Hice un ejercicio de Anagrama , que es como un problema de Cambio de Cuenta 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 marcos de pila (podría ser que scala hace un mal trabajo entregando a java o limitación de printStackTrace. No lo sé). Esta es una mala opción, como se explicó de todos modos. No desea que todos los hilos de la aplicación sean monstruosos. Sin embargo, hice algunos experimentos con el nuevo Thread (tamaño de 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)

Verá que la pila puede crecer exponencialmente más profunda con exponencialmente más pila asignada al hilo.