Comment augmenter la taille de la pile Java ?

Question

J'ai posé cette question pour savoir comment augmenter la taille de la pile d'appels en cours d'exécution dans la JVM. J'ai obtenu une réponse à cette question, ainsi que de nombreuses réponses et commentaires utiles sur la manière dont Java gère la situation où une grande pile d'exécution est nécessaire. J'ai complété ma question avec le résumé des réponses.

À l'origine, je voulais augmenter la taille de la pile de la JVM pour que des programmes tels que les exécutions sans 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));
  }
}

Le paramètre de configuration correspondant est le java -Xss... avec une valeur suffisamment grande. Pour le programme TT ci-dessus, cela fonctionne comme suit avec la JVM d'OpenJDK :

$ javac TT.java
$ java -Xss4m TT

L'une des réponses a également souligné que la -X... dépendent de la mise en œuvre. J'utilisais

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)

Il est également possible de spécifier une grande pile pour un seul thread (voir dans l'une des réponses comment). Il est recommandé d'utiliser cette méthode plutôt que java -Xss... pour éviter de gaspiller de la mémoire pour des threads qui n'en ont pas besoin.

J'étais curieux de connaître la taille de la pile dont le programme ci-dessus a besoin, et je l'ai donc exécuté. n augmentée :

• -Xss4m peut suffire pour fact(1 << 15)
• -Xss5m peut suffire pour fact(1 << 17)
• -Xss7m peut suffire pour fact(1 << 18)
• -Xss9m peut suffire pour fact(1 << 19)
• -Xss18m peut suffire pour fact(1 << 20)
• -Xss35m peut suffire pour fact(1 << 21)
• -Xss68m peut suffire pour fact(1 << 22)
• -Xss129m peut suffire pour fact(1 << 23)
• -Xss258m peut être suffisant pour fact(1 << 24)
• -Xss515m peut suffire pour fact(1 << 25)

D'après les chiffres ci-dessus, il semble que Java utilise environ 16 octets par trame de pile pour la fonction ci-dessus, ce qui est raisonnable.

L'énumération ci-dessus contient peut suffire au lieu de est suffisant L'exigence de la pile n'est pas déterministe : l'exécuter plusieurs fois avec le même fichier source et les mêmes -Xss... réussit parfois et produit parfois un StackOverflowError . Par exemple, pour 1 << 20, -Xss18m a suffi dans 7 séries sur 10, et -Xss19m n'a pas toujours suffi non plus, mais -Xss20m a suffi (pour 100 passages sur 100). Est-ce que le garbage collection, le JIT qui intervient, ou quelque chose d'autre provoque ce comportement non déterministe ?

La trace de la pile imprimée à un StackOverflowError (et éventuellement à d'autres exceptions) n'affiche que les 1024 éléments les plus récents de la pile d'exécution. Une réponse ci-dessous montre comment compter la profondeur exacte atteinte (qui peut être beaucoup plus grande que 1024).

De nombreuses personnes qui ont répondu ont souligné que c'est une bonne pratique de codage que d'envisager d'autres implémentations du même algorithme, moins gourmandes en ressources. En général, il est possible de convertir un ensemble de fonctions récursives en fonctions itératives (à l'aide d'une fonction de type Stack qui est alimenté sur le tas et non sur la pile d'exécution). Pour cet objet fact il est assez facile de la convertir. Ma version itérative ressemblerait à ceci

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

Pour information, comme le montre la solution itérative ci-dessus, l'élément fact ne peut pas calculer la factorielle exacte des nombres supérieurs à 65 (en fait, même supérieurs à 20), car le type intégré Java long déborderait. Refonte fact de sorte qu'il renvoie un BigInteger au lieu de long donnerait également des résultats exacts pour des entrées importantes.

Answer 1

Hmm... cela fonctionne pour moi et avec bien moins de 999MB de pile :

> java -Xss4m Test
0

(Windows JDK 7, build 17.0-b05 client VM, et Linux JDK 6 - mêmes informations de version que celles que vous avez postées)

Answer 2

Je suppose que vous avez calculé la "profondeur de 1024" à partir des lignes récurrentes de la trace de pile ?

Manifestement, la longueur du tableau de la trace de pile dans Throwable semble être limitée à 1024. Essayez le programme suivant :

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 3

Si vous voulez jouer avec la taille de la pile de threads, vous pouvez utiliser l'option -Xss de la JVM Hotspot. Il se peut que ce soit différent sur les VM non Hotspot puisque les paramètres -X de la JVM sont spécifiques à la distribution, IIRC.

Sur Hotspot, cela ressemble à java -Xss16M si vous voulez que la taille soit de 16 mégaoctets.

Type java -X -help si vous voulez voir tous les paramètres JVM spécifiques à la distribution que vous pouvez passer. Je ne suis pas sûr que cela fonctionne de la même manière avec d'autres JVM, mais cela affiche tous les paramètres spécifiques à Hotspot.

Pour ce que cela vaut, je recommanderais de limiter l'utilisation des méthodes récursives en Java. L'optimisation de ces méthodes n'est pas très bonne - d'une part, la JVM ne prend pas en charge la récursion de queue (voir La JVM empêche-t-elle l'optimisation des appels de queue ? ). Essayez de remanier votre code factoriel ci-dessus pour utiliser une boucle while au lieu d'appels de méthode récursifs.

Answer 4

Le seul moyen de contrôler la taille de la pile au sein d'un processus est de lancer un nouveau Thread . Mais vous pouvez également contrôler en créant un sous-processus Java qui s'appelle lui-même avec la commande -Xss paramètre.

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 5

Votre exemple utilise la récursivité des arbres et est extrêmement à forte intensité de mémoire. Vous pourriez utiliser la mémorisation (stocker les résultats précédemment calculés plutôt que de les recalculer) et vous en sortir sans abandonner complètement votre solution récursive.