Почему сохранение длинной строки приводит к ошибке OOM, но не разбиение ее на список коротких строк?

Ответ 1

По сути, вы правы.

A StringBuilder (точнее, AbstractStringBuilder) использует char[] для хранения строкового представления (хотя обычно String не является char[]). Хотя Java не гарантирует, что массив действительно хранится в смежной памяти, это, скорее всего, есть. Таким образом, всякий раз, когда добавляются строки к базовому массиву, выделяется новый массив и, если он слишком велик, бросается OutOfMemoryError.

Действительно, выполнение кода

StringBuilder b = new StringBuilder();
for (int i = 0; i < 7 * Math.pow(10, 8); i++)
    b.append("a"); // line 11

генерирует исключение:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3332)
    at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:124)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:448)
    at java.lang.StringBuilder.append(StringBuilder.java:136)
    at test1.Main.main(Main.java:11)

Когда строка <33 > char[] copy = new char[newLength]; достигается внутри Arrays.copyOf, исключение создается потому, что для массива размера newLength недостаточно памяти.

Обратите внимание также на сообщение с ошибкой: "Кучное пространство Java". Это означает, что объект (массив в этом случае) не может быть выделен в куче Java. (Изменить: есть еще одна возможная причина этой ошибки, см. ответ Marco13).

2.5.3. Heap

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

     

... Память для кучи не обязательно должна быть смежной.

     

^{Реализация Java Virtual Machine может предоставить программисту или пользователю контроль над начальным размером кучи, а также, если куча может динамически расширяться или сокращаться, контролировать максимальный и минимальный размер кучи.}

     

Следующее исключительное условие связано с кучей:

     

•   
• Если для вычисления требуется больше кучи, чем может быть предоставлено системой автоматического управления хранилищем, виртуальная машина Java генерирует OutOfMemoryError.  

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

Сравните приведенный выше код с этим:

static StringBuilder b1 = new StringBuilder();
static StringBuilder b2 = new StringBuilder();
...
static StringBuilder b10 = new StringBuilder();

public static void main(String[] args) {
    for (int i = 0; i < Math.pow(10, 8); i++)
        b1.append("a");
    System.out.println(b1.length());
    // ...
    for (int i = 0; i < Math.pow(10, 8); i++)
        b10.append("a");
    System.out.println(b10.length());
}

Выходной сигнал

100000000
100000000
100000000
100000000
100000000
100000000
100000000
100000000

а затем вызывается OOME.

В то время как первая программа не могла выделить больше, чем 7 * Math.pow(10, 8) ячейки массива, она суммируется как минимум 8 * Math.pow(10, 8).

Обратите внимание, что размер кучи можно изменить с помощью параметров инициализации VM, поэтому размер, который будет вызывать OOME, не является постоянным между системами.

Ответ 2

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

_{(Хотя до сих пор этот ответ может быть только "обоснованным предположением". Никто не может определить причину без изучения условий, при которых произошла ошибка в вашей системе)}

При конкатенации строк с помощью StringBuilder, StringBuilder будет внутренне поддерживать массив char[], содержащий символы строкой, которую нужно построить.

При добавлении последовательности строк, размер этого массива char[] может быть увеличен через некоторое время. В конечном итоге это делается в базовом классе AbstractStringBuilder:

/**
 * This method has the same contract as ensureCapacity, but is
 * never synchronized.
 */
private void ensureCapacityInternal(int minimumCapacity) {
    // overflow-conscious code
    if (minimumCapacity - value.length > 0)
        expandCapacity(minimumCapacity);
}

/**
 * This implements the expansion semantics of ensureCapacity with no
 * size check or synchronization.
 */
void expandCapacity(int minimumCapacity) {
    int newCapacity = value.length * 2 + 2;
    if (newCapacity - minimumCapacity < 0)
        newCapacity = minimumCapacity;
    if (newCapacity < 0) {
        if (minimumCapacity < 0) // overflow
            throw new OutOfMemoryError();
        newCapacity = Integer.MAX_VALUE;
    }
    value = Arrays.copyOf(value, newCapacity);
}

Он вызывается всякий раз, когда строковый построитель замечает, что новые данные не помещаются в выделенный в данный момент массив.

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

(Изменить: также посмотрите на answer1803551: это необязательно должно быть местом, откуда возникла ваша ошибка! Возможно, вы действительно пришли из класс Arrays или, скорее, изнутри JVM)

При тщательном изучении кода вы заметите, что размер массива удваивается каждый раз, когда его емкость расширяется. Это имеет решающее значение: если бы он только обеспечивал добавление нового блока данных, то добавление n символов (или других строк с фиксированной длиной) в StringBuilder будет иметь время работы O (n²). Когда размер увеличивается с постоянным коэффициентом (здесь, 2), тогда время работы есть только O (n).

Однако это удвоение размера может привести к OutOfMemoryError, хотя фактический размер результирующей строки все еще намного меньше предела.