Что такое StackOverflowError?

Что это такое StackOverflowError, что его вызывает и как с ними бороться?

Параметры и локальные переменные размещаются в стеке (со ссылочными типами объект живет в куче, а переменная в стеке ссылается на этот объект в куче). Стек обычно находится в верхнем конце вашего адресного пространства и по мере его использования направляется вниз части адресного пространства (то есть к нулю).

У вашего процесса также есть куча , которая живет в нижней части вашего процесса. По мере выделения памяти эта куча может увеличиваться в направлении верхнего края вашего адресного пространства. Как вы можете видеть, существует вероятность того, что куча "столкнется" со стеком (немного похоже на тектонические плиты !!!).

Распространенной причиной переполнения стека является плохой рекурсивный вызов . Как правило, это происходит, когда ваши рекурсивные функции не имеют правильного условия завершения, поэтому они в конечном итоге вызывают себя навсегда. Или когда условие завершения в порядке, оно может быть вызвано тем, что требуется слишком много рекурсивных вызовов перед его выполнением.

Тем не менее, с программированием GUI, возможно генерировать косвенную рекурсию . Например, ваше приложение может обрабатывать сообщения рисования и во время их обработки может вызывать функцию, которая заставляет систему отправлять другое сообщение рисования. Здесь вы явно не называли себя, но OS / VM сделала это за вас.

Чтобы разобраться с ними, вам нужно изучить свой код. Если у вас есть функции, которые вызывают сами себя, проверьте, что у вас есть условие завершения. Если да, то убедитесь, что при вызове функции вы как минимум изменили один из аргументов, иначе не будет видимых изменений для рекурсивно вызываемой функции и условие завершения бесполезно. Также помните, что вашему стековому пространству может не хватить памяти до достижения допустимого условия завершения, поэтому убедитесь, что ваш метод может обрабатывать входные значения, требующие более рекурсивных вызовов.

Если у вас нет очевидных рекурсивных функций, проверьте, вызываете ли вы какие-либо библиотечные функции, которые косвенно вызовут вашу функцию (как неявный случай выше).

Чтобы описать это, сначала давайте разберемся, как хранятся локальные переменные и объекты.

Локальные переменные хранятся в стеке :

Если вы посмотрели на изображение, вы должны понимать, как все работает.

Когда вызов функции вызывается приложением Java, в стеке вызовов выделяется кадр стека. Кадр стека содержит параметры вызванного метода, его локальные параметры и адрес возврата метода. Адрес возврата обозначает точку выполнения, с которой выполнение программы должно продолжаться после возврата вызванного метода. Если нет места для нового стекового фрейма, StackOverflowErrorон генерируется виртуальной машиной Java (JVM).

Наиболее распространенным случаем, который может исчерпать стек приложения Java, является рекурсия. В рекурсии метод вызывает себя во время выполнения. Рекурсия считается мощной техникой программирования общего назначения, но ее следует избегать с осторожностью StackOverflowError.

Пример броска a StackOverflowErrorпоказан ниже:

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

В этом примере мы определяем рекурсивный метод, recursivePrintкоторый вызывается, который печатает целое число, а затем вызывает сам себя со следующим последующим целым числом в качестве аргумента. Рекурсия заканчивается, пока мы не передадим в 0качестве параметра. Однако в нашем примере мы передали параметр от 1 и его растущих последователей, следовательно, рекурсия никогда не завершится.

Пример выполнения с использованием -Xss1Mфлага, который задает размер стека потока равным 1 МБ, показан ниже:

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

В зависимости от начальной конфигурации JVM, результаты могут отличаться, но в конечном итоге StackOverflowErrorдолжны быть выброшены. Этот пример является очень хорошим примером того, как рекурсия может вызвать проблемы, если не применять ее с осторожностью.

Как бороться с StackOverflowError

1. Самое простое решение - тщательно осмотреть трассировку стека и обнаружить повторяющуюся последовательность номеров строк. Эти номера строк указывают на рекурсивно вызываемый код. Как только вы обнаружите эти строки, вы должны тщательно проверить свой код и понять, почему рекурсия никогда не заканчивается.

2. Если вы убедились, что рекурсия реализована правильно, вы можете увеличить размер стека, чтобы разрешить большее количество вызовов. В зависимости от установленной виртуальной машины Java (JVM) размер стека потока по умолчанию может быть равен 512 КБ или 1 МБ . Вы можете увеличить размер стека потока, используя -Xssфлаг. Этот флаг можно указать либо через конфигурацию проекта, либо через командную строку. Формат -Xssаргумента: -Xss<size>[g|G|m|M|k|K]

Если у вас есть такая функция:

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

Тогда foo () будет продолжать вызывать себя, становясь все глубже и глубже, и когда пространство, используемое для отслеживания того, в каких функциях вы находитесь, заполнено, вы получите ошибку переполнения стека.

Переполнение стека означает именно это: переполнение стека. Обычно в программе есть один стек, который содержит переменные локальной области и адреса, куда возвращаться, когда заканчивается выполнение подпрограммы. Этот стек имеет тенденцию быть фиксированным диапазоном памяти где-то в памяти, поэтому он ограничен, насколько он может содержать значения.

Если стек пуст, вы не можете всплыть, если вы это сделаете, вы получите ошибку переполнения стека.

Если стек заполнен, вы не можете нажать, если вы это сделаете, вы получите ошибку переполнения стека.

Таким образом, переполнение стека появляется, когда вы размещаете слишком много в стеке. Например, в упомянутой рекурсии.

Некоторые реализации оптимизируют некоторые формы рекурсий. Хвостовая рекурсия в частности. Хвостовые рекурсивные подпрограммы являются формой подпрограмм, в которых рекурсивный вызов представляется как последнее, что делает подпрограмма. Такой обычный вызов просто сводится к прыжку.

Некоторые реализации идут так далеко, что реализуют свои собственные стеки для рекурсии, поэтому они позволяют рекурсии продолжаться до тех пор, пока в системе не будет исчерпано памяти.

Самое простое, что вы можете попробовать - это увеличить размер стека, если можете. Однако если вы не можете этого сделать, то лучше всего посмотреть, есть ли что-то, что явно вызывает переполнение стека. Попробуйте, напечатав что-нибудь до и после вызова в рутине. Это поможет вам найти рутину.

Переполнение стека обычно вызывается слишком глубокими вызовами вложенных функций (особенно легко при использовании рекурсии, то есть функции, которая вызывает себя) или выделении большого объема памяти в стеке, где использование кучи было бы более уместным.

Как вы говорите, вам нужно показать код. :-)

Ошибка переполнения стека обычно возникает, когда ваша функция вызывает гнездо слишком глубоко. Посмотрите ветку Stack Overflow Code Golf для некоторых примеров того, как это происходит (хотя в случае этого вопроса ответы намеренно вызывают переполнение стека).

Наиболее распространенной причиной переполнения стека является чрезмерно глубокая или бесконечная рекурсия . Если это ваша проблема, этот урок о Java Recursion может помочь понять проблему.

StackOverflowErrorв стек, как OutOfMemoryErrorв кучу.

Неограниченные рекурсивные вызовы приводят к использованию стекового пространства.

Следующий пример производит StackOverflowError:

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

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

StackOverflowError можно избежать, если рекурсивные вызовы ограничены, чтобы общая сумма неполных вызовов в памяти (в байтах) не превышала размер стека (в байтах).

Вот пример рекурсивного алгоритма обращения к односвязному списку. На ноутбуке со следующими характеристиками (память 4G, процессор Intel Core i5 2,3 ГГц, 64-разрядная ОС Windows 7) эта функция будет приводить к ошибке StackOverflow для связанного списка размером около 10 000.

Я хочу сказать, что мы должны использовать рекурсию разумно, всегда принимая во внимание масштаб системы. Часто рекурсия может быть преобразована в итеративную программу, которая лучше масштабируется. (Одна итерационная версия того же алгоритма приведена внизу страницы, она переворачивает односвязный список размером 1 миллион за 9 миллисекунд.)

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

Итерационная версия того же алгоритма:

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

А StackOverflowErrorэто ошибка времени выполнения в Java.

Он генерируется при превышении объема памяти стека вызовов, выделенной JVM.

Распространенным случаем StackOverflowErrorвыброса является случай, когда стек вызовов превышает избыточную глубокую или бесконечную рекурсию.

Пример:

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

Трассировки стека:

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)

В приведенном выше случае этого можно избежать путем внесения программных изменений. Но если логика программы верна и она все еще происходит, размер стека необходимо увеличить.

Это типичный случай java.lang.StackOverflowError... Метод рекурсивно вызывает себя без выхода в doubleValue(),floatValue() и т.д.

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

Результат

    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)

Вот исходный код StackOverflowErrorв OpenJDK 7

В ситуации ниже ситуация приведет к ошибке переполнения стека.

public class Example3 {

public static void main(String[] args) {

    main(new String[1]);

}

}

Вот пример

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

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

Ошибка StackOverflowError в основном возникает, когда вы пытаетесь сделать что-то, что, скорее всего, вызывает само себя и продолжается бесконечно (или до тех пор, пока не выдаст ошибку StackOverflowError).

add5(a) позвоню сам, а потом снова позвоню и так далее.

Термин «переполнение стека (переполнение)» часто используется, но неправильно. Атаки не переполняют стек, но буферизуют в стеке.

- из слайдов лекции профессора доктора Дитера Голлмана