查看原文
其他

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

DotNet 2021-09-23

(给DotNet加星标,提升.Net技能

转自:iskcal
cnblogs.com/iskcal/p/implementation

前言


写了一篇《.NET中的StringBuilder和TextWriter区别》


当时提了一句没有找到相关源码,于是随后有很多热心人士给出了相关的源码链接感谢大家。


这几天抽了点时间查看了下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个字符数据4。sb对象有两个前置节点。


6、第六句sb.Append("hello world")。这个字符串长度为11,当前字符数组能完全放下,则直接放下。此时字符数组还空余14个空间。


7、第七句sb.Append("nice to meet you")。这个字符串长度为16,可以发现超过了剩余空间,首先先填充14个字符。之后多出的2个,则按照之前的规则再构造新的节点,新节点的长度为所有Chunk之和(16+24+40=80),即有80个存储空间。当前Chunk只存储最后两个字符ou。sb对象有3个前置节点。符合最终的输出结果。


总结


总的来说,采用定长的字符数组来保存不定长的字符串,不可能完全避免所添加的数据超出剩余空间这样的情况,重新开辟新空间并复制原始数据过于耗时。


StringBuilder采用链表的形式取消了数据的复制操作,提高了字符串连接的效率。


对于StringBuilder来说,大部分的操作都在尾部添加,采用逆向链表是一个不错的形式。


当然StringBuilder这个类本身有很多复杂的实现,本篇只是介绍了Append方法是如何进行字符串拼接的。


- EOF -


推荐阅读  点击标题可跳转
为什么要小心使用 Task.Run52 条 SQL 语句性能优化策略,建议收藏Visual Studio 调试技巧之即时窗口的妙用  


看完本文有收获?请转发分享给更多人

推荐关注「DotNet」,提升.Net技能 

点赞和在看就是最大的支持❤️

: . Video Mini Program Like ,轻点两下取消赞 Wow ,轻点两下取消在看

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存