Asegure la capacidad de StringBuilder(StringBuffer) de Java(): ¿Por qué se duplica y se incrementa en 2?

string vs stringbuilder c#

Question

He buscado sobre esto, pero no pude encontrar por qué el método ensureCapacity() StringBuilder no alarga la capacidad anterior simplemente duplicando sino también agregando dos.

Por lo tanto, cuando la capacidad predeterminada de 16 está llena, el siguiente valor alargado será 34 a menos que la longitud de toda la cadena no exceda de 34. ¿Por qué no debería ser 32?

Mi mejor conjetura es considerar un carácter nulo, ''/ u0000'', pero no estoy seguro. puede alguien decirme por que?

Answer 1

Creo que la razón es una combinación de

• una estrategia heurística antigua ;-) sobre cómo ampliar la capacidad, especialmente para buffers cortos,

• documentando esta estrategia en los primeros documentos API de Java,

• Sun / Oracle es muy cuidadoso de atenerse a un comportamiento documentado una vez.

StringBuilder comparte este método con su predecesor StringBuffer, que lee (probablemente desde los primeros inicios, al menos en j2sdk1.4_02, que aún existía en alguna carpeta de archivo en mi máquina):

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

Y documenta exactamente el comportamiento de los tiempos dos y dos más, por lo que incluso si mientras tanto algún desarrollador de JRE había encontrado una mejor estrategia, no hay posibilidad de implementarla aquí porque no se ajustaría a la documentación.

Answer 2

Creo que tiene que ver con una forma simple, aunque algo tonta, de asegurar el caso de esquina de cuerdas muy pequeñas.

Por ejemplo, si tengo la cadena

""

y solo lo doblo, no tendré un tamaño suficiente para almacenar nada más en él. Si lo doblo y agrego un pequeño número constante de espacios, puedo asegurar que mi nuevo valor sea más grande que el anterior.

¿Por qué incrementarlo en dos entonces? Probablemente una pequeña mejora de rendimiento. Al agregar dos en lugar de 1, puedo evitar una expansión intermedia para pequeñas expansiones (0 a 10 caracteres detallados a continuación)

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

que es 4 se expande en comparación con

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

que es 3 se expande. Esto también funciona bien para cadenas de caracteres (expandiéndose a 10 caracteres)

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

mientras que la rutina de expansión de 1 char parece

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

Finalmente, un incremento adicional de dos tiende a alinearse con palabras aproximadamente el 50% del tiempo, mientras que los incrementos agregados de uno o tres lo harían aproximadamente el 25% del tiempo. Si bien esto puede no parecer un gran problema, algunas arquitecturas no pueden acomodar lecturas no alineadas sin costosas llamadas de interrupción para volver a escribir la lectura en la CPU, lo que lleva a todo tipo de problemas de rendimiento.

Answer 3

Descargué el código fuente original de Java 1.5 de la web de Oracle y contiene las siguientes líneas:

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

Así que al menos dos cosas son claras:

• la teoría de que otras correcciones se agregaron adicionalmente es falsa (por ejemplo, "la semántica impar (doble + 2) tenía más sentido cuando era la única línea en la función" no es cierta)
• lo más probable es que originalmente se entendiera como "hagamos espacio para al menos un personaje más y multipliquémoslo por dos"

Answer 4

Supongo que la alineación de objetos es una clave, porque la estrategia length * 2 + 2 es efectiva en memoria (vea la explicación a continuación).

Consideremos HotSpot JVM .

En primer lugar, los objetos java están alineados con 8 bytes y la matriz char no es una excepción.

En segundo lugar, sizeof(object header) es igual a 8 bytes en JVM de 32 bits y 16 bytes en JVM de 64 bits con -XX: -UseCompressedOops .

Por lo tanto, el cuerpo del objeto debe estar alineado por 8 bytes :
objectBodySize(charArray) == sizeOf(arrayLength) + sizeOf(arrayValues) == (4 bytes) + (arrayLength * 2 bytes) .

Si la longitud de la matriz antigua es par , la nueva longitud de la matriz siempre dará una alineación de tamaño cero.

Ejemplos:

1. oldCharArrayLength == 6 luego newCharArrayLength == 14 y objectBodySize(newCharArray) == 4 + 14 * 2 == 32

2. oldCharArrayLength == 4 luego newCharArrayLength == 10 y objectBodySize(newCharArray) == 4 + 10 * 2 == 24

Es importante tener en cuenta que el indicador -XX: + UseCompressedOops está disponible desde 1.6, mientras que StringBuilder y AbstractStringBuilder están disponibles desde 1.5 . Significa que la estrategia anterior con dos caracteres adicionales tiene un costo cero de memoria en JVM de 64 bits antes de 1.6 , mientras que sizeof(object header) == 12 bytes cuando se ejecuta en JVM de 64 bits con -XX: + UseCompressedOops .

Answer 5

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

NOTA: value.length es la capacidad del StringBuffer, no la longitud.

No tiene nada que ver con una cadena nula porque la capacidad mínima es 16.

Lo que creo es que las asignaciones de memoria cuestan mucho tiempo, y si estamos llamando a asegurarCapacity () con frecuencia con una capacidad mínima en aumento, (capacidad +1) * 2 asignará un poco más de memoria y puede reducir las asignaciones adicionales y ahorrar algo de tiempo.

consideremos la capacidad inicial como 16,

solo duplicando 16, 32, 64, 128, 256, 512, 1024, 2048, etc.

con doble +2 16, 34, 70, 142, 286, 574, 1150, 2302, etc.

Por lo tanto, la memoria irá aumentando cada vez más y puede disminuir el número de asignaciones de memoria.