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

JerryXia 发表于 , 阅读 (671)

根据上次的评测结果,我们了解了几种字符串拼接方式的性能高低。从中可以看出,广受追捧的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原有的功能而已。如一言蔽之:<span>String有可变和不可变两个方面,从外界只能看到String不可变的一面,而可变的一面由StringBuilder暴露出来</span>。

为什么这么说呢?我们来看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对象的一切都差不多暴露在眼前,那么我们离真相也应该已经不远了。不过接下来的东西,还是留在下次评述吧。

添加新评论