Java StringBuilder (StringBuffer) securityCapacity(): почему он удваивается и увеличивается на 2?

Ответ 1

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

Например, если у меня есть строка

""

и я только удвою его, у меня не будет достаточного размера, чтобы хранить в нем что-нибудь еще. Если я удвою его и добавлю небольшое постоянное количество пробелов, я могу заверить, что мое новое значение больше моего старого.

Зачем увеличивать его на два? Вероятно, небольшое улучшение производительности. Добавив два вместо 1, я могу избежать промежуточного расширения для небольших расширений (от 0 до 10 символов, подробно описанных ниже)

"" => expand => "1" => expand => "123" expand => "1234567" expand => "123456789012345"

который имеет 4 расширения по сравнению с

"" => expand => "12" => expand => "123456" => expand => "123456789012"

который 3 расширяется. Это также хорошо работает для одной строки char (расширяется до 10 символов)

"1" => expand => "1234" => expand => "1234567890"

в то время как процедура расширения 1 char выглядит как

"1" => expand => "123" => expand => "1234567" => expand => "123456789012345"

Наконец, добавленный приращение в два раза приближается к слову, выровняющему примерно 50% времени, в то время как добавленные приращения одного или трех будут делать примерно 25% времени. Хотя это может показаться неважным, некоторые архитектуры не могут размещать не выровненные чтения без дорогостоящих вызовов прерываний, чтобы переписать чтение в CPU, что привело к различным проблемам с производительностью.

Ответ 2

Я думаю, что причиной является комбинация

• какая-то древняя;-) эвристическая стратегия, как расширить возможности, особенно для короткие буферы,

• документирование этой стратегии в ранних java-документах API,

• Sun/Oracle очень осторожно придерживается некогда документированного поведения.

StringBuilder использует этот метод со своим предшественником StringBuffer, который читает (возможно, с самого раннего начала, по крайней мере, в j2sdk1.4_02, который по-прежнему существует в какой-либо архивной папке на моей машине):

/**
 * Ensures that the capacity of the buffer is at least equal to the
 * specified minimum.
 * If the current capacity of this string buffer is less than the 
 * argument, then a new internal buffer is allocated with greater 
 * capacity. The new capacity is the larger of: 
 * <ul>
 * <li>The <code>minimumCapacity</code> argument. 
 * <li>Twice the old capacity, plus <code>2</code>. 
 * </ul>
 * If the <code>minimumCapacity</code> argument is nonpositive, this
 * method takes no action and simply returns.
 *
 * @param   minimumCapacity   the minimum desired capacity.
 */
public synchronized void ensureCapacity(int minimumCapacity) {
    if (minimumCapacity > value.length) {
        expandCapacity(minimumCapacity);
    }
}

И он точно документирует поведение "два плюс два", поэтому даже если разработчик JRE нашел лучшую стратегию, нет возможности реализовать его здесь, потому что он не будет соответствовать документации.

Ответ 3

Я полагаю, что выравнивание объекта является ключом, потому что length * 2 + 2 -стратегия эффективна с точки зрения памяти (см. объяснение ниже).

Рассмотрим HotSpot JVM.

Прежде всего, java-объекты выравниваются по 8 байт, а массив char не является исключением.

Во-вторых, sizeof(object header) равно 8 bytes на 32-разрядной JVM и 16 bytes на 64-разрядной JVM с -XX: -UseCompressedOops.

Таким образом, тело объекта должно быть выровнено с помощью 8 bytes:
objectBodySize(charArray) == sizeOf(arrayLength) + sizeOf(arrayValues) == (4 bytes) + (arrayLength * 2 bytes).

Если длина старого массива четная, тогда новая длина массива всегда будет давать выравнивание нулевого размера.

Примеры:

• oldCharArrayLength == 6, затем newCharArrayLength == 14 и objectBodySize(newCharArray) == 4 + 14 * 2 == 32

• oldCharArrayLength == 4, затем newCharArrayLength == 10 и objectBodySize(newCharArray) == 4 + 10 * 2 == 24

Важно отметить, что флаг -XX: + UseCompressedOops доступен с 1.6, тогда как StringBuilder и AbstractStringBuilder доступны с 1,5 > . Это означает, что вышеприведенная стратегия с двумя дополнительными символами имеет нулевую стоимость памяти на 64-разрядной JVM до 1.6, тогда как sizeof(object header) == 12 bytes при запуске на 64- бит JVM с -XX: + UseCompressedOops.

Ответ 4

Я загрузил исходный код Java 1.5 из веб-сайта Oracle и содержал следующие строки:

/**
 * This implements the expansion semantics of ensureCapacity with no
 * size check or synchronization.
 */
void expandCapacity(int minimumCapacity) {
    int newCapacity = (value.length + 1) * 2;
    if (newCapacity < 0) {
        newCapacity = Integer.MAX_VALUE;
    } else if (minimumCapacity > newCapacity) {
        newCapacity = minimumCapacity;
    }   
    char newValue[] = new char[newCapacity];
    System.arraycopy(value, 0, newValue, 0, count);
    value = newValue;
} 

Итак, по крайней мере две вещи ясны:

• теория, что дополнительные поправки были добавлены дополнительно, неверна (например, "нечетная (двойная + 2) семантика имеет больше смысла, когда она была единственной строкой в ​​функции" не соответствует истине ")
• Скорее всего, это изначально означало, что "пусть место для хотя бы еще одного символа и позволяет умножить его на два"