亲宝软件园·资讯

展开

StringBuilder内存碎片对性能的影响

.NET骚操作 人气:2
# 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骚操作】 ![DotNet骚操作](https://img2018.cnblogs.com/blog/233608/201908/233608-20190825165420518-990227633.jpg)

加载全部内容

相关教程
猜你喜欢
用户评论