Java StringBuilder(StringBuffer)'s ensureCapacity(): 为什么加倍加2？

Question

我已经对此进行了搜索，但我找不到为什么 StringBuilder 的 ensureCapacity() 方法不会通过仅加倍但也增加两个来延长旧容量。

所以，当16的默认容量已满时，下一个加长值将是34，除非整个字符串长度不超过34。为什么不应该是32？

我的最佳猜测是考虑使用空字符“\u0000”，但我不确定。谁能告诉我为什么？

Answer 1

我相信它与一种简单但有点愚蠢的方法有关，以确保非常小的字符串的极端情况。

例如，如果我有字符串

""

而且我只把它加倍，我没有足够的空间来存储任何其他东西。如果我将它加倍并添加一个小的常量空格，我可以确保我的新值大于我的旧值。

那为什么要加 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 个字符的扩展例程看起来像

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

最后，增加 2 的增量倾向于在大约 50% 的时间内进行单词对齐，而增加 1 或 3 的增量将在大约 25% 的时间内实现。虽然这看起来没什么大不了的，但如果不进行昂贵的中断调用以重写 CPU 中的读取，某些架构无法容纳非对齐读取，从而导致各种性能问题。

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

并且它准确地记录了 times-two plus-two 行为，因此即使在此期间一些 JRE 开发人员找到了更好的策略，也没有机会在这里实施它，因为它不符合文档。

Answer 3

我想对象对齐是一个关键，因为 length * 2 + 2-策略是内存有效的（见下面的解释）。

让我们考虑一下 HotSpot JVM。

首先，java对象是8字节对齐的，char数组也不例外。

其次，sizeof(object header) 等于 32 位 JVM 上的 8 bytes 和 64 位 JVM 上的 16 bytes -XX:-UseCompressedOops.

因此，对象主体应按 8 bytes:
对齐 objectBodySize(charArray) == sizeOf(arrayLength) + sizeOf(arrayValues) == (4 bytes) + (arrayLength * 2 bytes).

如果旧数组长度为 even，则新数组长度将始终为零大小对齐。

示例：

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 开始可用。这意味着上面带有两个额外字符的策略在 1.6 之前的 64 位 JVM 上的内存成本为零，而 sizeof(object header) == 12 bytes当运行在 64 位 JVM 上使用 -XX:+UseCompressedOops.

Answer 4

我从 Oracle 网站上下载了 Java 1.5 的原始源代码，它包含以下几行：

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

所以至少有两件事很清楚：

额外添加其他修正的理论是错误的（例如"the odd (double + 2) semantics made more sense when it was the only line in the function"是不正确的）
很可能它最初的意思是 "let's make room for at least one more character and let's multiply it by two"

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

注意：value.length是StringBuffer的容量，不是长度。

它与空字符串无关，因为最小容量是 16。

我的想法是，内存分配花费了太多时间，如果我们随着 minimumCapacity 的增加而频繁调用 ensureCapacity() ， (capacity +1)*2 将分配更多的内存并可能减少进一步的分配和节省一些时间。

假设初始容量为 16，

只有加倍 16 、 32 、 64 、 128 、 256 、 512 、 1024 、 2048 等等...

双 +2 16、34、70、142、286、574、1150、2302 等等...

因此每次内存都会逐渐增加，可能会减少分配内存的次数。

Java StringBuilder(StringBuffer)'s ensureCapacity(): 为什么加倍加2？

Java StringBuilder(StringBuffer)'s ensureCapacity(): Why is it doubled and incremented by 2?

java

stringbuilder

stringbuffer

capacity