源码上看 .NET 中 StringBuilder 拼接字符串的实现

前几天写了一篇StringBuilderTextWriter二者之间区别的文章(链接)。当时提了一句没有找到相关源码,于是随后有很多热心人士给出了相关的源码链接(链接),感谢大家。这几天抽了点时间查看了下StringBuilder是如何动态构造字符串的,发现在.NET Core中字符串的构建似乎和我原先猜想的并不完全一样,故此写了这篇文章,如有错误,欢迎指出。

StringBuilder字段和属性

字符数组

明确一点的是,StringBuilder的内部确实使用字符数组来管理字符串信息的,这一点上和我当时的猜测是差不多的。相较于字符串在大多数情况下的不变性而言,字符数组有其优点,即修改字符数组内部的数据不会全部重新创建字符数组(字符串的不变性)。下面是StringBuilder的部分源码,可以看到,内部采用m_ChunkChars字段存储字符数组信息。

public sealed class StringBuilder
{
    internal char[] m_ChunkChars;
    ...
}

然而,采用字符数组并不是没有缺点,数组最大的缺点就是在在使用前就需要指定它的空间大小,这种固定大小的数组空间不可能有能力处理多次的字符串拼接,总有某次,数组中的空余部分塞不下所要拼接的字符串。如果某次拼接的字符串超过数组的空闲空间时,一种易想到做到的方法就是开辟一个更大的空间,并将原先的数据复制过去。这种方法能够保证数组始终是连续的,然而,它的问题在于,复制是一个非常耗时的操作,如非必要,尽可能地降低复制的频率。在.NET Core中,StringBuilder采用了一个新方法避免了复制操作。

单链表

为了能够有效地提高性能,StringBuilder采用链表的形式规避了两个字符数组之间的复制操作。在其源代码中,可以发现每个StringBuilder内部保留对了另一个StringBuilder的引用。

public sealed class StringBuilder
{
    internal StringBuilder? m_ChunkPrevious;
    ...
}

StringBuilder中,每个对象都维护了一个m_ChunkPrevious引用,按字段命名的意思来说,就是每个类对象都维护指向前一个类对象的引用。这一点和我们常见的单链表结构有点一点不太一样,常见的单链表结构中每个节点维护的是指向下一个节点的引用,这和StringBuilder所使用的模式刚好相反,挺奇怪的。整理下,这部分有两个问题:

  1. 为什么说采用单链表能避免复制操作?
  2. 为什么采用逆向链表,即每个节点保留指向前一个节点的引用?

对于第一个问题,试想下,如果又有新的字符串需要拼接且其长度超过字符数组空闲的容量时,可以考虑新开辟一个新空间专门存储超额部分的数据。这样,先前部分的数据就不需要进行复制了,但这又有一个新问题,整个数据被存储在两个不相连的部分,怎么关联他们,采用链表的形式将其关联是一个可行的措施。以上就是StringBuilder拼接字符串最为核心的部分了。

那么,对于第二个问题,采用逆向链表对的好处是什么?这里我给出的原因属于我个人的主观意见,不一定对。从我平时使用上以及一些开源类库中来看,对StringBuilder使用最广泛的功能就是拼接字符串了,即向尾部添加新数据。在这个基础上,如果采用正向链表(每个节点保留下一个节点的引用),那么多次拼接字符串在数组容量不够的情况下,势必需要每次循环找到最后一个节点并添加新节点,时间复杂度为O(n)。而采用逆向链表,因为用户所持有的就是最后一个节点,只需要在当前节点上做些处理就可以添加新节点,时间复杂度为O(1)。因此,StringBuilder内的字符数组可以说是字符串的一个部分,也被称为Chunk。

举个例子,如果类型为Stringbuilder变量sb内已经保存了HELLO字符串,再添加WORLD时,如果字符数组满了,再添加就会构造一个新StringBuilder节点。注意的是调用类方法不会改变当前变量sb指向的对象,因此,它会移动内部的字符数组引用,并将当前变量的字符数组引用指向WORLD。下图中的左右两图是添加前后的说明图,其中黄色StringBuilder是同一个对象。

链表

当然,采用链表并非没有代价。因为链表没有随机读取的功能。因此,如果向指定位置添加新数据,这反而比只使用一个字符数组来得慢。但是,如果前面的假设没错的话,也就是最频繁使用的是尾部拼接的话,那么使用链表的形式是被允许的。根据使用场景频率的不同,提供不同的实现逻辑。

各种各样的长度

剩下来的部分,就是描述各种各样的长度及其他数据。主要如下:

public sealed class StringBuilder
{
    internal int m_ChunkLength;
    internal int m_ChunkOffset;
    internal int m_MaxCapacity;
    internal const int DefaultCapacity = 16;
    internal const int MaxChunkSize = 8000;
    public int Length
    {
        get => m_ChunkOffset + m_ChunkLength;
    }
    ...
}
  • m_ChunkLength描述当前Chunk存储信息的长度。也就是存储了字符数据的长度,不一定等于字符数组的长度。
  • m_ChunkOffset描述当前Chunk在整体字符串中的起始位置,方便定位。
  • m_MaxCapacity描述构建字符串的最大长度,通常设置为int最大值。
  • DefaultCapacity描述默认设置的空间大小,这里设置的是16。
  • MaxChunkSize描述Chunk的最大长度,也就是Chunk的容量。
  • Length属性描述的是内部保存整体字符串的长度。

构造函数

上述讲述的是StringBuilder的各个字段和属性的意义,这里就深入看下具体函数的实现。首先是构造函数,这里仅列举本文所涉及到的几个构造函数。

public StringBuilder()
{
    m_MaxCapacity = int.MaxValue;
    m_ChunkChars = new char[DefaultCapacity];
}

public StringBuilder(string? value, int startIndex, int length, int capacity)
{
    ...
    m_MaxCapacity = int.MaxValue;
    if (capacity == 0)
    {
        capacity = DefaultCapacity;
    }
    capacity = Math.Max(capacity, length);

    m_ChunkChars = GC.AllocateUninitializedArray<char>(capacity);
    m_ChunkLength = length;

    unsafe
    {
        fixed (char* sourcePtr = value)
        {
            ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length);
        }
    }
}

private StringBuilder(StringBuilder from)
{
    m_ChunkLength = from.m_ChunkLength;
    m_ChunkOffset = from.m_ChunkOffset;
    m_ChunkChars = from.m_ChunkChars;
    m_ChunkPrevious = from.m_ChunkPrevious;
    m_MaxCapacity = from.m_MaxCapacity;
    ...
}

这里选出了三个和本文关系较为紧密的构造函数,一个个分析。

  1. 首先是默认构造函数,该函数没有任何的输入参数。代码中可以发现,其分配的长度就是16。也就是说不对其做任何指定的话,默认初始长度为16个Char型数据,即32字节。
  2. 第二个构造函数是当构造函数传入为字符串时所调用的,这里我省略了在开始最前面的防御性代码。这里的构造过程也很简单,比较传入字符串的大小和默认容量DefaultCapacity的大小,并开辟二者之间最大值的长度,最后将字符串复制到数组中。可以发现的是,这种情况下,初始字符数组的长度并不总是16,毕竟如果字符串长度超过16,肯定按照更长的来。
  3. 第三个构造函数专门用来构造StringBuilder的节点的,或者说是StringBuilder的复制,即原型模式。它主要用在容量不够构造新的节点,本质上就是将内部数据全部赋值过去。

从前两个构造函数可以看出,如果第一次待拼接的字符串长度超过16,那么直接将该字符串以构造函数的参数传入比构建默认StringBuilder对象再使用Append方法更加高效,毕竟默认构造函数只开辟了16个char型空间。

Append方法

这里主要看StringBuilder Append(char value, int repeatCount)这个方法(位于第710行)。该方法主要是向尾部添加char型字符value,一共添加repeatCount个。

public StringBuilder Append(char value, int repeatCount)
{
    ...

    int index = m_ChunkLength;
    while (repeatCount > 0)
    {
        if (index < m_ChunkChars.Length)
        {
            m_ChunkChars[index++] = value;
            --repeatCount;
        }
        else
        {
            m_ChunkLength = index;
            ExpandByABlock(repeatCount);
            Debug.Assert(m_ChunkLength == 0);
            index = 0;
        }
    }

    m_ChunkLength = index;
    AssertInvariants();
    return this;
}

这里仅列举出部分代码,起始的防御性代码以及验证代码略过。看下其运行逻辑:

  1. 依次循环当前字符repeatCount次,对每一次执行以下逻辑。(while大循环)
  2. 如果当前字符数组还有空位时,则直接向内部进行添加新数据。(if语句命中部分)
  3. 如果当前字符数组已经被塞满了,首先更新m_ChunkLength值,因为数组被塞满了,因此需要下一个数组来继续放数据,当前的Chunk长度也就是整个字符数组的长度,需要更新。其次,调用了ExpandByABlock(repeatCount)函数,输入参数为更新后的repeatCount数据,其做的就是构建新的节点,并将其挂载到链表上。
  4. 更新m_ChunkLength值,记录当前Chunk的长度,最后将本身返回。

接下来就是ExpandByABlock方法的实现。

private void ExpandByABlock(int minBlockCharCount)
{
    ...
    int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));
    ...

    // Allocate the array before updating any state to avoid leaving inconsistent state behind in case of out of memory exception
    char[] chunkChars = GC.AllocateUninitializedArray<char>(newBlockLength);

    // Move all of the data from this chunk to a new one, via a few O(1) pointer adjustments.
    // Then, have this chunk point to the new one as its predecessor.
    m_ChunkPrevious = new StringBuilder(this);
    m_ChunkOffset += m_ChunkLength;
    m_ChunkLength = 0;

    m_ChunkChars = chunkChars;

    AssertInvariants();
}

和上面一样,仅列举出核心功能代码。

  1. 设置新空间的大小,该大小取决于三个值,从当前字符串长度和Chunk最大容量取较小值,然后从较小值和输入参数长度中取最大值作为新Chunk的大小。值得注意的是,这里当前字符串长度通常是Chunk已经被塞满的情况下,可以理解成所有Chunk的长度之和。
  2. 开辟新空间。
  3. 通过上述最后一个构造函数,构造向前的节点。当前节点仍然为最后一个节点,更新其他值,即偏移量应该是原先偏移量加上一个Chunk的长度。清空当前Chunk的长度以及将新开辟空间给Chunk引用。

对于Append(string? value)这个函数的实现功能和上述说明是差不多的,基本都是新数据先往当前的字符数组内塞,如果塞满了就添加新节点并刷新当前字符数组数据再塞。详细的功能可以从L802开始看。这里不做过多说明。

验证

当然,以上只是阅读代码的流程,具体是否正确还可以做点测试来验证。这里我做了一个小测试demo。

var sb = new StringBuilder();
sb.Append('1', 10);
sb.Append('2', 6);
sb.Append('3', 24);
sb.Append('4', 15);
sb.Append("hello world");
sb.Append("nice to meet you");
Console.WriteLine($"结果:{sb.ToString()}");

var p = sb;
char[] data;
Type type = sb.GetType();
int count = 0;
while (p != null)
{
    count++;
    data = (char[])type.GetField("m_ChunkChars", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(p);
    Console.WriteLine($"倒数第{count}个StringBuilder内容:{new string(data)}");
    p = (StringBuilder)type.GetField("m_ChunkPrevious", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(p);
}

这里主要做的是利用Append方法添加不同的数据并将最终结果输出。考虑到内部的细节并没有对外公开,只能通过反射的操作来获取,通过遍历每一个StringBuilder的节点,反射获取内部的字符数组并将其输出。最终的结果如下。

测试结果

这里分析下具体的过程:

  1. 第一句sb = new StringBuilder()。从之前的构造函数代码内可以得知,无参构造函数会生成一个16长度的字符数组。
  2. 第二句sb.Append('1', 10)。这句话意思是向sb内添加10个1字符,因为添加的长度小于给定的默认值16,因此直接将其添加即可。
  3. 第三句sb.Append('2', 6)。在经过上面添加操作后,当前字符数组还剩6个空间,刚好够塞,因此直接将6个2字符直接塞进去。
  4. 第四句sb.Append('3', 24)。在添加字符3之前,StringBuilder内部的字符数组就已经没有空间了。为此,需要构造新的StringBuilder对象,并将当前对象内的数据传过去。对于当前对象,需要创建新的字符数组,按照之前给出的规则,当前Chunk之和(16)和Chunk长度(8000)取最小值(16),最小值(16)和输入字符串长度(24)取最大值(24)。因此,直接创建24个字符空间并存下来。此时,sb对象有一个前置节点。
  5. 第五句sb.Append('4', 15)。上一句代码只创建了长度为24的字符数组,因此,新数据依然无法再次塞入。此时,依旧需要创建新的StringBuilder节点,按照同样的规则,取当前所有Chunk之和(16+24=40)。因此,新字符数组长度为40,内部存了15个字符数据4sb对象有两个前置节点。
  6. 第六句sb.Append("hello world")。这个字符串长度为11,当前字符数组能完全放下,则直接放下。此时字符数组还空余14个空间。
  7. 第七句sb.Append("nice to meet you")。这个字符串长度为16,可以发现超过了剩余空间,首先先填充14个字符。之后多出的2个,则按照之前的规则再构造新的节点,新节点的长度为所有Chunk之和(16+24+40=80),即有80个存储空间。当前Chunk只存储最后两个字符ousb对象有3个前置节点。符合最终的输出结果。

总结

总的来说,采用定长的字符数组来保存不定长的字符串,不可能完全避免所添加的数据超出剩余空间这样的情况,重新开辟新空间并复制原始数据过于耗时。StringBuilder采用链表的形式取消了数据的复制操作,提高了字符串连接的效率。对于StringBuilder来说,大部分的操作都在尾部添加,采用逆向链表是一个不错的形式。当然StringBuilder这个类本身有很多复杂的实现,本篇只是介绍了Append方法是如何进行字符串拼接的。