每当打酱油的时候就有可能会查看.NET的源代码以满足自己的“好奇心”。这次来学习一下M$是如何实现StringBuilder这个类的，揭开它的神秘“面纱”。
在看源代码之前，我自己也想过如何去实现这个“缓冲区”，无非是扩容、减少容量。参考List的实现方式，我们可能想过每次超过预先的缓冲区容量时直接分配2倍的容量，但M$似乎比我们想得要多。
我个人认为，M$确实考虑到了我之前没考虑的情况。但是看过源代码之后，我觉得M$在这个类的实现上还是不够完善，至少它自己宣称的一些“优化”并没有得到很好的实现。
对于基础类库，M$主要考虑到了如下几个方面的问题：
- 避免在大对象堆上分配对象。
- 似乎M$对超过85K的对象都很少采用优化（合并空间等），在StringBuilder实现的时候也考虑到了这一点。
- 扩容时引起的性能问题。
- M$宣称StringBuilder的最大长度能达到32位整数的最大值（大约2G个字节）。假如我们有一个很大的字符串，如果像List那样扩容会引起性能上的问题。
- 插入、删除操作的性能问题。
- 这点与上一点类似。在List插入或删除元素时，会引起后面的所有元素位置的移动。
看到微软想到的这些问题（其实是我想到的 – -），可以肯定的是StringBuilder实现的时候是一个链表，每个链表都有一定的缓冲区（这点和ConcurrentQueue类似）。StringBuilder在内部拷贝内容时似乎是线程安全的（这点是借助了String类的一个内部方法wstrcpy），但整个StringBuilder似乎不是线程安全的。
说到这里，StringBuilder类似乎没有什么神秘感了，我们自己应该也能实现一个出来。但这里我们还是学习一下M$的实现吧。
首先是类的字段：
internal char[] m_ChunkChars; // The characters in this block
internal StringBuilder m_ChunkPrevious; // Link to the block logically before this block
internal int m_ChunkLength; // The index in m_ChunkChars that represent the end of the block
internal int m_ChunkOffset; // The logial offset (sum of all characters in previous blocks)
internal int m_MaxCapacity = 0;
internal const int MaxChunkSize = 8000;注释已经写得比较清楚了。m_ChunkChars是保存当前节点内容的一个缓冲区（字符数组，以后都称作缓冲区），m_ChunkPrevious是上一个节点的引用（StringBuilder类对外提供的都是最后一个节点的引用，其他节点都是不可见的）。
m_ChunkLength表示当前缓冲区中已经使用的最后一个字符的索引，m_ChunkOffset是在逻辑上这个节点的开始字符在整个“字符串”中的位置。
MaxChunkSize就限定了每个节点存储的最大字符数（大约16K的容量），但是这并不是绝对的，具体的下面会说到。
首先是类的构造方法，这里我们只看一个：
[System.Security.SecuritySafeCritical] // auto-generated
public StringBuilder(String value, int startIndex, int length, int capacity) {
//省略一大段判断参数的代码
m_MaxCapacity = Int32.MaxValue;
if (capacity == 0) {
capacity = DefaultCapacity;
}
if (capacity < length)
capacity = length;
m_ChunkChars = new char[capacity];
m_ChunkLength = length;
unsafe {
fixed (char* sourcePtr = value)
ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length);
}
}当以一个字符串作为参数时，会将字符串的内容拷贝到缓冲区中。看到这里相信大家已经发现我之前所说的“不是很完善”的地方了。如果没看出来，那继续往下看吧。
虽然已经知道了这个类的结构，但是为了加深印象我们看一下ToString方法吧：
[System.Security.SecuritySafeCritical] // auto-generated
public override String ToString() {
Contract.Ensures(Contract.Result<String>() != null);
VerifyClassInvariant();
if (Length == 0)
return String.Empty;
string ret = string.FastAllocateString(Length);
StringBuilder chunk = this;
unsafe {
fixed (char* destinationPtr = ret)
{
do
{
if (chunk.m_ChunkLength > 0)
{
// Copy these into local variables so that they are stable even in the presence of ----s (hackers might do this)
char[] sourceArray = chunk.m_ChunkChars;
int chunkOffset = chunk.m_ChunkOffset;
int chunkLength = chunk.m_ChunkLength;
// Check that we will not overrun our boundaries.
if ((uint)(chunkLength + chunkOffset) <= ret.Length && (uint)chunkLength <= (uint)sourceArray.Length)
{
fixed (char* sourcePtr = sourceArray)
string.wstrcpy(destinationPtr + chunkOffset, sourcePtr, chunkLength);
}
else
{
throw new ArgumentOutOfRangeException("chunkLength", Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
}
chunk = chunk.m_ChunkPrevious;
} while (chunk != null);
}
}
return ret;
}Length是一个属性值计算这个链表内一共存了多少个字符，那么毫无疑问直接return m_ChunkOffset + m_ChunkLength就行了。取到长度后，先为返回的字符串分配一个预留的存储空间（FastAllocateString，具体代码这里就不分析了）。
接下来的do-while循环将每个节点存储的内容按照所处的位置拷贝到字符串的相应位置上。注意由于用户拿到的是最后一个节点，所以复制过程是从最后往前进行的。顺便提一句，虽然M$说字符串是不可变的，但实际上我们看到M$还是可以通过内部方法想怎么改就怎么改……
取其中某个位置上的字符（或者设置某个位置的字符）也与之类似，从最后一个往前找就行了，当遇到index – m_ChunkOffset >= m_ChunkLength 的就表示要查找的字符在当前节点中：
StringBuilder chunk = this;
for (; ; )
{
int indexInBlock = index - chunk.m_ChunkOffset;
if (indexInBlock >= 0)
{
if (indexInBlock >= chunk.m_ChunkLength)
throw new IndexOutOfRangeException();
return chunk.m_ChunkChars[indexInBlock];
}
chunk = chunk.m_ChunkPrevious;
if (chunk == null)
throw new IndexOutOfRangeException();
}从这里可以看出，取长度、取某个位置的字符的时间复杂度并不是O(1)的。
接下来是比较重要的几个内部方法，我们一个一个看吧。
首先是在最后添加的Append方法（参数为char* value, int valueCount，是internal的unsafe方法），其他的Append方法都是调用的这个方法。
很自然地有两种情况：第一种是最后一个节点正好有这么多空间，那么直接丢进去就完事了：
int newIndex = valueCount + m_ChunkLength;
if (newIndex <= m_ChunkChars.Length)
{
ThreadSafeCopy(value, m_ChunkChars, m_ChunkLength, valueCount);
m_ChunkLength = newIndex;否则的话，就需要进行扩容：
else
{
// Copy the first chunk
int firstLength = m_ChunkChars.Length - m_ChunkLength;
if (firstLength > 0)
{
ThreadSafeCopy(value, m_ChunkChars, m_ChunkLength, firstLength);
m_ChunkLength = m_ChunkChars.Length;
}
// Expand the builder to add another chunk.
int restLength = valueCount - firstLength;
ExpandByABlock(restLength);
Contract.Assert(m_ChunkLength == 0, "Expand did not make a new block");
// Copy the second chunk
ThreadSafeCopy(value + firstLength, m_ChunkChars, 0, restLength);
m_ChunkLength = restLength;
}我画了一个图来表示上面用到的几个变量：
ExpandByABlocks也是一个内部方法，如果你对上面的实现有问题先不要着急，看看这个方法的实现：
private void ExpandByABlock(int minBlockCharCount)
{
//省略Contracts部分的代码
VerifyClassInvariant();
if ((minBlockCharCount + Length) > m_MaxCapacity)
throw new ArgumentOutOfRangeException("requiredLength", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
// Compute the length of the new block we need
// We make the new chunk at least big enough for the current need (minBlockCharCount)
// But also as big as the current length (thus doubling capacity), up to a maximum
// (so we stay in the small object heap, and never allocate really big chunks even if
// the string gets really big.
int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));
// Copy the current block to the new block, and initialize this to point at the new buffer.
m_ChunkPrevious = new StringBuilder(this);
m_ChunkOffset += m_ChunkLength;
m_ChunkLength = 0;
// Check for integer overflow (logical buffer size > int.MaxInt)
//代码省略
VerifyClassInvariant();
}示意图如下：
实际上，M$是在当前节点之前生成了一个新的节点（内容全部复制到了这个新的节点中），新生成的节点按照所请求的字符数分配初始容量。具体计算方法为：
- 至少为原来长度的2倍（但不超过8000个字符）；
- 如果请求的字符超过了原来长度的2倍，那么直接用请求的长度来分配空间。
看到这里相信你又有问题了，对，我也是……
MakeRoom方法：主要用于Insert操作，将索引处后面的部分后移。首先找到索引所在的节点：
chunk = this;
while (chunk.m_ChunkOffset > index)
{
chunk.m_ChunkOffset += count;
chunk = chunk.m_ChunkPrevious;
}
indexInChunk = index - chunk.m_ChunkOffset;一看写这个方法的人和写索引器方法的人不是同一个，所以M$内部也会互相吐槽（接下来会看到）。
如果插入的内容恰好在预先分配的容量之内，且要移动的字符在32个以内，那么就用简单的方法直接往后移（这点是处于频繁调用Append方法插入短字符串时考虑）：
// Cool, we have some space in this block, and you don't have to copy much to get it, go ahead
// and use it. This happens typically when you repeatedly insert small strings at a spot
// (typically the absolute front) of the buffer.
if (!doneMoveFollowingChars && chunk.m_ChunkLength <= DefaultCapacity * 2 && chunk.m_ChunkChars.Length - chunk.m_ChunkLength >= count)
{
for (int i = chunk.m_ChunkLength; i > indexInChunk; )
{
--i;
chunk.m_ChunkChars[i + count] = chunk.m_ChunkChars[i];
}
chunk.m_ChunkLength += count;
return;
}否则呢，就先分配一个新的节点：
StringBuilder newChunk = new StringBuilder(Math.Max(count, DefaultCapacity), chunk.m_MaxCapacity, chunk.m_ChunkPrevious);
newChunk.m_ChunkLength = count;然后呢将当前节点中处于开始位置之前的东东都复制过去，并且把这个位置之后的内容复制到当前节点的开始位置：
// Copy the head of the buffer to the new buffer.
int copyCount1 = Math.Min(count, indexInChunk);
if (copyCount1 > 0)
{
unsafe {
fixed (char* chunkCharsPtr = chunk.m_ChunkChars) {
ThreadSafeCopy(chunkCharsPtr, newChunk.m_ChunkChars, 0, copyCount1);
// Slide characters in the current buffer over to make room.
int copyCount2 = indexInChunk - copyCount1;
if (copyCount2 >= 0)
{
ThreadSafeCopy(chunkCharsPtr + copyCount1, chunk.m_ChunkChars, 0, copyCount2);
indexInChunk = copyCount2;
}
}
}
}这样子的话，新插入的节点就会预留足够的空间，把最后一个节点的开始位置和引用重新设置一下：
chunk.m_ChunkPrevious = newChunk; // Wire in the new chunk
chunk.m_ChunkOffset += count;
if (copyCount1 < count)
{
chunk = newChunk;
indexInChunk = copyCount1;
}那么Insert方法就很好写了：
unsafe private void Insert(int index, char* value, int valueCount)
{
if ((uint)index > (uint)Length)
{
throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
if (valueCount > 0)
{
StringBuilder chunk;
int indexInChunk;
MakeRoom(index, valueCount, out chunk, out indexInChunk, false);
ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, value, valueCount);
}
}ReplaceInPlaceAtChunk会根据当前块的容量决定是否需要把部分内容拷贝到下一个节点中，这里就不看了。
最后一个Remove的内部方法用于删除其中部分的内容，本质上，找到删除开始的节点和结束的节点，直接把结束节点的上一个节点置为开始节点，并且设置相应的字段就行了。中间的节点直接不管，交给GC处理吧。当然M$还考虑一点，就是是否要将最后节点的元素复制到开始节点中来，这里就不多说了。
看到这里，相信对StringBuilder的实现有了一个大概的了解（而且我也饿了，要去吃东西并go home了）。相信大家也产生了很多和我一样的问题：新增加的节点似乎都没有保证不分配到大对象堆中。
比如我们像StringBuilder添加一个大于8000字符的字符串，M$就直接生成了一个同等长度的字符数组，并没有把字符串进行拆分。
另外一点，分配一个新的节点时（ExpandByABlock），如果初始的字符串不是很长（比如只有50个字符），并且容量也是一个很小的值时，新增的节点可能只有很小的缓冲区。比如，可能会连续生成诸如16、32、64、128个字符的节点。
对于第一个问题，M$可能是这么认为的：既然你要插入一个这么大的字符串，那么你肯定都已经在大对象堆中分配了字符串了，那么我也这样做。而且这种情况也不会经常发生。但对于第二个问题，我认为就不好了，这样节点就会变得多（虽然不会很多，但还是没有必要这样）。
所以可以看出M$实现时对每个节点的容量并不是很“智能”。但我觉得这还是由于编程序和设计的人偷懒，不想把算法弄得复杂。所以我认为M$还是有一些可以改进的余地（其他的一些问题比如Length还可以设置，就有点让人莫名其妙）。
总的来说，StringBuilder似乎适合小字符串的不断连接操作，对于添加新的大字符串，似乎不是很好（而且如果期间有大容量的删除操作，那么多余的空间也会浪费掉）。而且，初始容量最好不要设置得太小（避免出现不必要的节点的情况）。
虽然有一定的缺陷，但总体上还是可以达到Builder这个名字的要求吧。
PS: M$互相吐槽的代码：
if (delta > 0)
{
// the end of the string value of the current StringBuilder object is padded with the Unicode NULL character
Append('', delta); // We could improve on this, but who does this anyway?
}