Hello World
Spiga

数组排序方法的性能比较(1):注意事项及试验

2010-01-21 00:11 by 老赵, 8131 visits

昨天有朋友写了一篇文章,其中比较了List<T>的Sort方法与LINQ中排序方法的性能,而最终得到的结果是“LINQ排序方法性能高于List<T>.Sort方法”。这个结果不禁让我很疑惑。因为List<T>.Sort方法是改变容器内部元素的顺序,而LINQ排序后得到的是一个新的序列。假如两个排序方法的算法完全一致,LINQ排序也比对方多出元素复制的开销,为什么性能反而会高?如果LINQ排序的算法/实现更为优秀,那为什么.NET Fx不将List<T>.Sort也一并优化一下呢?于是今天我也对这个问题进行了简单的试验。

注意事项

在后面的评论中有人说,List<T>.Sort是“内部排序”,而LINQ排序是“外部排序”。但是根据外部排序的定义,这个说法是不正确的。“外部排序”是指在排序目标规模太大,导致主存相对太小(如内存)而不够放,不得不利用外部存储(如硬盘)做一些“过渡”的排序方式。因此,LINQ排序虽然生成了新的序列,但还是内部排序。事实上,从定义中我们也可以很容易推断出,如果数据规模相同,外部排序的性能一般总是比内部排序要差——不过事实上我们不太好做这样的比较,因为如果是能够进行内部排序的情况下,谁会利用麻烦的外部排序呢?

那篇文章中得到的结果是不对的,那么问题究竟出在什么地方呢?在我看来,问题主要出在以下两点。

首先,原文作者使用了ASP.NET作为测试环境。值得注意的是,ASP.NET执行.NET代码的时候,使用的是IIS进程中托管的CLR,它的配置和直接运行.NET应用程序时不同(不同的CLR托管方式配置很可能不一样——例如SQL Server里托管的CLR)。例如,ASP.NET中每个线程的调用栈为250K,而直接运行.NET应用程序时这个大小为1M。根据我的经验(也就是说我无法确切地“证明”这个说法),在ASP.NET中执行此类性能测试得到的结果可能很不稳定。因此,一般我建议使用一个最普通的Console应用程序来进行性能测试。

其次,也是更重要的原因,便是原作者只测试了一次排序的性能。这是性能测试中的大忌讳,因为这么做的话误差实在太大。例如,会不会在进行某一个方法的测试时,忽然系统起了一个后台进程进行维护,动用了一部分CPU和内存资源,从而导致测试消耗的时间很冤枉地增加。而且,.NET程序是有一个“预热”过程的,这导致代码在第一次执行时需要有一个生成本机代码的过程(俗称“预热”)。这个过程和代码的执行效率是无关的,因为它无论如何只会产生一次消耗,而代码是会被执行无数次的。因此,在进行测试的时候,一定要将测试目标反复执行N次,至少要让执行耗时到达“秒”级别,这样的结果才有一定参考价值。如果执行时间太少的话测试也可能不准确——要知道“计时器”也是有开销,也是有误差的,我们要得到尽量准确的结果。

最后,我强烈建议使用CodeTimer进行计时,因为在它的Initialize方法中会将当前进程及线程的优先级设置到最高,以此减少其他无关因素所造成的干扰。如果可以的话,其实也应该尽量关闭系统中其他应用程序或服务,并且最好可以断开网络(也是一个道理)。当然Release编译也是一定需要的。而且,如果您一定需要使用ASP.NET进行性能测试的话,也千万记得要在web.config中将<compilation />节点的debug属性设为false——考虑到原作者忽略了之前犯了很明显的忌讳,我强烈怀疑这点也没有满足。:)

因此,我认为那篇文章中的测试结果是不准确的,参考价值很低。

重新测试

既然如此,我们来重新进行一次试验吧。不过我现在来比较的是Array.Sort<T>方法与LINQ排序的性能。这么做的主要原因是,由于我们要执行多次排序操作,因此每次都应该使用乱序的序列。但是,每次生成新的序列也会带来开销,如果使用List<T>的话,填充元素的开销会很大,但如果是普通数组的话,就可以用性能很高的Array.Copy方法了:

static T[] CloneArray<T>(T[] source)
{
    var dest = new T[source.Length];
    Array.Copy(source, dest, source.Length);
    return dest;
}

从试验结果上看,数组的复制操作应该并没有造成显著影响。还有便是,经过阅读List<T>.Sort方法的代码,我们可以发现它只是将实现简单地委托给Array.Sort<T>方法,因此我们可以认为它们的性能完全一致。

Array.Sort<T>方法其实有两“类”重载,一类是使用IComparer<T>对象进行比较,而另一类则使用了Comparison<T>这个委托对象进行比较。为此,我们构造一个Int32Comparer类来实现IComparer<int>接口:

private class Int32Comparer : IComparer<int>
{
    #region IComparer<int> Members

    public int Compare(int x, int y)
    {
        return x - y;
    }

    #endregion
}

于是,两“类”重载的测试方法分别为:

static void SortWithCustomComparer(int[] array)
{
    Array.Sort(array, new Int32Comparer());
}

static void SortWithDelegate(int[] array)
{
    Array.Sort(array, (x, y) => x - y);
}

但是,我在这里还是再补充一个排序“方法”(原因以后再谈)。因为int类型是框架知道该如何比较的类型,因此我们其实也可以这么写:

static void SortWithDefaultComparer(int[] array)
{
    Array.Sort(array, Comparer<int>.Default);
}

最后,参加活动的自然还有LINQ排序:

static void SortWithLinq(int[] array)
{
    var sorted =
        (from i in array
         orderby i
         select i).ToList();
}

这里我使用的是ToList方法而不是ToArray方法来生成新序列,这是因为ToList的方法性能更高一些,我还是想尽可能将关注点放在“排序”而不是其他方面。

比较代码如下:

static void Main(string[] args)
{
    var random = new Random(DateTime.Now.Millisecond);
    var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray();

    CodeTimer.Initialize();

    CodeTimer.Time("SortWithDefaultComparer", 100,
        () => SortWithDefaultComparer(CloneArray(array)));

    CodeTimer.Time("SortWithCustomComparer", 100,
        () => SortWithCustomComparer(CloneArray(array)));

    CodeTimer.Time("SortWithDelegate", 100,
        () => SortWithDelegate(CloneArray(array)));

    CodeTimer.Time("SortWithLinq", 100,
        () => SortWithLinq(CloneArray(array)));

    Console.ReadLine();
}

首先,我们生成一个拥有50万个随机元素的数组,以此进行排序方法的性能比较。每次比较的时候我们都使用CloneArray方法来生成一个新的数组。

试验结果

试验结果如下:

SortWithDefaultComparer
        Time Elapsed:   7,662ms
        Gen 0:          49
        Gen 1:          49
        Gen 2:          49

SortWithCustomComparer
        Time Elapsed:   13,847ms
        Gen 0:          49
        Gen 1:          49
        Gen 2:          49

SortWithDelegate
        Time Elapsed:   19,625ms
        Gen 0:          49
        Gen 1:          49
        Gen 2:          49

SortWithLinq
        Time Elapsed:   31,785ms
        Gen 0:          99
        Gen 1:          99
        Gen 2:          99

从结果上来,四种做法的性能区别还是非常明显的:使用Comparer<int>.Default进行排序的耗时只有LINQ排序的1/4。有趣的是,从GC次数上来看,LINQ排序也刚好是其他三种的一倍,和“理论值”几乎完全吻合。

经过测试后发现,其实LINQ排序的性能并不会比Array.Sort<T>要高,甚至还有明显的劣势。由于排序算法都已经被用到滥了,而且几乎已经成为了一个“标准”,因此从算法上来看它们不应该会有那么大的差距。所以,我们这里应该可以得出一个比较靠谱的推测:这几种排序方法的性能差距,完全是由于具体实现上的细节引起的。

至于其中的原因,我们下次再来进行分析——这些方法的实现,尤其是LINQ排序的实现,似乎还是挺有趣的。

本文代码:http://gist.github.com/281857

相关文章

Creative Commons License

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

Add your comment

53 条回复

  1. Fred_Xu
    *.*.*.*
    链接

    Fred_Xu 2010-01-21 00:12:00

    沙发!老赵写博客真敬业啊!这么晚了!佩服!膜拜下!

  2. 老赵
    admin
    链接

    老赵 2010-01-21 00:15:00

    @Fred_Xu
    你动作也很快

  3. Fred_Xu
    *.*.*.*
    链接

    Fred_Xu 2010-01-21 00:16:00

    Jeffrey Zhao:
    @Fred_Xu
    你动作也很快


    刚写好年报,习惯性的刷新了下首页,然后就看到您的博文了,学习啦。嘿嘿。

  4. DiryBoy
    *.*.*.*
    链接

    DiryBoy 2010-01-21 01:05:00

    执行 Compare 方法比较跟直接用 < 来比较差别挺大的

  5. 飞林沙
    *.*.*.*
    链接

    飞林沙 2010-01-21 01:05:00

    呵呵,学习了,期待下文。今天还在北京群里讨论他那个测试有问题呢。

  6. 火山
    *.*.*.*
    链接

    火山 2010-01-21 01:59:00

    学习了,今天看到这个问题。
    赵哥真厚道。

  7. 徐少侠
    *.*.*.*
    链接

    徐少侠 2010-01-21 07:47:00

    赵哥前阵子搞过类似主题的
    我昨天看见那个文章就联想到赵哥

    没想到今天就赫然看见了

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

    小城故事 2010-01-21 08:48:00

    昨天略读了下那篇文章,也纳闷Linq排序怎么会性能还高,而且是那么多?
    今天细品老赵的文章,一阵清新舒畅涌上心头……

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

    小城故事 2010-01-21 08:50:00

    Array.Sort(array, Comparer<int>.Default) 性能要比 Array.Sort(array)高吗?

  10. GoodGF
    *.*.*.*
    链接

    GoodGF 2010-01-21 08:58:00

    呵,很好很强大!

  11. 老赵
    admin
    链接

    老赵 2010-01-21 09:04:00

    @小城故事
    下次再说,不过你可以(也应该)先自己挖掘一下,呵呵。

  12. 四有青年
    *.*.*.*
    链接

    四有青年 2010-01-21 09:05:00

    果然是一上班文章就多起来了,哈哈继续期待。

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

    小城故事 2010-01-21 09:18:00

    Jeffrey Zhao:
    @小城故事
    下次再说,不过你可以(也应该)先自己挖掘一下,呵呵。


    我刚测试过,性能几乎一样嘛,估计是 Array.Sort(array)会再先判断array元素类型,再调用Array.Sort(array, Comparer<int>.Default)方法

  14. 老赵
    admin
    链接

    老赵 2010-01-21 09:25:00

    @小城故事
    “为什么”这个东西不能猜的,你还是看看源代码吧。

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

    小城故事 2010-01-21 09:44:00

    @Jeffrey Zhao
    只要合理为什么不能猜呢,先猜再去验证这样印象就深了。

    我看到Array.Sort会调用Comparer.Default作比较器,Comparer.Default提供了int Compare(object a, object b)方法, a和b必须同类型并且实现了IComparer接口,对于int数组来说,和Comparer<int>.Default效果是一样的。

  16. 老赵
    admin
    链接

    老赵 2010-01-21 09:46:00

    @小城故事
    少写个字,不能“光靠猜”,不过似乎可以“光看代码”,呵呵。

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

    小城故事 2010-01-21 09:50:00

    @Jeffrey Zhao
    呵呵,是啊,老赵也是先猜测再验证的

    所以Array.Sort的带Comparer的重载,用于一个类型没实现IComparer接口,或是实现了但不想用它默认的,要自定义排序规则。比如整型,我想不按大小排序,想按它各个数位的和排序,就可以自定义一个Int32Comparer.

  18. 老赵
    admin
    链接

    老赵 2010-01-21 09:52:00

    @小城故事
    对了,还有就是现在Array.Sort方法有泛型和非泛型两种,编译器究竟为我们选择了哪一种,是要弄明白的。比如:

    int[] array = ...
    Array.Sort(array)

    它调用的究竟是Array.Sort(Array),还是Array.Sort<T>(T[] array)呢?

  19. Tristan G
    *.*.*.*
    链接

    Tristan G 2010-01-21 10:01:00

    老赵同学,
    盛大创新院是搞啥的?

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

    小城故事 2010-01-21 10:02:00

    @Jeffrey Zhao
    很清楚了,编译器没有提前优化,因为没必要,就是用Array.Sort。无论是否泛型方法,最终比较两个元素时都要用IComparer.Compare方法,只要类型实现IComparer接口就可以了。

    我觉得IComparer是个学习接口的最好入门示例了,老赵说呢?

  21. 老赵
    admin
    链接

    老赵 2010-01-21 10:05:00

    @小城故事
    和优化无关,我是说编译器的选择。
    IComparer和IComparer<T>是不一样的,而且这也涉及到性能问题。
    你刚才混着说了(包括你提到的Compare方法是非泛型的),所以我觉得你应该确认一下。

  22. 明轩
    *.*.*.*
    链接

    明轩 2010-01-21 10:10:00

    LINQ排序也刚好是其他三种的一倍,和“理论值”几乎完全吻合


    理论值是怎么得来的?

  23. 老赵
    admin
    链接

    老赵 2010-01-21 10:11:00

    @明轩
    根据行为推测出来的。

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

    小城故事 2010-01-21 10:15:00

    IComparer和IComparer<T>型参数在Sort方法中效果应该是一样的,前者相当于IComparer<object>,都要调用Compare方法,其性能自然不会差太多了

  25. 老赵
    admin
    链接

    老赵 2010-01-21 10:16:00

    @小城故事
    类型转换,装箱拆箱。泛型的作用之一不就是提高这方面的性能吗?

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

    小城故事 2010-01-21 10:21:00

    @Jeffrey Zhao
    Array.Sort(Array array) 没有发生拆装箱操作啊,只是需要将array每个元素映射到IComparer接口上。

  27. 老赵
    admin
    链接

    老赵 2010-01-21 10:24:00

    @小城故事
    我说的是调用IComparer和IComparer<T>的Compare方法的时候……

  28. 苏飞
    *.*.*.*
    链接

    苏飞 2010-01-21 10:29:00

    赵哥 那么晚还写博客,明天早上还能赶上地铁吗?

    泛型里的Sort()方法 使用的应该是 QuickSort 算法
    的吧, 如果两元素相等时,顺序可能会被打乱的。

  29. 老赵
    admin
    链接

    老赵 2010-01-21 10:32:00

    @苏飞
    你说的这个和现在这个话题的关系是?

  30. 明轩
    *.*.*.*
    链接

    明轩 2010-01-21 10:33:00

    Jeffrey Zhao:
    @明轩
    根据行为推测出来的。


    老赵是根据的内存复制次数,来估计GC中回收次数吗?

  31. 老赵
    admin
    链接

    老赵 2010-01-21 10:35:00

    @明轩
    没那么复杂,文章里都提到了。

  32. abatei
    *.*.*.*
    链接

    abatei 2010-01-21 10:37:00

    这么久以来第一次能看到老赵的博客,感动啊!
    是不是现在没有Exploer6的限制了?
    Exploer6不是几M的小东西,没必要强制别人装吧!
    况且,从家到办公室到其他我用得到电脑的地方,总不能要求我到一个地方就装一次Exploer6吧

  33. 老赵
    admin
    链接

    老赵 2010-01-21 10:40:00

    @abatei
    现在IE6可以访问了?不会吧,前几天还有人向我提意见。
    // 我觉得你的概念啊名词啊用的好混乱……

  34. 极品拖拉机
    *.*.*.*
    链接

    极品拖拉机 2010-01-21 10:45:00

    你的是数组,整型的
    如果是List<object>
    根据object里面的某个字段来排序呢?
    是否ling性能要高点?
    利用delegate性能怎么样?

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

    小城故事 2010-01-21 10:48:00

    刚才试了下,Array.Sort(array)要求array元素实现IComparable或IComparable<T>,要是实现IComparable<T>就不存在拆装箱的问题了。

  36. 老赵
    admin
    链接

    老赵 2010-01-21 10:49:00

    @极品拖拉机
    要学会自己分析啊,比如看代码什么的,还有要合理推测。
    至少我没有看出LINQ在什么情况下性能会高。

  37. 前进中
    *.*.*.*
    链接

    前进中 2010-01-21 10:55:00

    最喜欢老赵文章中分析思路的讲解,精华所在,支持老赵

  38. asheng
    *.*.*.*
    链接

    asheng 2010-01-21 11:00:00

    Fred_Xu:

    Jeffrey Zhao:
    @Fred_Xu
    你动作也很快


    刚写好年报,习惯性的刷新了下首页,然后就看到您的博文了,学习啦。嘿嘿。



    哥们,你们啥公司啊?
    “年报”由你写啊……

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

    韦恩卑鄙 alias:v-zhewg 2010-01-21 11:25:00

    Jeffrey Zhao:
    @极品拖拉机
    要学会自己分析啊,比如看代码什么的,还有要合理推测。
    至少我没有看出LINQ在什么情况下性能会高。


    直接看System.LinQ 下面 Extention的实现就好了

    里面对Array IList<T> 进行扩展的函数 都是额外优化过向 Array看齐的,超过也不大可能

    其他的实现对 IEnumerable<T>进行扩展的函数
    都是100%调用foreach的 肯定快不了

  40. 吉日嘎拉>不仅权限设计
    *.*.*.*
    链接

    吉日嘎拉>不仅权限设计 2010-01-21 14:01:00

    先按推荐,然后再想,要是把你写的文章,都学一遍,仔细消化一下,不知道需要多长时间才可以。。。。。

  41. 极品菜鸟
    *.*.*.*
    链接

    极品菜鸟 2010-01-21 14:19:00

    如果你有肺,那就顶了。。

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

    韦恩卑鄙 alias:v-zhewg 2010-01-21 14:57:00

    吉日嘎拉&gt;不仅权限设计:
    先按推荐,然后再想,要是把你写的文章,都学一遍,仔细消化一下,不知道需要多长时间才可以。。。。。


    很快的 去年这个时候我才学开始用c#和lambda

  43. 铃兰草
    *.*.*.*
    链接

    铃兰草 2010-01-21 15:21:00

    羡慕ing,有这么多时间做研究。。。。。

  44. Jeffrey.Dan
    *.*.*.*
    链接

    Jeffrey.Dan 2010-01-21 15:56:00

    老赵也把代码放到git上了,Jquery最新的版本也从GOOGLE弄到git上了,这个东西,你们这些大牛都在推进呀 ··

  45. Fred_Xu
    *.*.*.*
    链接

    Fred_Xu 2010-01-22 09:06:00

    asheng:

    Fred_Xu:

    Jeffrey Zhao:
    @Fred_Xu
    你动作也很快


    刚写好年报,习惯性的刷新了下首页,然后就看到您的博文了,学习啦。嘿嘿。



    哥们,你们啥公司啊?
    “年报”由你写啊……


    年报中有个技术交流栏目,我只是写了一篇技术文章而已。

  46. 天天不在
    *.*.*.*
    链接

    天天不在 2010-01-22 09:52:00

    LINQ排序也比对方多出元素复制的开销.
    是不是这个造成了从GC次数上来看,LINQ排序也刚好是其他三种的一倍.

  47. asheng
    *.*.*.*
    链接

    asheng 2010-01-29 09:47:00

    CodeTimer.Time("SortWithDefaultComparer", 100,
    () => SortWithDefaultComparer(CloneArray(array)));
    第三个参数 看不出来是什么意思……

  48. 老赵
    admin
    链接

    老赵 2010-01-29 09:48:00

    @asheng
    搜CodeTimer,了解一下怎么用的。

  49. asheng
    *.*.*.*
    链接

    asheng 2010-01-29 10:01:00

    不是啊,我看了 CodeTimer 2009年3月的那篇文章
    后面 () => SortWithDefaultComparer(CloneArray(array)));这句看不懂……

  50. 老赵
    admin
    链接

    老赵 2010-01-29 10:02:00

    @asheng
    还看不懂的话就是你C#没学好了。

  51. asheng
    *.*.*.*
    链接

    asheng 2010-01-29 10:08:00

    我还有好多地方没学好……
    正在学嘛……

  52. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2010-01-30 10:26:00

    有快的,.NET不会弄个慢的算法让人用吧,除非有特殊使用场景。

  53. 獨翏淚
    *.*.*.*
    链接

    獨翏淚 2010-02-20 04:54:00

    SortWithDefaultComparer
    Time Elapsed: 6,219ms
    CPU Cycles: 14,847,507,504
    Gen 0: 49
    Gen 1: 49
    Gen 2: 49

    SortWithCustomComparer
    Time Elapsed: 30,612ms
    CPU Cycles: 73,158,368,166
    Gen 0: 49
    Gen 1: 49
    Gen 2: 49

    SortWithDelegate
    Time Elapsed: 36,909ms
    CPU Cycles: 88,216,384,149
    Gen 0: 49
    Gen 1: 49
    Gen 2: 49

    SortWithLinq
    Time Elapsed: 30,344ms
    CPU Cycles: 72,475,799,337
    Gen 0: 79
    Gen 1: 79
    Gen 2: 79

    中间的两个差距很大.
    不知何因.

    很喜欢老赵的博客.

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我