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

error stack overflow 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 para que los programas 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 programa 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 pila 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 pila que el programa 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 pila 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 pila 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 pila impreso en StackOverflowError (y posiblemente en otras excepciones también) 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 a funciones iterativas (usando un objeto Stack , por ejemplo, que se rellena en el montón en lugar de en la pila 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 < 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));
  }
}

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.

Answer 1

¡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 pila será de 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 2

Agrega esta opción

--driver-java-options -Xss512m

a su comando spark-submit solucionará este problema.

Answer 3

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 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.

Answer 4

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 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: Error => // 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 pila puede crecer exponencialmente más profundo con una pila exponencialmente más asignada al hilo.

Answer 5

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

> 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 ha publicado)

Answer 6

La única forma de controlar el tamaño de la pila 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 (Error 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 (Error e) {
            System.err.println("true recursion level was " + level);
            System.err.println("reported recursion level was "
                    + e.getStackTrace().length);
        }
    }

}

Answer 7

Otros carteles han señalado cómo aumentar 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/

Answer 8

Si desea jugar con el tamaño de la pila 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.

Answer 9

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

Obviamente, la longitud del conjunto de trazas 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 (Error 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);
    }
}