# StringBuilder内存碎片对性能的影响
## TL;DR:
`StringBuilder`内部是由多段`char[]`组成的**半自动链表**，因此频繁从**中间**修改`StringBuilder`，会将原本连续的内存分隔为多段，从而影响读取/遍历性能。
连续内存与不连续内存的性能差，可能高达`1600`倍。
## 背景
用`StringBuilder`的用户可能大都想用`StringBuilder`拼接`html/json`模板、组装动态`SQL`等正常操作。但在一些特殊场景中——如为某种编程语言写语言服务，或者写一个富文本编辑器时，`StringBuilder`依然也有用武之地，通过里面的`Insert`/`Remove`两个方法来修改。
## 测试方法
*Talk is cheap, show me the code*:
```csharp
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;
}
```
关于这段代码，请注意以下几点：
1. 通过`.PadRight(n)`来直接创建长度为`n`的空白字符串，可以用`new string(' ', n)`来代替；
2. `new Random(42)`处，我指定了一个随机因子，确保每次分隔后分隔的位置**完全相同**，有利于做对照组；
3. 我分别对字符串进行了`2^1 ~ 2^16`次修改，分别比较经过这么多次修改之后的性能差异；
4. 我使用`sb[i]`来逐一访问`StringBuilder`中的位置，使内存不连续性更加突显。
## 运行结果
| **mutations** | **PerformanceRatio** |
| ------------- | -------------------- |
| 2 | 1 |
| 4 | 1 |
| 8 | 1 |
| 16 | 1 |
| 32 | 1 |
| 64 | 1.1 |
| 128 | 1.2 |
| 256 | 1.8 |
| 512 | 5.2 |
| 1024 | 19.9 |
| 2048 | 81.3 |
| 4096 | 274.5 |
| 8192 | 745.8 |
| 16384 | 1578.8 |
| 32768 | 1630.4 |
| 65536 | 930.8 |
可见如果在`StringBuilder`中间进行大量修改，其性能会急据下降，注意看`32768`次修改的情况下，遍历时会产生高达`1630.4`倍的性能差！
## 解决方式
如果一定要用`StringBuilder`，可以考虑在修改一定次数后，重新创建一个新的`StringBuilder`，以使得访问时获得最佳的内存连续性，即可解决此问题：
```csharp
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`，此时运行效果如下：
| **mutations** | **PerformanceRatio** |
| ------------- | -------------------- |
| 2 | 1.2 |
| 4 | 0.7 |
| 8 | 1 |
| 16 | 1 |
| 32 | 1 |
| 64 | 1.1 |
| 128 | 1.2 |
| 256 | 1 |
| 512 | 1 |
| 1024 | 1 |
| 2048 | 1 |
| 4096 | 1.1 |
| 8192 | 1.5 |
| 16384 | 1.3 |
| 32768 | 1 |
| 65536 | 1 |
可见，在**几乎**所有情况下，受内存不连续造成的访问性能问题，解决——同时`250`**可能**是一个**相对比较**合理的数字，在插入性能与查询/遍历性能中，获得平衡。
# 反思与总结
众所周知，由于`string`的不可变性，拼接大量字符串时，会浪费大量内存。但使用`StringBuilder`也需要了解它的结构。
`StringBuilder`这样做成链式的结构并非没有原因，如果考虑插入性能，做成链式接口是**最**优秀的。但如果考虑查询性能，链式结构就非常不利了，如果设计为非链式结构，从中间插入时，`StringBuilder`的内存空间可能不够，因此需要重新分配内存，这样相当于将`StringBuilder`降格为`string`，因此完全丧失了`StringBuilder`适合做“频繁插入”的优势。
本文说的其实是一个非常特殊的例子，现实中除了语言服务、编辑器外，很少会需要这种即要频繁插入**快**，也要频繁修改**快**的场景。如果想简单点搞，用`StringBuilder`会是一个**有条件合适**的解决方案。更适合的解决方案当然是专门的数据结构——`PieceTable`，微软在`VSCode`编辑器中，为了确保大文件编辑性能，使用了该数据结构，取得了非常不错的成果，参考链接：[Text Buffer Reimplementation](https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation)。
喜欢的朋友请关注我的微信公众号：【DotNet骚操作】
