StringBuilder 扩容规则研究 - C# - 理论研究 | Jiaying's Note = CWHISME = 人不能没有梦想，也要有足够的敬畏

# 前言

在上面对项目字符串性能优化方式及测试文章中，我查看了 StringBuilder 的源码，并总结出了 StringBuilder 的一般及自动扩容规则：

容量足够的情况下，通过 unsafe 方法进行指针及直接内存操作：

获取添加的字符串指针
获取字符数组待添加下标指针
调用 Buffer.Memcpy 进行内存拷贝进字符数组

如果后续容量不够，则进行动态扩容，不过动态扩容不是直接扩容字符数组，而是通过单向链表的方式：

将当前数据全部转移至『上一个』节点，然后自己创建一个新的字符数组进行处理。

简单来说，就是创建一个新的 StringBuilder，把自己当前所有数据转移过去，自己创建一个新的数组继续继续处理余下的。

然后就一直有个疑问：如何做到每次扩容是之前的 2 倍大小的？

然后现在研究半天发现，都知道实现扩容的具体方法是通过单链表，2 倍扩容的原理其实已经是明面上的规则了：是个非常简单的原理，只是思维上一直没考虑到而已，所以作个记录。

这里前言先不说具体原理，从试验和测试开始，具体的留到文后总结再写吧。

# 扩容测试

StringBuilder 默认容量是 16 个字符，如果测试扩容的话，数量太大容易混淆。

因此我传设置了默认的容量 1，并依次传入 1、2、3、4、5，并打印每个数值 Append 之后容量大小，测试代码如下：

	/// <summary>
	/// 执行测试
	/// </summary>
	public void DoTest()
	{
	Console.ReadKey();
	StringBuilder builder = new StringBuilder(1);
	builder.Append(1);
	Console.WriteLine(builder.Capacity);
	builder.Append(2);
	Console.WriteLine(builder.Capacity);
	builder.Append(3);
	Console.WriteLine(builder.Capacity);
	builder.Append(4);
	Console.WriteLine(builder.Capacity);
	builder.Append(5);
	Console.WriteLine(builder.Capacity);
	}

其结果为：

可以发现，每次扩容容量都是以 2 倍递增，所以为什么呢？

用反编译工具对 StringBuilder 的源代码看了又看，有点想不明白。

想不明白就像试一试，直接上调试大法，断点打到 StringBuilder 里边去：

上述截图显示的是：当前 StringBuilder 容量为 2，且 Append (3) 的情况。

盯着这个看了下，计算了一下数值与结果，一个个分析下：

minBlockCharCount 当前为 1
当前长度 Length 为 2
扩容长度为 Max (Length,minBlockCharCount)[8000 是翻倍上限，后续翻倍到这数量级后最多扩容 8000，除非传入字符串剩余字符大于 8000]
即扩容 Max (2,1)

而 Length 在这里是个属性，点进 Length 去看：

	// 当前实际存储字符长度
	public int Length
	{
	get
	{
	return this.m_ChunkOffset + this.m_ChunkLength;
	}
	}

其由 m_ChunkOffset+m_ChunkLength 构成。

将代码往上一层的 Append(char* value, int valueCount) 方法移动：

	// 当空间不足走扩容逻辑时
	else
	{
	// 当前剩余容量
	int num3 = this.m_ChunkChars.Length - this.m_ChunkLength;
	if (num3 > 0)
	{
	// 剩余容量大于 0，就先复制一部分填满
	new ReadOnlySpan<char>((void*)value, num3).CopyTo(this.m_ChunkChars.AsSpan(this.m_ChunkLength));
	//m_ChunkLength 设置为字符数组满长度
	this.m_ChunkLength = this.m_ChunkChars.Length;
	}
	// 至少扩容长度 = 添加字符串长度 - 剩余已添加字符长度
	int num4 = valueCount - num3;
	// 执行扩容
	this.ExpandByABlock(num4);
	// 将剩余字符复制进扩容后的字符数组（以前的已经变成链表的上一个节点了）
	new ReadOnlySpan<char>((void*)(value + num3), num4).CopyTo(this.m_ChunkChars);
	// 设置当前 StringBuilder 已使用长度
	this.m_ChunkLength = num4;
	}

从这里可以看出，每次扩容之前，前一个数组必然是被填满的，也就是说：

m_ChunkLength = 上一个节点实际使用字符长度
m_ChunkOffset 直接可以在扩容方法中看到，为前面所有节点的 m_ChunkLength (通过 += 赋值的)

由此可以得出结果：在扩容的时候，Length=this.m_ChunkOffset + this.m_ChunkLength = 所有节点的总长度
(注：只有在扩容的时候才是如此，否则 Capacity [this.m_ChunkChars.Length + this.m_ChunkOffset] 才是就算没装满的所有节点的总容量)

当依照所有节点的总长度创建一个新节点的时候，新节点的字符数组长度即为之前所有节点总和。

这时候统计的就是新的节点加上以前所有节点长度，两者相加：相当于就扩容了两倍！

例如旧的所有节点相加为 32，扩容的新节点为 32，那么新的总节点容量就是 64..... 以此类推。

然后就焕然大悟了，原来这么回事啊。

# 性能测试

现在知道扩容为什么是翻倍的了。

然后在这个过程中，突然想到插入问题，插入与追加显然是不同的方法：比较单链表的模式，每个链表节点都是一个单独数组，想往前面的数组插入值？

想想这种模式插入就不大好办，看了下 Insert 代码，插入一次就得创建一个 StringBuilder (除非之前的节点有空闲空间，正常情况下不可能)

而且，不遵守扩容规则：最大为扩容字符串长度，最小为默认的 16 个字符，然后重连链表结构。

//MakeRooms：每次调用插入，都会先创建一个 StringBuilder 占位，然后填充数据，一一处理链表节点

StringBuilder stringBuilder = new StringBuilder(Math.Max(count, 16), chunk.m_MaxCapacity, chunk.m_ChunkPrevious);

如果插入的下标正好还处于某一个节点字符数据中间，还需要遍历链表通过 CopyTo 移动数据，所以插入操作是比较耗时的。

# 测试代码

为此我尝试使用 TestRunner 进行测试，分别测试追加、插入开始、插入中间、插入结束的性能。

每个操作分别进行 100000 次，测试代码如下：

	private const int TestNum = 100000;

	[Test]
	public void TestAppend()
	{
	StringBuilder builder = new StringBuilder(1);
	for (int i = 0; i < TestNum; i++)
	{
	builder.Append(1);
	}
	Debug.Log("TestAppend Capacity" + builder.Capacity);
	}

	[Test]
	public void TestInsertStart()
	{
	StringBuilder builder = new StringBuilder(1);
	for (int i = 0; i < TestNum; i++)
	{
	builder.Insert(0, 1);
	}
	Debug.Log("TestInsertStart Capacity" + builder.Capacity);
	}

	[Test]
	public void TestInsertMiddle()
	{
	StringBuilder builder = new StringBuilder(1);
	for (int i = 0; i < TestNum; i++)
	{
	builder.Insert(builder.Length / 2, 1);
	}
	Debug.Log("TestInsertMiddle Capacity" + builder.Capacity);
	}

	[Test]
	public void TestInsertEnd()
	{
	StringBuilder builder = new StringBuilder(1);
	for (int i = 0; i < TestNum; i++)
	{
	builder.Insert(builder.Length, 1);
	}
	Debug.Log("TestInsertEnd Capacity" + builder.Capacity);
	}

	[Test]
	public void TestAppendNormalParams()
	{
	StringBuilder builder = new StringBuilder(1);
	for (int i = 0; i < TestNum; i++)
	{
	builder.Append("X");
	builder.Append(1);
	builder.Append("Y");
	}
	Debug.Log("TestAppendNormalParams Capacity：" + builder.Capacity);
	}

	[Test]
	public void TestAppendFormatParams()
	{
	StringBuilder builder = new StringBuilder(1);
	for (int i = 0; i < TestNum; i++)
	{
	builder.AppendFormat("X{0}Y", 1);
	}
	Debug.Log("TestAppend Capacity：" + builder.Capacity);
	}

运行结果：

TestAppend (0.026s)
---
TestAppend Capacity104192

TestAppendNormalParams (0.030s)
---
TestAppendNormalParams Capacity：304192

TestAppendFormatParams (0.032s)
---
TestAppend Capacity：304192

TestInsertStart (5.795s)
---
TestInsertStart Capacity100000

TestInsertMiddle (2.852s)
---
TestInsertMiddle Capacity100000

TestInsertEnd (0.069s)
---
TestInsertEnd Capacity100000

由于插入操作必须对插入节点后续的节点作额外处理，因此插入越靠前消耗越大，可以看出即使是直接插入最后一个节点，也是比追加字符操作更为耗时的，所以使用 StringBuilder 时，尽量不要采用插入操作。

另外 AppendFormat 采用了与 string.Format 类似的处理方式：遍历字符串找占位符，因此也会造成多余消耗 (这里因为只有一个占位符，因此与普通 3 次追加差距不大，但消耗确实也多了，占位符越多消耗越大)。

# 疑问

之前看源码，插入时通过创建一个新的 StringBuilder 插入链表，且默认最小容量为 16。

但是现在为什么打印出来的 Capacity 容量，这里插入操作的增加反而最小？难道之前分析错了？

—————————————————————————————————————————

于是另外写了一份更简单的插入代码，查看链表插入节点信息：

Capacity=this.m_ChunkChars.Length + this.m_ChunkOffset
m_ChunkLength = 上一个节点实际使用字符长度
m_ChunkChars.Length = 字符数组长度
m_ChunkOffset = 之前节点实际使用长度总和

这里插入起始的这个节点，真实容量 Capacity=16
但是到了后续节点，由于后边节点只统计实际使用长度，后续节点 Capacity=1 + 当前字符数组长度，导致只统计了插入字符串实际长度大小，容量就变回去了。

所以对于插入的节点，测试打印出来的 Capacity 增加很小是个错觉，每个插入的 StringBuilder 依然还是有占用，至少 16 个空字符数组大小。

# 总结

最后发现原因就是这么简单：因为是链表结构，扩容的新节点长度等于以前节点总和，所以同样有了倍增的效果。

不过插入操作则会打乱倍增规律：例如原本 4 个下一次倍增应该为 8，若此时插入一个字符，下一次则扩容为 10。

另外 AppendFormat 原理与普通 string.Format 类似：遍历字符串找占位符，因此也会造成多余消耗。

同时顺便测试了下追加与插入等操作的性能，插入原理是创建一个新的、至少 16 个字符容量的 StringBuilder，性能消耗很大，因此得出尽量不要使用插入操作的结论。

性能优化 C#