Qu'est-ce qu'une StackOverflowError?

Qu'est-ce qu'un StackOverflowError, qu'est-ce qui le cause et comment dois-je le traiter?

Les paramètres et les variables locales sont alloués sur la pile (avec les types de référence, l'objet vit sur le tas et une variable dans la pile fait référence à cet objet sur le tas). La pile vit généralement à l' extrémité supérieure de votre espace d'adressage et lorsqu'elle est utilisée, elle se dirige vers le bas de l'espace d'adressage (c'est-à-dire vers zéro).

Votre processus a également un tas , qui vit à l' extrémité inférieure de votre processus. Lorsque vous allouez de la mémoire, ce segment peut augmenter vers l'extrémité supérieure de votre espace d'adressage. Comme vous pouvez le voir, il y a un potentiel pour que le tas "entre en collision" avec la pile (un peu comme les plaques tectoniques !!!).

La cause courante d'un débordement de pile est un mauvais appel récursif . En règle générale, cela se produit lorsque vos fonctions récursives n'ont pas la condition de terminaison correcte, donc elles finissent par s'appeler pour toujours. Ou lorsque la condition de terminaison est correcte, elle peut être provoquée en exigeant trop d'appels récursifs avant de la remplir.

Cependant, avec la programmation GUI, il est possible de générer une récursivité indirecte . Par exemple, votre application peut gérer des messages de peinture et, lors de leur traitement, elle peut appeler une fonction qui amène le système à envoyer un autre message de peinture. Ici, vous ne vous êtes pas explicitement appelé, mais l'OS / VM l'a fait pour vous.

Pour y faire face, vous devrez examiner votre code. Si vous avez des fonctions qui s'appellent elles-mêmes, vérifiez que vous avez une condition de terminaison. Si c'est le cas, vérifiez que lors de l'appel de la fonction, vous avez au moins modifié l'un des arguments, sinon il n'y aura pas de changement visible pour la fonction appelée récursivement et la condition de fin est inutile. Gardez également à l'esprit que votre espace de pile peut manquer de mémoire avant d'atteindre une condition de fin valide, assurez-vous donc que votre méthode peut gérer les valeurs d'entrée nécessitant des appels plus récursifs.

Si vous n'avez pas de fonctions récursives évidentes, vérifiez si vous appelez des fonctions de bibliothèque qui provoqueront indirectement l' appel de votre fonction (comme le cas implicite ci-dessus).

Pour décrire cela, commençons par comprendre comment les variables et objets locaux sont stockés.

Les variables locales sont stockées dans la pile :

Si vous avez regardé l'image, vous devriez pouvoir comprendre comment les choses fonctionnent.

Lorsqu'un appel de fonction est appelé par une application Java, une trame de pile est allouée sur la pile d'appels. Le cadre de pile contient les paramètres de la méthode invoquée, ses paramètres locaux et l'adresse de retour de la méthode. L'adresse de retour indique le point d'exécution à partir duquel l'exécution du programme doit se poursuivre après le retour de la méthode invoquée. S'il n'y a pas d'espace pour un nouveau cadre de pile, alors, il StackOverflowErrorest lancé par la machine virtuelle Java (JVM).

Le cas le plus courant qui peut éventuellement épuiser la pile d'une application Java est la récursivité. En récursivité, une méthode s'invoque lors de son exécution. La récursivité est considérée comme une technique de programmation polyvalente puissante mais doit être utilisée avec prudence pour éviter StackOverflowError.

Un exemple de lancement d'un StackOverflowErrorest illustré ci-dessous:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

  public static void recursivePrint(int num) {
    System.out.println("Number: " + num);

    if (num == 0)
      return;
    else
      recursivePrint(++num);
  }

  public static void main(String[] args) {
    StackOverflowErrorExample.recursivePrint(1);
  }
}

Dans cet exemple, nous définissons une méthode récursive, appelée recursivePrintqui imprime un entier puis, s'appelle elle-même, avec le prochain entier successif comme argument. La récursivité se termine jusqu'à ce que nous passions en 0paramètre. Cependant, dans notre exemple, nous avons passé le paramètre de 1 et ses suiveurs croissants, par conséquent, la récursivité ne se terminera jamais.

Un exemple d'exécution, utilisant l' -Xss1Mindicateur qui spécifie la taille de la pile de threads à 1 Mo, est illustré ci-dessous:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

En fonction de la configuration initiale de la JVM, les résultats peuvent différer, mais finalement ils StackOverflowErrordoivent être levés. Cet exemple est un très bon exemple de la façon dont la récursivité peut causer des problèmes, si elle n'est pas implémentée avec prudence.

Comment gérer la StackOverflowError

1. La solution la plus simple consiste à inspecter soigneusement la trace de la pile et à détecter le motif répétitif des numéros de ligne. Ces numéros de ligne indiquent que le code est appelé de manière récursive. Une fois que vous avez détecté ces lignes, vous devez inspecter soigneusement votre code et comprendre pourquoi la récursivité ne se termine jamais.

2. Si vous avez vérifié que la récursivité est correctement implémentée, vous pouvez augmenter la taille de la pile, afin d'autoriser un plus grand nombre d'appels. En fonction de la machine virtuelle (JVM) Java installée, la taille de la pile de threads par défaut peut être égal soit 512Ko ou 1Mo . Vous pouvez augmenter la taille de la pile de threads à l'aide de l' -Xssindicateur. Cet indicateur peut être spécifié soit via la configuration du projet, soit via la ligne de commande. Le format de l' -Xssargument est: -Xss<size>[g|G|m|M|k|K]

Si vous avez une fonction comme:

int foo()
{
    // more stuff
    foo();
}

Ensuite, foo () continuera de s'appeler, de plus en plus profond, et lorsque l'espace utilisé pour garder une trace des fonctions dans lesquelles vous vous trouvez est rempli, vous obtenez l'erreur de débordement de pile.

Le débordement de pile signifie exactement cela: une pile déborde. Habituellement, il y a une seule pile dans le programme qui contient des variables de portée locale et indique où retourner à la fin de l'exécution d'une routine. Cette pile a tendance à être une plage de mémoire fixe quelque part dans la mémoire, par conséquent, la quantité de valeurs qu'elle peut contenir est limitée.

Si la pile est vide, vous ne pouvez pas sauter, si vous le faites, vous obtiendrez une erreur de dépassement de pile.

Si la pile est pleine, vous ne pouvez pas pousser, sinon vous obtiendrez une erreur de débordement de pile.

Un débordement de pile apparaît donc là où vous allouez trop dans la pile. Par exemple, dans la récursion mentionnée.

Certaines implémentations optimisent certaines formes de récursions. Récursion de la queue en particulier. Les routines récursives de queue sont une forme de routines où l'appel récursif apparaît comme une chose finale que fait la routine. Un tel appel de routine est simplement réduit en saut.

Certaines implémentations vont jusqu'à implémenter leurs propres piles pour la récursivité, donc elles permettent à la récursivité de continuer jusqu'à ce que le système manque de mémoire.

La chose la plus simple que vous pourriez essayer serait d'augmenter la taille de votre pile si vous le pouvez. Si vous ne pouvez pas faire cela, la deuxième meilleure chose serait de vérifier s'il y a quelque chose qui provoque clairement le débordement de la pile. Essayez-le en imprimant quelque chose avant et après l'appel dans la routine. Cela vous aide à découvrir la routine qui échoue.

Un débordement de pile est généralement appelé en imbriquant trop profondément les appels de fonction (particulièrement facile lorsque vous utilisez la récursivité, c'est-à-dire une fonction qui s'appelle elle-même) ou en allouant une grande quantité de mémoire sur la pile où l'utilisation du tas serait plus appropriée.

Comme vous le dites, vous devez montrer du code. :-)

Une erreur de débordement de pile se produit généralement lorsque vos appels de fonction s'imbriquent trop profondément. Voir le fil de discussion Stack Overflow Code Golf pour quelques exemples de la façon dont cela se produit (bien que dans le cas de cette question, les réponses provoquent intentionnellement un dépassement de pile).

La cause la plus courante de débordements de pile est une récursivité excessivement profonde ou infinie . Si tel est votre problème, ce didacticiel sur la récursivité Java pourrait aider à comprendre le problème.

StackOverflowErrorest à la pile comme OutOfMemoryErrorau tas.

Les appels récursifs non limités entraînent une utilisation de l'espace de pile.

L'exemple suivant produit StackOverflowError:

class  StackOverflowDemo
{
    public static void unboundedRecursiveCall() {
     unboundedRecursiveCall();
    }

    public static void main(String[] args) 
    {
        unboundedRecursiveCall();
    }
}

StackOverflowError est évitable si les appels récursifs sont limités pour empêcher le total cumulé des appels en mémoire incomplets (en octets) de dépasser la taille de la pile (en octets).

Voici un exemple d'algorithme récursif pour inverser une liste liée individuellement. Sur un ordinateur portable avec les spécifications suivantes (mémoire 4G, processeur Intel Core i5 2,3 GHz, 64 bits Windows 7), cette fonction se heurtera à une erreur StackOverflow pour une liste liée de taille proche de 10000.

Mon point est que nous devons utiliser la récursion judicieusement, en tenant toujours compte de l'échelle du système. Souvent, la récursivité peut être convertie en programme itératif, qui évolue mieux. (Une version itérative du même algorithme est donnée au bas de la page, elle inverse une liste liée de taille 1 million en 9 millisecondes.)

    private static LinkedListNode doReverseRecursively(LinkedListNode x, LinkedListNode first){

    LinkedListNode second = first.next;

    first.next = x;

    if(second != null){
        return doReverseRecursively(first, second);
    }else{
        return first;
    }
}

public static LinkedListNode reverseRecursively(LinkedListNode head){
    return doReverseRecursively(null, head);
}

Version itérative du même algorithme:

    public static LinkedListNode reverseIteratively(LinkedListNode head){
    return doReverseIteratively(null, head);
}   

private static LinkedListNode doReverseIteratively(LinkedListNode x, LinkedListNode first) {

    while (first != null) {
        LinkedListNode second = first.next;
        first.next = x;
        x = first;

        if (second == null) {
            break;
        } else {
            first = second;
        }
    }
    return first;
}


public static LinkedListNode reverseIteratively(LinkedListNode head){
    return doReverseIteratively(null, head);
}

A StackOverflowErrorest une erreur d'exécution en java.

Elle est levée lorsque la quantité de mémoire de pile d'appels allouée par JVM est dépassée.

Un cas courant de StackOverflowErrorrejet est lorsque la pile d'appels dépasse en raison d'une récursion profonde ou infinie excessive.

Exemple:

public class Factorial {
    public static int factorial(int n){
        if(n == 1){
            return 1;
        }
        else{
            return n * factorial(n-1);
        }
    }

    public static void main(String[] args){
        System.out.println("Main method started");
        int result = Factorial.factorial(-1);
        System.out.println("Factorial ==>"+result);
        System.out.println("Main method ended");
    }
}

Trace de la pile:

Main method started
Exception in thread "main" java.lang.StackOverflowError
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)

Dans le cas ci-dessus, cela peut être évité en effectuant des changements de programmation. Mais si la logique du programme est correcte et qu'elle se produit toujours, la taille de la pile doit être augmentée.

Ceci est un cas typique de java.lang.StackOverflowError... La méthode s'appelle récursivement sans sortie dans doubleValue(),floatValue() etc.

Rational.java

    public class Rational extends Number implements Comparable<Rational> {
        private int num;
        private int denom;

        public Rational(int num, int denom) {
            this.num = num;
            this.denom = denom;
        }

        public int compareTo(Rational r) {
            if ((num / denom) - (r.num / r.denom) > 0) {
                return +1;
            } else if ((num / denom) - (r.num / r.denom) < 0) {
                return -1;
            }
            return 0;
        }

        public Rational add(Rational r) {
            return new Rational(num + r.num, denom + r.denom);
        }

        public Rational sub(Rational r) {
            return new Rational(num - r.num, denom - r.denom);
        }

        public Rational mul(Rational r) {
            return new Rational(num * r.num, denom * r.denom);
        }

        public Rational div(Rational r) {
            return new Rational(num * r.denom, denom * r.num);
        }

        public int gcd(Rational r) {
            int i = 1;
            while (i != 0) {
                i = denom % r.denom;
                denom = r.denom;
                r.denom = i;
            }
            return denom;
        }

        public String toString() {
            String a = num + "/" + denom;
            return a;
        }

        public double doubleValue() {
            return (double) doubleValue();
        }

        public float floatValue() {
            return (float) floatValue();
        }

        public int intValue() {
            return (int) intValue();
        }

        public long longValue() {
            return (long) longValue();
        }
    }

Main.java

    public class Main {

        public static void main(String[] args) {

            Rational a = new Rational(2, 4);
            Rational b = new Rational(2, 6);

            System.out.println(a + " + " + b + " = " + a.add(b));
            System.out.println(a + " - " + b + " = " + a.sub(b));
            System.out.println(a + " * " + b + " = " + a.mul(b));
            System.out.println(a + " / " + b + " = " + a.div(b));

            Rational[] arr = {new Rational(7, 1), new Rational(6, 1),
                    new Rational(5, 1), new Rational(4, 1),
                    new Rational(3, 1), new Rational(2, 1),
                    new Rational(1, 1), new Rational(1, 2),
                    new Rational(1, 3), new Rational(1, 4),
                    new Rational(1, 5), new Rational(1, 6),
                    new Rational(1, 7), new Rational(1, 8),
                    new Rational(1, 9), new Rational(0, 1)};

            selectSort(arr);

            for (int i = 0; i < arr.length - 1; ++i) {
                if (arr[i].compareTo(arr[i + 1]) > 0) {
                    System.exit(1);
                }
            }


            Number n = new Rational(3, 2);

            System.out.println(n.doubleValue());
            System.out.println(n.floatValue());
            System.out.println(n.intValue());
            System.out.println(n.longValue());
        }

        public static <T extends Comparable<? super T>> void selectSort(T[] array) {

            T temp;
            int mini;

            for (int i = 0; i < array.length - 1; ++i) {

                mini = i;

                for (int j = i + 1; j < array.length; ++j) {
                    if (array[j].compareTo(array[mini]) < 0) {
                        mini = j;
                    }
                }

                if (i != mini) {
                    temp = array[i];
                    array[i] = array[mini];
                    array[mini] = temp;
                }
            }
        }
    }

Résultat

    2/4 + 2/6 = 4/10
    Exception in thread "main" java.lang.StackOverflowError
    2/4 - 2/6 = 0/-2
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
    2/4 * 2/6 = 4/24
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
    2/4 / 2/6 = 12/8
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)

Voici le code source d' StackOverflowErrorOpenJDK 7

Dans une situation critique, la situation ci-dessous entraînera une erreur de débordement de la pile.

public class Example3 {

public static void main(String[] args) {

    main(new String[1]);

}

}

Voici un exemple

public static void main(String[] args) {
    System.out.println(add5(1));
}

public static int add5(int a) {
    return add5(a) + 5;
}

Une StackOverflowError est essentiellement lorsque vous essayez de faire quelque chose, qui s'appelle très probablement, et continue à l'infini (ou jusqu'à ce qu'il donne une StackOverflowError).

add5(a) s'appellera, puis s'appellera à nouveau, et ainsi de suite.

Le terme «dépassement de pile (débordement)» est souvent utilisé mais est un terme impropre; les attaques ne débordent pas la pile mais les tampons sur la pile.

- à partir de diapositives de cours du Prof. Dr. Dieter Gollmann