数组排序方法的性能比较（1）：注意事项及试验
2010-01-21 00:11 by 老赵, 9366 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
沙发！老赵写博客真敬业啊！这么晚了！佩服！膜拜下！