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

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

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

""

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

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

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

что в 4 раза больше по сравнению с

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

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

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

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

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

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

Я думаю, что причина в сочетании

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

• документирование этой стратегии в самых ранних документах 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 нашел лучшую стратегию, у него нет возможности реализовать ее здесь, потому что она не будет соответствовать документации.

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

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

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

Во-вторых, 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).

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

Примеры:

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

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

Я загрузил исходный код 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) семантика имела больше смысла, когда это была единственная строка в функции» не соответствует действительности)
• скорее всего изначально имелось в виду "давайте освободим место хотя бы для еще одного символа и умножим его на два"

 public void ensureCapacity(int minimumCapacity) {
     if (minimumCapacity > value.length) {
         expandCapacity(minimumCapacity);
     }
 }



 void expandCapacity(int minimumCapacity) {
     int newCapacity = (value.length + 1) * 2;
     if (newCapacity < 0) {
         newCapacity = Integer.MAX_VALUE;
     } else if (minimumCapacity > newCapacity) {
         newCapacity = minimumCapacity;
     }
    value = Arrays.copyOf(value, newCapacity);
}

ПРИМЕЧАНИЕ. value.length — это емкость StringBuffer, а не длина.

Это не имеет ничего общего с нулевой строкой, потому что минимальная емкость равна 16.

Я думаю, что выделение памяти стоит очень много времени, и если мы часто вызываем sureCapacity() с увеличением minimumCapacity , (capacity +1)*2 выделит немного больше памяти и может сократить дальнейшее выделение и сэкономить время.

давайте рассмотрим начальную емкость как 16,

только с удвоением 16, 32, 64, 128, 256, 512, 1024, 2048 и так далее...

с двойным +2 16 , 34 , 70 , 142 , 286 , 574 , 1150 , 2302 и так далее...

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