Hello World
Spiga

重谈字符串连接性能(中):细节实现

2009-12-03 10:10 by 老赵, 9100 visits

根据上次的评测结果,我们了解了几种字符串拼接方式的性能高低。从中可以看出,广受追捧的StringBuilder性能似乎并不是最好的,String.Concat方法有时候有时候更适合使用。那么为什么String.Concat方法性能那么高,StringBuilder又为什么落败,而我们又有没有什么可以改进的做法呢?为此,我们不妨动用.NET Reflector这一利器,看一下两者是怎么实现的。

String.Concat为什么这么快

String.Concat方法有多个重载,其中我们关注那个接受字符串数组作为参数的重载,它是实现的核心。代码如下:

public static string Concat(params string[] values)
{
    int totalLength = 0;

    if (values == null)
    {
        throw new ArgumentNullException("values");
    }

    string[] arrayToConcate = new string[values.Length];

    // 遍历源数组,填充拼接用的数组
    for (int i = 0; i < values.Length; i++)
    {
        string str = values[i];

        // null作为空字符串对待
        arrayToConcate[i] = (str == null) ? Empty : str;

        // 累计字符串总长度
        totalLength += arrayToConcate[i].Length;

        // 如果越界了,抛异常
        if (totalLength < 0)
        {
            throw new OutOfMemoryException();
        }
    }

    // 拼接
    return ConcatArray(arrayToConcate, totalLength);
}

由于数组中的字符串都是确定的,因此Concat方法可以事先计算出结果的长度,并交由ConcatArray方法进行拼接:

[MethodImpl(MethodImplOptions.InternalCall)]
private static extern string FastAllocateString(int length);

private static string ConcatArray(string[] values, int totalLength)
{
    // 分配目标字符串所占用的空间(即创建对象)
    string dest = FastAllocateString(totalLength);

    int destPos = 0;

    for (int i = 0; i < values.Length; i++)
    {
        // 不断将源字符串的每个元素填充至目标位置
        FillStringChecked(dest, destPos, values[i]);

        // 偏移量不断更新
        destPos += values[i].Length;
    }

    return dest;
}

在ConcatArray方法中,首先使用FastAllocateString分配一个长度为length的字符串对象——这是一个外部调用,由CLR实现。CLR在堆上会生成一个字符串对象(其实就是开辟一块内存,并填好一些数据),其中包含了各个字段,也就是说“结构”已经完备,而唯一所缺的便是字符串的内容。于是遍历源字符串数组,将它们一个一个复制(或叫做“填充”)到目标字符串的某一段位置上去,它所用的FilStringChecked方法实现如下:

private static unsafe void FillStringChecked(string dest, int destPos, string src)
{
    int length = src.Length;
    if (length > (dest.Length - destPos))
    {
        throw new IndexOutOfRangeException();
    }

    fixed (char* chDest = &dest.m_firstChar)
    {
        fixed (char* chSrc = &src.m_firstChar)
        {
            wstrcpy(chDest + destPos, chSrc, length);
        }
    }
}

这里使用了非安全代码,直接调用wstrcpy复制内存上的内容,wstrcpy方法的具体实现很“单纯”,我们可以不去关心它,而这里可以关注的是作内存数据复制的“位置”是哪里。从前一篇文章中我们知道,在一个字符串结构中,从对象地址偏移12字节的地方是m_firstChar字段,这个字段——更确切地说应该是“位置”包含了字符串的首地址,而往后则便是一个一个字符了。换句话说,从m_firstChar字段的地址开始便是字符串的内容,因此FillStringChecked方法在复制的时候,都是从m_firstChar开始的:从src.m_firstChar读取数据,而从dest.m_firstChar开始偏移destPos个字符的位置写入。

这便是String.Concat(string[])方法的全部实现,非常简单,清晰,但这也正是这个方法高效的原因所在。我们知道字符串是个不可变的对象,每次新建字符串都要开辟一块新空间。而String.Concat方法便将这个开辟新空间的代价减少到最小。因为在此之前已经确定结果的大小,因此直接创建一个“容器”即可,剩下的只是填充数据而已。既然可以不浪费任何一寸空间,也没有任何多余的操作,性能又怎会不高呢?

String.Concat还有一些重载,接受少量的对象进行拼接,这些方法都是单独实现,而没有委托给接受字符串数组的重载,这也是出于性能考虑——毕竟节省了构造字符串数组的开销。String.Concat方法和编译器联系紧密,属于使用最为频繁的操作之一,因此.NET在这里会尽可能榨干任何性能上的水分。

String即Builder

这个节标题有些唬人,不过这也是我最终得到的结果。可能这和平时了解的东西不太一样,对于一些初学的朋友可能不太适合去记住这个,反而会产生混淆。这其实也是我认为不能“一切都追究到底”,而必须“在一定抽象上看待事物”的原因。不过,现在我们只是在关注一个客观事实,希望这个事实不会对您产生误导。

我们从了解.NET之处便一直被告知,String对象是不可变的,因此我们没法修改一个String对象,只能新建一个。但是,上面的代码也告诉我们,String并非不可变的,它只是不允许外界进行修改,而.NET内部爱怎么动便可以怎么动。这句话从两个角度来理解会有不同感觉:1) 这是一句废话,因为所有东西都在内存里,只要能涂改内存里的数据,又有什么不是不可修改的呢?不过,2) 其实从代码上看,String对象其实原本就打算给人(自己人)修改,String了解StringBuilder的存在,而StringBuilder也只是利用了String原有的功能而已。如一言蔽之:String有可变和不可变两个方面,从外界只能看到String不可变的一面,而可变的一面由StringBuilder暴露出来

为什么这么说呢?我们来看StringBuilder的Append方法:

public StringBuilder Append(string value)
{
    if (value != null)
    {
        string currentValue = this.m_StringValue;

        IntPtr currentThread = Thread.InternalGetCurrentThread();

        // 如果上次修改和本次修改不是同一个线程,
        if (this.m_currentThread != currentThread)
        {
            // 则复制一份当前的字符串及“容量”,
            // 避免多个线程修改同一块内存
            currentValue = string.GetStringForStringBuilder(currentValue, currentValue.Capacity);
        }

        int length = currentValue.Length;
        // 计算目标长度
        int requiredLength = length + value.Length;

        // 如果目标长度超过当前容量
        if (this.NeedsAllocation(currentValue, requiredLength))
        {
            // 则复制一个新的字符串对象,不过拥有更大的容量
            string newString = this.GetNewString(currentValue, requiredLength);
            // 把新加的部分复制到原“字符序列”的后面
            newString.AppendInPlace(value, length);
            // 保留当前线程标识符及新的字符串对象(新容量)
            this.ReplaceString(currentThread, newString);
        }
        else // 容量足够
        {
            currentValue.AppendInPlace(value, length);
            this.ReplaceString(currentThread, currentValue);
        }
    }

    return this;
}

private bool NeedsAllocation(string currentString, int requiredLength)
{
    return (currentString.ArrayLength <= requiredLength);
}

之前我们分析了String对象的结构,发现其中有两个字段,stringLength和arrayLength,其中stringLength自然表示了字符串的长度,但字符串对象的体积确是由arrayLength决定的。换句话说,假设有一个stringLength为1,arrayLength为100的字符串对象,它的大小与stringLength为90,arrayLength为100的对象完全一样。这样看来arrayLength就好比一个“容量”,表明了这个字符串对象“可以包含”的最长字符序列。事实上从上面的代码中也可以看出,String类中的确有这么一个Capacity属性:

public class String
{
    internal int Capacity
    {
        get
        {
            return (this.m_arrayLength - 1);
        }
    }
}

可见,它的值便是arrayLength——抛开最后一位填上“\0”,也因此上次我们发现,对于最“满当”的字符串,arrayLength也比stringLength多1。当然,在平时来说,我们只能创建容量与内容相同的字符串,如果真要创建一个“空荡荡”的容器,则需要调用String类的静态方法GetStringForStringBuilder——虽然这的确没有什么用途。GetStringForStringBuilder的实现我们也可以猜出,便是让CLR分别一个一定容量的字符串对象,然后从m_firstChar的地址进行内存复制而已。

在我们不断地Append之后,最后便要调用StringBuilder的ToString方法了:

public override string ToString()
{
    string currentValue = this.m_currentValue;

    if (this.m_currentThread != Thread.InternalGetCurrentThread())
    {
        return string.InternalCopy(currentValue);
    }

    // 如果这个字符串对象“太空”的话
    if ((2 * currentValue.Length) < currentValue.ArrayLength)
    {
        // 则构造一个“满当”地对象
        return string.InternalCopy(currentValue);
    }

    // 将字符序列最后放一个\0
    currentValue.ClearPostNullChar();

    // 既然容器已经“暴露”,则设制“当前线程”的标识为Zero,
    // 这意味着下次操作会生成新字符串对象(即新的容器)
    this.m_currentThread = IntPtr.Zero;

    // 如果“还不算太空”,则返回当前对象
    return currentValue;
}

StringBuilder的ToString方法比较有意思,它会判断到底是“构造一个新对象”还是就“直接返回当前容器”给你。如果直接返回当前容器,则可能会浪费较多内存,而如果构造一个新对象,则又会损耗性能。让StringBuilder做出决定的便是容器内部的字符序列占“最大容积”的比例,如果超过一半,则表明“还不算太空”,便选择“时间”,直接返回容器;否则,StringBuilder会认为还是选择“空间”较为合算,便构造一个新对象并返回,至于当前的容器便会和StringBuilder一道被GC回收了。

同时我们可以看到,如果返回了新对象,则当前容器还可以继续在Append时使用,否则Append方法便会因为m_currentValue为Zero而创建新的容器。不过,从ToString的实现中也可以看出,多次调用ToString方法一定返回新建的对象。这是一种浪费,虽然在一般情况下这不会成为问题,但如果写出这样的代码,便是无端在浪费性能了:

var sb = new StringBuilder();
// ...

for (var i = 0; i < sb.ToString().Length; i++)
{ 
    // ...
}

喔,很容易明白,不是吗?

似乎关于String和StringBuilder对象的一切都差不多暴露在眼前,那么我们离真相也应该已经不远了。不过接下来的东西,还是留在下次评述吧。

相关文章

Creative Commons License

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

Add your comment

40 条回复

  1. 乌卡卡
    *.*.*.*
    链接

    乌卡卡 2009-12-03 10:12:00

    沙发了,再看吧

  2. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-12-03 10:33:00

    陪老赵一起耍性能
    呵呵
    不过照片上貌似不老呀

  3. 木野狐(Neil Chen)
    *.*.*.*
    链接

    木野狐(Neil Chen) 2009-12-03 10:37:00

    继续关注 :)

  4. 亚历山大同志
    *.*.*.*
    链接

    亚历山大同志 2009-12-03 10:43:00

    老赵是深挖洞广积粮的典心,string这个坑挖这么大,能存不少东西了

  5. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-12-03 10:45:00

    String早就挖得差不多了,,,Array和GC才是大坑。。。。

  6. 老赵
    admin
    链接

    老赵 2009-12-03 10:47:00

    @Ivony...
    CLR是个奇特的东西,好多东西很难挖,比如GC,因为看不到代码……
    话说脑袋昨天说去看GC的代码,结果如何?

  7. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-12-03 10:50:00

    Jeffrey Zhao:
    @Ivony...
    CLR是个奇特的东西,好多东西很难挖,比如GC,因为看不到代码……
    话说脑袋昨天说去看GC的代码,结果如何?


    同问

  8. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-12-03 10:58:00

    我只是想去看看那个card table和write barrier,没有去看GC……

  9. 老赵
    admin
    链接

    老赵 2009-12-03 11:03:00

    @装配脑袋
    其实脑袋只要说看得到多少,说不定RFX就会口水四溢去微软了……

  10. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-12-03 11:05:00

    有时候黑箱研究更有挑战性的说。。看代码,又不是能够build出来的代码,不能够跟进去看的那种很难说有多少吸引力。呵呵

  11. 老赵
    admin
    链接

    老赵 2009-12-03 11:07:00

    @装配脑袋
    但是代码至少给出了探索的方向,好比没有引路人但有个地图还是好的……

  12. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-12-03 11:08:00

    Jeffrey Zhao:
    @装配脑袋
    其实脑袋只要说看得到多少,说不定RFX就会口水四溢去微软了……


    我一直都在口水四溢只是没能去微软而已……要是有人帮忙推荐的话就好了 TvT

  13. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-12-03 11:16:00

    装配脑袋:有时候黑箱研究更有挑战性的说。。看代码,又不是能够build出来的代码,不能够跟进去看的那种很难说有多少吸引力。呵呵




    嗯,,,朦胧美。。。。

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

    韦恩卑鄙 alias:v-zhewg 2009-12-03 11:53:00

    @老农
    一般不看 要联系可以用右下的msn

  15. 老赵
    admin
    链接

    老赵 2009-12-03 12:19:00

    RednaxelaFX:
    我一直都在口水四溢只是没能去微软而已……要是有人帮忙推荐的话就好了 TvT


    其实你的水平,想去的话直接应聘啊,要人推荐做啥……我也想你去微软,这样才好玩啊。

  16. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-12-03 13:49:00

    Jeffrey Zhao:

    RednaxelaFX:
    我一直都在口水四溢只是没能去微软而已……要是有人帮忙推荐的话就好了 TvT


    其实你的水平,想去的话直接应聘啊,要人推荐做啥……我也想你去微软,这样才好玩啊。




    介个,其实微软太大了,直接应聘很难找到合适的部门吧。。。。

    要进微软从外包走貌似还是很简单的,,,只不过。。。。

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

    韦恩卑鄙 alias:v-zhewg 2009-12-03 13:54:00

    只不过转正很难 最近名额太少了吧

  18. 老赵
    admin
    链接

    老赵 2009-12-03 14:04:00

    @Ivony...
    只不过RFX随便去一个团队估计也浪费了,也产生不到效果……

  19. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-12-03 14:28:00

    大家发现没,貌似.NET Framework开放源代码的力度变大了,现在更多源代码可以下载了。

    正在下载System.Web

  20. 钧梓昊逑
    *.*.*.*
    链接

    钧梓昊逑 2009-12-03 15:17:00

    Ivony...:
    大家发现没,貌似.NET Framework开放源代码的力度变大了,现在更多源代码可以下载了。

    正在下载System.Web


    貌似很久以前就可以下载了

  21. 路过 ........[未注册用户]
    *.*.*.*
    链接

    路过 ........[未注册用户] 2009-12-03 16:29:00

    是“重(zhong)” 还是"重(chong)" 啊

  22. pixysoft[未注册用户]
    *.*.*.*
    链接

    pixysoft[未注册用户] 2009-12-03 17:08:00

    没看完文章。不过

    我发现stringbuilder 好像也用了string.concat.

    在一次异常中,exception stack出现了。是先发生strign.concat异常,然后再在stringbuilder.

  23. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-12-03 17:22:00

    pixysoft:
    没看完文章。不过

    我发现stringbuilder 好像也用了string.concat.

    在一次异常中,exception stack出现了。是先发生strign.concat异常,然后再在stringbuilder.


    这个可能要好好检查一下当时的stack trace……用Reflector看StringBuilder在managed的一侧是没有调用过String.Concat()方法的。而native的一侧也只有StringBuilder.Replace()而已,没调用String.Concat()。

  24. 老赵
    admin
    链接

    老赵 2009-12-03 17:58:00

    @RednaxelaFX
    我猜会不会是某些特别的重载先作了一些计算,然后再调用Append(string)这个重载。

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

    小城故事 2009-12-03 18:11:00

    这些绝对是真正的.Net程序员应该了解的,老赵完全可以就这个话题开一个WebCast讲座

  26. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-12-03 18:40:00

    @Jeffrey Zhao
    败了……JE貌似不让外连图了。换这个地址:
    http://rednaxelafx.javaeye.com/picture/50531

  27. 老赵
    admin
    链接

    老赵 2009-12-03 18:56:00

    @RednaxelaFX
    嗯?这是啥意思呀?

  28. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-12-03 19:06:00

    Jeffrey Zhao:
    @RednaxelaFX
    嗯?这是啥意思呀?




    那是Append方法的依赖树,String.Concat不在这棵树上,也就是说即使没有String.Concat,也不会影响StringBuilder.Append方法的执行。

    当然,这是只考虑IL的前提下。

  29. 老赵
    admin
    链接

    老赵 2009-12-03 19:12:00

    @Ivony...
    但这只是Append(string)方法亚。
    我刚才是说,会不会是Append的其它重载,例如Append(bool),先用了String.Concat,然后最后调用了Append(string)……

  30. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-12-03 20:33:00

    @Jeffrey Zhao
    String.Concat()是managed的方法,基本上BCL里的方法进到native一侧之后不是callback都不会调回到managed的一侧……
    那看这个,StringBuilder.Append(Int32)的:
    http://rednaxelafx.javaeye.com/picture/50535
    只展开了依赖树上返回类型为String或者StringBuilder的方法。这棵树上其它方法也没找到String.Concat()……

    还是想看看pixysoft当时的stack trace,肯定能带来点启发的~

  31. 老赵
    admin
    链接

    老赵 2009-12-03 20:50:00

    @RednaxelaFX
    我想到一种可能性,回家写文章,hmmm……

  32. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-12-03 20:50:00

    RednaxelaFX:
    @Jeffrey Zhao
    String.Concat()是managed的方法,基本上BCL里的方法进到native一侧之后不是callback都不会调回到managed的一侧……
    那看这个,StringBuilder.Append(Int32)的:
    http://rednaxelafx.javaeye.com/picture/50535
    只展开了依赖树上返回类型为String或者StringBuilder的方法。这棵树上其它方法也没找到String.Concat()……

    还是想看看pixysoft当时的stack trace,肯定能带来点启发的~




    这个现象应该还是很简单能重现的。
    举一个简单的例子,比如说有个类型的ToString里面调用了String.Concat,用这个类型调用StringBuilder.Append( object )方法就可以了。。。。。

    当然我不知道pixysoft他所遇到的情况是怎样,只是说要造成这种现象还是挺简单。

  33. 老赵
    admin
    链接

    老赵 2009-12-03 20:54:00

    @Ivony...
    好吧,被抢了……但是我还要写……
    其实就是调用StringBuilder.Append(object),然后在这个object的ToString()里连接两个非string对象,然后编译器会用String.Concat(object,object)进行连接,如果此时其中某个object的ToString再抛出异常,这样call stack里便是Append里的Concat里异常了……

  34. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-12-03 21:05:00

    @Jeffrey Zhao
    @Ivony...
    嗯,你们说得没错。ToString()是个大洞……

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

    tianxd 2009-12-19 23:21:00

    下还没出来?

  36. 菜鸟毛
    *.*.*.*
    链接

    菜鸟毛 2009-12-22 17:33:00

    各位大哥,看您们谈了这么多关于性能的问题,下次希望能看到数据到对像的性能优化.

    正因为这方面文章不是太多,而很多新人,包括我,之前也是追求对象的性能,例如,string与StringBuilder,而忽视了数据到对象之个过程的性能.走了很多弯路,也吃了不少大亏啊.

    老赵,指点一下吧.

  37. 老赵
    admin
    链接

    老赵 2009-12-22 17:36:00

    @菜鸟毛
    没听懂,什么叫作数据到对象?还有,一定要我做才行吗?自己为什么不尝试一下呢?

  38. 菜鸟毛
    *.*.*.*
    链接

    菜鸟毛 2009-12-23 17:31:00

    不是懒,也不是没做尝试,ORM,数据映射都做过,甚至于自己去写了一层从数据到对象的数据层.作为菜鸟,总是希望得到权威的指引.

    我做了很多的项目,回头看看,依然觉得不够完美,甚至觉得以前的都垃圾.唉!

  39. 老赵
    admin
    链接

    老赵 2009-12-23 17:49:00

    @菜鸟毛
    那就把你的尝试结果写篇文章出来,大家一起讨论一下。

  40. 菜鸟毛
    *.*.*.*
    链接

    菜鸟毛 2009-12-24 17:01:00

    老赵,按您的吩咐,我已经写了第一篇关于数据到对象的性能尝试的,链接在这里.http://www.cnblogs.com/CoreCaiNiao/archive/2009/12/24/1631514.html,各位达人请指教,不对的地方,请批评.

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我