浅谈C# StringBuilder内存碎片对性能的影响

StringBuilder内部是由多段char[]组成的半自动链表，因此频繁从中间修改StringBuilder，会将原本连续的内存分隔为多段，从而影响读取/遍历性能。

连续内存与不连续内存的性能差，可能高达1600倍。

背景

用StringBuilder的用户可能大都想用StringBuilder拼接html/json模板、组装动态SQL等正常操作。但在一些特殊场景中——如为某种编程语言写语言服务，或者写一个富文本编辑器时，StringBuilder依然也有用武之地，通过里面的Insert/Remove两个方法来修改。

测试方法

Talk is cheap, show me the code:

int docLength = 10000;
void Main()
{
 (from power in Enumerable.Range (1, 16)
 let mutations = (int) Math.Pow (2, power)
 select new
 {
   mutations,
   PerformanceRatio = Math.Round (GetPerformanceRatio (docLength, mutations), 1)
 }).Dump();
}

float GetPerformanceRatio (int docLength, int mutations)
{
 var sb = new StringBuilder ("".PadRight (docLength));
 var before = GetPerformance (sb);
 FragmentStringBuilder (sb, mutations);
 var after = GetPerformance (sb);
 return (float) after.Ticks / before.Ticks;
}

void FragmentStringBuilder (StringBuilder sb, int mutations)
{
 var r = new Random(42);
 for (int i = 0; i < mutations; i++)
 {
   sb.Insert (r.Next (sb.Length), 'x');
   sb.Remove (r.Next (sb.Length), 1);
 }
}

TimeSpan GetPerformance (StringBuilder sb)
{
 var sw = Stopwatch.StartNew();
 long tot = 0;
 for (int i = 0; i < sb.Length; i++)
 {
   char c = sb[i];
   tot += (int) c;
 }
 sw.Stop();
 return sw.Elapsed;
}

关于这段代码，请注意以下几点：

• 通过.PadRight(n)来直接创建长度为n的空白字符串，可以用new string(' ', n)来代替；

• new Random(42)处，我指定了一个随机因子，确保每次分隔后分隔的位置完全相同，有利于做对照组；

• 我分别对字符串进行了2^1 ~ 2^16次修改，分别比较经过这么多次修改之后的性能差异；

• 我使用sb[i]来逐一访问StringBuilder中的位置，使内存不连续性更加突显。

运行结果

可见如果在StringBuilder中间进行大量修改，其性能会急据下降，注意看32768次修改的情况下，遍历时会产生高达1630.4倍的性能差！

解决方式

如果一定要用StringBuilder，可以考虑在修改一定次数后，重新创建一个新的StringBuilder，以使得访问时获得最佳的内存连续性，即可解决此问题：

void FragmentStringBuilder (StringBuilder sb, int mutations)
{
 var r = new Random(42);
 for (int i = 0; i < mutations; i++)
 {
   sb.Insert (r.Next (sb.Length), 'x');
   sb.Remove (r.Next (sb.Length), 1);

// 重点
   const int defragmentCount = 250;
   if (i ％ defragmentCount == defragmentCount - 1)
   {
     string buf = sb.ToString();
     sb.Clear();
     sb.Append(buf);
   }
 }
}

如上，每经过250次修改，即将原StringBuilder删除，然后重新创建一个新的StringBuilder，此时运行效果如下：

可见，在几乎所有情况下，受内存不连续造成的访问性能问题，解决——同时250可能是一个相对比较合理的数字，在插入性能与查询/遍历性能中，获得平衡。

反思与总结

众所周知，由于string的不可变性，拼接大量字符串时，会浪费大量内存。但使用StringBuilder也需要了解它的结构。

StringBuilder这样做成链式的结构并非没有原因，如果考虑插入性能，做成链式接口是最优秀的。但如果考虑查询性能，链式结构就非常不利了，如果设计为非链式结构，从中间插入时，StringBuilder的内存空间可能不够，因此需要重新分配内存，这样相当于将StringBuilder降格为string，因此完全丧失了StringBuilder适合做“频繁插入”的优势。

本文说的其实是一个非常特殊的例子，现实中除了语言服务、编辑器外，很少会需要这种即要频繁插入快，也要频繁修改快的场景。如果想简单点搞，用StringBuilder会是一个有条件合适的解决方案。更适合的解决方案当然是专门的数据结构——PieceTable，微软在VSCode编辑器中，为了确保大文件编辑性能，使用了该数据结构，取得了非常不错的成果，参考链接：Text Buffer Reimplementation。

来源：https://www.cnblogs.com/sdflysha/p/20200317-memory-fragment-performance-impact-to-stringbuilder.html