Hello World
Spiga

重谈字符串连接性能(下):分析优化

2009-12-23 14:03 by 老赵, 7989 visits

经过之间的性能比较,我们得知StringBuilder的性能并非时时最优,再经过实现分析,我们大致了解了StringBuilder的实现方式。虽然在此之前,大家也基本已经了解StringBuilder的实现原理,也有不少朋友指出了它性能缺陷的原因。不过“严谨”起见,寻找性能问题的方式应该是进行Profiling,然后找出性能关键再进行优化——而不是纯粹进行“阅读”这种静态分析方式。

那么,假设我们还是使用原来的方式使用StringBuilder连接字符串:

static void Main()
{
    for (int i = 0; i < 100 * 100 * 20; i++) StringBuilder(1024);
}

private static readonly string STR = "0123456789";

private static string StringBuilder(int count)
{
    var builder = new StringBuilder();
    for (int i = 0; i < count; i++)
        builder.Append(STR);
    return builder.ToString();
}

我们对这段代码进行Profiling,便可以得到这样的结果:

从结果上可以看出,几乎所有时间都是消耗在Append操作上的(这是废话)。而在Append方法中,AppendInPlace和GetNewString方法都占用了较多的比例。从上次的代码分析中我们知道,AppendInPlace方法是将新的字符串复制到原字符序列(也就是那个“容器”)的后面,而GetNewString的作用便是创建一个新的,容量加倍字符串(容器)——它的主要消耗都在GetStringForStringBuilder方法上。

AppendInPlace的作用是复制字符串,消耗无法节省下来。但是,我们可以尽可能避免GetNewString的开销,只要减少“创建新容器”的次数即可。这意味着我们可以在一开始指定容量更大的StringBuilder。于是乎,我们尝试将StringBuilder的使用改写为如下形式:

private static string NewStringBuilder(int count)
{
    var builder = new StringBuilder(count * STR.Length);
    for (int i = 0; i < count; i++)
        builder.Append(STR);
    return builder.ToString();
}

再次进行Profiling,结果如下:

由于我们一下子提供了足够的容量,因此在NewStringBuilder方法中一次“扩容”都不需要,因此也就不会调用GetNewString方法了。从上图中可以看出,此时AppendInPlace方法占用的比例增加了。与此对应的是StringBuilder的构造函数开销也增大了——因为需要一下子开辟较多的空间。由于总时间消耗地少,因此采样总数也比之前有所减少——这些结果都符合我们的推测。

于是我们将NewStringBuilder和之前的StringConcat以及StringListBuilder进行比较。公平起见,我也相应提高StringListBuilder中List<string>的容量,避免“扩容操作”:

class Program
{
    static void Main()
    {
        CodeTimer.Initialize();

        for (int i = 2; i <= 4096; i *= 2)
        {
            CodeTimer.Time(
                String.Format("StringBuilder ({0})", i),
                10000,
                () => NewStringBuilder(i));

            CodeTimer.Time(
                String.Format("String.Concat ({0})", i),
                10000,
                () => StringConcat(i));

            CodeTimer.Time(
                String.Format("StringListBuilder ({0})", i),
                10000,
                () => StringListBuilder(i));
        }
    }

    private static readonly string STR = "0123456789";

    private static string NewStringBuilder(int count)
    {
        var builder = new StringBuilder(count * STR.Length);
        for (int i = 0; i < count; i++)
            builder.Append(STR);
        return builder.ToString();
    }

    private static string StringConcat(int count)
    {
        var array = new string[count];
        for (int i = 0; i < count; i++) array[i] = STR;
        return String.Concat(array);
    }

    private static string StringListBuilder(int count)
    {
        var builder = new StringListBuilder(count);
        for (int i = 0; i < count; i++) builder.Append(STR);
        return builder.ToString();
    }
}

public class StringListBuilder
{
    private List<string> m_list;

    public StringListBuilder(int capacity)
    {
        this.m_list = new List<string>(capacity);
    }

    public StringListBuilder Append(string s)
    {
        this.m_list.Add(s);
        return this;
    }

    public string ToString()
    {
        return String.Concat(this.m_list.ToArray());
    }
}

结果如下:

绘制成图表:

终于,StringBuilder翻身了。由于避免了不断扩容,不断复制的过程,因此StringBuilder的性能已经成为三者中性能最高的作法。事实上,String.Concat高性能的原因,也正是事先知道了目标字符串的长度,实现了最高效的构造方法。而StringListBuilder,它比String.Concat需要进行更多List<string>和数组方面的维护,因此性能略低一些。

那么,经过了这三篇文章的比较和分析之后,我们是否可以知道哪种字符串连接方式性能最高呢?自然这需要根据情况而定:

  • StringBuilder:如果能够确定目标字符串的最终长度,则可以使用StringBuilder。如果不能确定的话,也可以在一开始指定更大的容量,减少扩容的次数。
  • String.Concat:如果不能确定最终长度,但是能够确定字符串的个数(如这个场景),可以将它们放在一个数组中,并调用String.Concat进行连接。
  • StringListBuilder:折衷方案,与String.Concat相比其优势在于无需确定字符串个数,与StringBuilder相比其优势在于“扩容”操作只需复制一些引用即可。

我的“重谈”之旅到此就告一段落了,您是否觉得哪里还意犹未尽呢?

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

44 条回复

  1. 老赵
    admin
    链接

    老赵 2009-12-23 14:19:00

    看不见图片和表格的兄弟可以看这里:
    http://cid-fba4447598b1d752.skydrive.live.com/self.aspx/Public/string-concat-perf-3.zip
    不过最好还是能看到吧。

  2. Jeff Wong
    *.*.*.*
    链接

    Jeff Wong 2009-12-23 14:21:00

    顶了再看

  3. 熊呜呜
    *.*.*.*
    链接

    熊呜呜 2009-12-23 14:23:00

    通常很少碰到需要如此大规模字符串连接的情况

    只连接5,6次哪个更好一点?

  4. 老赵
    admin
    链接

    老赵 2009-12-23 14:24:00

    @熊呜呜
    把这3篇完整地看一下吧。

  5. 疯子阿飞
    *.*.*.*
    链接

    疯子阿飞 2009-12-23 14:37:00

    老赵兄你的个人邮箱是什么,有些问题想私下向你讨教,QQ或者msn也行。

  6. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-12-23 14:44:00

    这个不错 不过性能要求要是到了这份上 不如交给native code去做了

  7. 老赵
    admin
    链接

    老赵 2009-12-23 14:46:00

    @winter-cn
    我觉得还好,现在这些倒都不过分,没有拿可维护性或其他什么东西来换,属于知道该怎么做,然后这么去做就行,呵呵。

  8. jolboy
    *.*.*.*
    链接

    jolboy 2009-12-23 15:54:00

    很精辟~呵呵,了解了不少!收藏收藏

  9. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-12-23 16:12:00

    Jeffrey Zhao:
    @winter-cn
    我觉得还好,现在这些倒都不过分,没有拿可维护性或其他什么东西来换,属于知道该怎么做,然后这么去做就行,呵呵。


    嗯对 这属于知道比不知道要好的知识
    我的意思是 如果性能要求如此苛刻 换成native code
    大概还能快一点

  10. 熊呜呜
    *.*.*.*
    链接

    熊呜呜 2009-12-23 16:18:00

    Jeffrey Zhao:
    @熊呜呜
    把这3篇完整地看一下吧。


    不好意思,今天才看到你有写关于这个的文章。。:)

  11. DiggingDeeply
    *.*.*.*
    链接

    DiggingDeeply 2009-12-23 16:22:00

    sb是预先分配,直道不够capacity的时候才申请新空间,然后拷贝;
    string是总是分配新空间,再拷贝。
    如果sb无法避免每次FastNewString的时候,不见得sb一定会比string性能好。

    文章看的比较匆忙,不知道我的评论对上了题目了吗。
    错了勿怪

  12. 飞笑
    *.*.*.*
    链接

    飞笑 2009-12-23 17:08:00

    够精彩,够过瘾……

  13. 飞笑
    *.*.*.*
    链接

    飞笑 2009-12-23 17:11:00

    winter-cn:

    Jeffrey Zhao:
    @winter-cn
    我觉得还好,现在这些倒都不过分,没有拿可维护性或其他什么东西来换,属于知道该怎么做,然后这么去做就行,呵呵。


    嗯对 这属于知道比不知道要好的知识
    我的意思是 如果性能要求如此苛刻 换成native code
    大概还能快一点



    不一定非要系统对性能要求高的时候才用啊,了解了这些,一些普通的应用都有了可靠的依据,再也不用每次花时间考虑用什么了,也不用浑浑噩噩的随意的单纯使用其中一种了。重点是有了个依据。

  14. 飞笑
    *.*.*.*
    链接

    飞笑 2009-12-23 17:12:00

    DiggingDeeply:
    sb是预先分配,直道不够capacity的时候才申请新空间,然后拷贝;
    string是总是分配新空间,再拷贝。
    如果sb无法避免每次FastNewString的时候,不见得sb一定会比string性能好。

    文章看的比较匆忙,不知道我的评论对上了题目了吗。
    错了勿怪



    跳过前两篇,只看这一篇,你就算白看了。

  15. Nana's Lich
    *.*.*.*
    链接

    Nana's Lich 2009-12-23 18:06:00

    @winter-cn
    你幽默了

  16. 小城故事
    *.*.*.*
    链接

    小城故事 2009-12-23 18:06:00

    初始化stringBuilder时指定个容量不就行了

  17. 迷失的code
    *.*.*.*
    链接

    迷失的code 2009-12-23 18:09:00

    弱弱的问句:我怎么在VS中找不到Profiler?是不是team版才有?

  18. 深山老林
    *.*.*.*
    链接

    深山老林 2009-12-23 20:20:00

    意犹未尽,期待老赵的更多文章。

  19. 老赵
    admin
    链接

    老赵 2009-12-23 20:58:00

    @迷失的code
    可能是吧

  20. IT Person
    *.*.*.*
    链接

    IT Person 2009-12-23 23:23:00

    老赵设计试验场景并根据试验归纳结果的能力真得很强,很是佩服,我有时的确也对这些性能方面的内容比较感兴趣,但是有时的确不能设计出好的实验方法来验证一些自己的推断,这就是差距阿!

  21. jeffery0101
    *.*.*.*
    链接

    jeffery0101 2009-12-24 10:43:00

    其实我还是有几个不明白的
    1. @“”和+=,那个好?
    2. StringBuilder.AppendFormat和StringBuilder.Append,哪个好?

  22. 老赵
    admin
    链接

    老赵 2009-12-24 10:45:00

    @jeffery0101
    我这几篇文章,从性能评测,到代码分析,到profiling什么都做过了——还是做不到自己研究一下吗?

  23. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2009-12-24 13:34:00

    @jeffery0101
    @“”和+=,那个好?
    这个还是要稍微明确下 如果你连接的都是常量 那么 +=会被编译器直接优化成 @"" 等价的IL形式
    ----------------

    看错了 - - 你问得不是+而是 +=?

  24. 老赵
    admin
    链接

    老赵 2009-12-24 13:39:00

    @韦恩卑鄙 alias:v-zhewg
    @和+=该怎么比较阿……

  25. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2009-12-24 13:49:00

    Jeffrey Zhao:
    @韦恩卑鄙 alias:v-zhewg
    @和+=该怎么比较阿……



    你的疑问证实了我的粗心 他怎么问得是 += ?


    我的回答针对的是

    string sql=@"select *
    from table1
    ";
    





    string sql  ="select * " +
    "from table1";
    
    


    哪个更高效哎



  26. 老赵
    admin
    链接

    老赵 2009-12-24 13:53:00

    @韦恩卑鄙 alias:v-zhewg
    哦……@很神奇,可以保留换行。

  27. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2009-12-24 13:58:00

    jeffery0101:
    其实我还是有几个不明白的
    1. @“”和+=,那个好?
    2. StringBuilder.AppendFormat和StringBuilder.Append,哪个好?




     static void Main(string[] args)
            {
                string a = @"1
    2
    3
    4
    5
    ";
                string b = "1\r\n"
                  + "2\r\n"
                  + "3\r\n"
                  + "4\r\n"
                  + "5\r\n";
    
                string c = "1\r\n";
                 c += "2\r\n";
                 c += "3\r\n";
                 c += "4\r\n";
                 c += "5\r\n";
    
                 Console.WriteLine(a);
                 Console.WriteLine(b);
                 Console.WriteLine(c);
            }
    



    编译后的结果是

    private static void Main(string[] args)
    {
        string a = "1\r\n2\r\n3\r\n4\r\n5\r\n";
        string b = "1\r\n2\r\n3\r\n4\r\n5\r\n";
        string c = "1\r\n";
        c = (c + "2\r\n" + "3\r\n") + "4\r\n" + "5\r\n";
        Console.WriteLine(a);
        Console.WriteLine(b);
        Console.WriteLine(c);
    }
    
     
    
    
    



    ---------

    StringBuilder.AppendFormat
    和文中提到的


    String.Concat:如果不能确定最终长度,但是能够确定字符串的个数(如这个场景),可以将它们放在一个数组中,并调用String.Concat进行连接。


    本质是一样的
    哪个好 也同样可以用统一的原则判断

  28. tianxd
    *.*.*.*
    链接

    tianxd 2009-12-26 23:32:00

    StringListBuilder:折衷方案,与String.Concat相比其优势在于无需确定字符串个数,与StringBuilder相比其优势在于“扩容”操作只需复制一些引用即可。

    to 老赵

    StringListBuilder用的是List<String>,而它内部用的是string[]数组,数组扩容难道只是复制一些应用(引用,写错了),而不需要Array.Copy操作?

  29. 老赵
    admin
    链接

    老赵 2009-12-26 23:37:00

    @tianxd
    没听懂你的意思,不过StringBuilder的实现也分析过了,你应该可以自己比较StringBuidler和StringListBuilder。

  30. tianxd
    *.*.*.*
    链接

    tianxd 2009-12-26 23:56:00

    StringConcat用的是String[],而StringListBuilder用的是List<String>,除此之外没其他区别,StringConcat比StringListBuilder性能好说明在字符串大小固定的情况下数组的效率还是比List<T>效率要好的。

  31. tianxd
    *.*.*.*
    链接

    tianxd 2009-12-26 23:59:00

    @Jeffrey Zhao
    List<T>内部用的是数组T[],当List要扩容时必然要导致内部的数组重新分配并且将原来的内容拷贝到新的数组~~我想应该是这样的吧

  32. 老赵
    admin
    链接

    老赵 2009-12-27 00:02:00

    @tianxd
    String.Concat和StringListBuilder的性能差距,和字符串大小有关吗?

  33. tianxd
    *.*.*.*
    链接

    tianxd 2009-12-27 00:09:00

    Jeffrey Zhao:
    @tianxd
    String.Concat和StringListBuilder的性能差距,和字符串大小有关吗?


    没有,但是和String.Concat使用的string[]和StringListBuilder使用的List<String>有关系

    难道我没有表达清楚?

  34. 老赵
    admin
    链接

    老赵 2009-12-27 00:27:00

    @tianxd
    嗯,那么你理解的没错

  35. tianxd
    *.*.*.*
    链接

    tianxd 2009-12-27 17:39:00

    其实我是想问你为啥StringListBuilder“扩容”操作只需复制一些引用即可。按照我的理解也应该有数组Copy操作的

    还有,看你的文章真过瘾,你不断激发思考

  36. 老赵
    admin
    链接

    老赵 2009-12-27 17:41:00

    @tianxd
    数组Copy不就是在复制引用吗?与此相对的,StringBuilder复制的就是大段大段的字符了。

  37. tianxd
    *.*.*.*
    链接

    tianxd 2009-12-31 13:45:00

    @Jeffrey Zhao

    Jeffrey Zhao:
    @tianxd
    数组Copy不就是在复制引用吗?与此相对的,StringBuilder复制的就是大段大段的字符了。



    如果值类型数组复制就不是复制引用了,不过string数组应该是复制引用

  38. Jonas Yans
    124.129.183.*
    链接

    Jonas Yans 2010-06-12 00:45:30

    看你的blog学到很多,不过这个问题我觉得你忽略了需要考虑的一点。 类库升级带来的性能提升,4.0的StringBuilder重写了,有兴趣分别Profiling一下,呵呵。 希望你能坚持一直博ing,期待你的好文章。(世界杯比赛间隙)

  39. 老赵
    admin
    链接

    老赵 2010-06-12 09:32:42

    @Jonas Yans

    你有Profiling的结果嘛?目前我是没想到StringBuilder如何可以改造的比Concat快了,业务不同决定的。

  40. Jonas Yans
    60.210.19.*
    链接

    Jonas Yans 2010-06-12 22:13:30

    jonas.yans@gmail.com给我发个mail,我把profiling的文件发给你

    PS:今天白天在公司跑的和家里的结果不一样。

  41. 老赵
    admin
    链接

    老赵 2010-06-12 22:49:47

    @Jonas Yans

    写篇文章记录一下测试结果和原因分析吧。

  42. Gabriel Zhang
    182.148.62.*
    链接

    Gabriel Zhang 2012-11-14 23:07:11

    看完3篇,老赵对技术的严谨着实让我佩服,努力的向你学习。

  43. 链接

    灰机_不会飞 2013-08-12 09:10:25

    赵叔叔的博文为何我总看不到最后几张图呢,访问被限制?有时候又都看得到.

  44. tgzhao
    124.73.20.*
    链接

    tgzhao 2013-09-04 22:08:50

    很详细,看了很过瘾

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我