Java StringBuilder(StringBuffer)的ensureCapacity()方法:为什么它会加倍并增加2个?

26
我已经搜索了这个问题,但是我找不到为什么StringBuilder的ensureCapacity()方法不仅会将旧容量加倍,而且还会增加2个单位的原因。
因此,默认容量为16时,下一个长度值将是34,除非整个字符串长度不超过34。 为什么不应该是32?
我最好的猜测是考虑到空字符'\u0000',但我不确定。 有人能告诉我为什么吗?

我理解了。我希望有人能够更好地解释,而不是直接给出答案。这就是为什么我保持沉默的原因。 :) - soorapadman
感谢@soorapadman的帮助!:D 我非常感激。 - Philip Paek
你在哪里找到了(value.length + 1) * 2这段代码?我的意思是说它是否在某个地方被使用了? - prime
源代码说了什么?那会告诉你需要知道的一切。 - user177800
1
尽管文档中声明了“旧容量的两倍加2”,但代码int newCapacity = (value.length + 1) * 2实际上意味着“增加一个额外的空间,然后将其翻倍”。因此,这是有道理的,因为容量已经填满,只需添加一个额外的空间,然后将新长度翻倍。 - Den Isahac
显示剩余4条评论
5个回答

8

我认为这与一种简单但有些愚蠢的方法有关,该方法可确保非常小的字符串的极端情况。

举个例子,如果我有字符串

""

如果我只是将其加倍,那么它的大小将不足以存储其他任何内容。如果我将其加倍并添加少量常数空间,我可以确保我的新值大于旧值。

为什么要增加2呢?可能是一个小的性能改进。通过添加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"

最后,增加两个字节往往可以使单词对齐的概率达到50%,而增加一个或三个字节则只能让其在25%的时间内对齐。虽然这似乎不是什么大问题,但某些架构无法容纳不对齐的读取,需要昂贵的中断调用来重写CPU中的读取,从而导致各种性能问题。


为什么不在长度为0时添加空格? - shmosel
它们包含一个if-else语句,即使他们没有添加2,也能处理0的情况。 - matt
@matt 嗯,这很奇怪,但这不是我第一次看到处理同一个“令人担忧”的情况有多种方法。 - Edwin Buck
1
@shmosel 这种猜测技术的真正奇怪之处在于,它们被赋予了最小容量来扩展。我猜他们在编写expandCapacity(...)方法后添加了minimumCapacity变量,以尽量减少垃圾堆积,但最初的设计是“在需要时扩展到所需的容量”,当函数中只有一行代码时,奇怪的(double + 2)语义更有意义。 - Edwin Buck
在Mono中,他们对于StringBuilder使用类似的技术,但是只在第一次尝试时将容量加倍。 - matt
显示剩余2条评论

0

我认为对象对齐是关键,因为length * 2 + 2的策略在内存上非常有效(见下面的解释)。

让我们来考虑一下HotSpot JVM

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

其次,在32位JVM上,sizeof(object header)等于8字节,在64位JVM with -XX:-UseCompressedOops上等于16字节

因此,对象主体应该按8字节对齐:
objectBodySize(charArray) == sizeOf(arrayLength) + sizeOf(arrayValues) == (4字节) + (arrayLength * 2字节)

如果旧的数组长度是偶数,那么新的数组长度将总是得到零大小的对齐。

举个例子:

  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 版本开始提供,而 StringBuilderAbstractStringBuilder1.5 版本开始提供。这意味着在 64位JVM 上,在 1.6 版本之前,使用两个额外字符的策略对内存没有任何成本,而在使用 -XX:+UseCompressedOops64位JVM 上,sizeof(object header) == 12 bytes


0
 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。

我认为,内存分配需要很长时间,如果我们频繁调用 ensureCapacity() 并逐渐增加 minimumCapacity,(capacity +1)*2 将分配更多的内存,并可能减少进一步的内存分配,从而节省时间。

假设初始容量为16,

只需将其倍增 16、32、64、128、256、512、1024、2048,以此类推...

使用双倍+2的方式 16、34、70、142、286、574、1150、2302,以此类推...

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


0

我认为原因是以下几个方面的综合:

  • 一些古老的启发式策略,特别是对于短缓冲区的扩展容量方法;

  • 在最早的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开发人员找到了更好的策略,也没有机会在此实现,因为它不符合文档要求。


Sun/Oracle非常小心地遵循曾经记录下来的行为。如果无法观察到,我就不会称其为已记录的行为,而只是一条实现注释。 - shmosel
可以通过capacity()方法观察到。 - Daniel Lemire

0
我从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;
} 

所以至少有两件事情是清楚的:

  • 其他更正被额外添加的理论是错误的(例如,“当它是函数中唯一的一行时,奇数(双+2)语义更有意义”不是真的)
  • 很可能最初的意思是“让我们为至少再留出一个字符的空间,并将其乘以二”

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接