EnsureCapacity () de Java StringBuilder (StringBuffer): Pourquoi est-il doublé et incrémenté de 2?

Je pense que la raison est une combinaison de

• Certains anciens; -) stratégie heuristique comment étendre la capacité, en particulier pour tampons courts,

• Documenter cette stratégie dans les premiers documents de l'API java,

• Sun / Oracle étant très prudent de s'en tenir à un comportement une fois documenté.

StringBuilder partage cette méthode avec son prédécesseur StringBuffer, qui lit (probablement depuis les premiers débuts, au moins dans j2sdk1. 4_02, qui arrivé à exister encore dans un dossier d'archive sur ma machine):

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

Et il documente exactement le comportement times-two plus-two, donc même si en attendant un développeur JRE avait trouvé une meilleure stratégie, il n'y a aucune chance de l'implémenter ici car il ne serait pas conforme à la documentation.

Je suppose que l'alignement des objets est une clé, car length * 2 + 2 - strategy est efficace en mémoire (voir l'explication ci-dessous).

Considérons HotSpot JVM .

Tout d'abord, les objets java sont alignés sur 8 octets et char array n'est pas une exception.

Deuxièmement, sizeof(object header) est égal à 8 bytes sur JVM 32 bits et 16 bytes sur JVM 64 bits avec -XX:-UseCompressedOops.

Ainsi, le corps de l'objet doit être aligné par 8 bytes:
objectBodySize(charArray) == sizeOf(arrayLength) + sizeOf(arrayValues) == (4 bytes) + (arrayLength * 2 bytes).

Si vieux la longueur du tableau est même , alors la nouvelle longueur du tableau donnera toujours un alignement de taille nulle.

Exemples:

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

2. oldCharArrayLength == 4 alors newCharArrayLength == 10 et objectBodySize(newCharArray) == 4 + 10 * 2 == 24

, Il est important de noter que -XX:+UseCompressedOops option est disponible depuis 1.6 alors que StringBuilder et AbstractStringBuilder sont disponibles depuis 1.5. Cela signifie que la stratégie ci-dessus avec deux caractères supplémentaires a un coût nul de mémoire sur JVM 64 bits avant 1.6, alors que sizeof(object header) == 12 bytes sur JVM 64 bits avec -XX:+UseCompressedOops.

J'ai téléchargé le code source original de Java 1.5 à partir du Web Oracle et il contient les lignes suivantes:

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

, Donc au moins deux choses sont claires:

• la théorie selon laquelle d'autres corrections ont été ajoutées est fausse (par exemple, "la sémantique impaire (double + 2) avait plus de sens quand c'était la seule ligne de la fonction" n'est pas vraie)
• très probablement, il a été conçu à l'origine comme "faisons de la place pour au moins un personnage de plus et multiplions-le par deux"

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

NOTE: valeur.la longueur est la capacité du StringBuffer, pas la longueur.

Cela n'a rien à voir avec une chaîne nulle car la capacité minimale est 16.

Ce que je pense, les allocations de mémoire coûtent tellement de temps, et si nous appelons ensureCapacity() fréquemment avec une minimumCapacity croissante, (capacity +1)*2 allouera un peu plus de mémoire et peut réduire d'autres allocations et gagner du temps.

Considérons la capacité initiale comme 16,

Uniquement avec le doublement de 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 2048 , ainsi de suite...

, Avec double +2 16 , 34 , 70 , 142 , 286 , 574 , 1150 , 2302 , ainsi de suite...

Ainsi, la mémoire va progressivement continuer à augmenter à chaque fois et peut diminuer le nombre d'allocations de mémoire.