数组排序方法的性能比较（5）：对象大小与排序性能
2010-01-29 00:09 by 老赵, 7183 visits在我公开测试结果之后，有朋友也进行了其他测试。在测试中我使用的是int数组，经过分析之后我们了解到Array.Sort<T>对于int数组有特殊的优化。于是，某些朋友使用了一些引用类型的数组进行排序，得到Array.Sort<T>方法的性能落后于LINQ排序——虽然由于测试方式的问题，这个结果和结论都不太妥当。不过在讨论的过程中，我们都意识到了一个问题：在其他条件不变的情况下，引用类型的字段越多，Array.Sort<T>方法所需时间就越久。这次我们就来讨论一下这个问题。
性能测试
为了体现字段数量和排序时间的相关性，我们首先来构造一个方法，它可以使用Emit生成包含一定数量的字段：
public abstract class TypeBase { public int ID; } class Program { public static ModuleBuilder moduleBuilder = null; static Program() { var assemblyName = new AssemblyName { Name = "SomeAssembly" }; var domain = Thread.GetDomain(); var asmBuilder = domain.DefineDynamicAssembly( assemblyName, AssemblyBuilderAccess.Run); moduleBuilder = asmBuilder.DefineDynamicModule("SomeModule"); } static Type CreateType(int numberOfField) { var typeName = "TypeWith$" + numberOfField + "$Fields"; var typeBuilder = moduleBuilder.DefineType( typeName, TypeAttributes.Class, typeof(TypeBase)); for (int i = 0; i < numberOfField; i++) { typeBuilder.DefineField("Field$" + i, typeof(int), FieldAttributes.Public); } return typeBuilder.CreateType(); } }
方便起见，我让每种动态类型都继承统一的TypeBase类，这样我们排序的目标便可以定为TypeBase数组，而作为比较器的TypeBaseComparer也可以直接访问ID字段。然后便是测试用的方法：
static void Main(string[] args) { CodeTimer.Initialize(); var random = new Random(DateTime.Now.Millisecond); var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray(); for (var num = 1; num <= 512; num *= 2) { var type = CreateType(num); var arrayToSort = new TypeBase[array.Length]; for (var i = 0; i < array.Length; i++) { var instance = (TypeBase)Activator.CreateInstance(type); instance.ID = array[i]; arrayToSort[i] = instance; } CodeTimer.Time( String.Format("Type with {0} fields (Array.Sort)", num), 10, () => Sort(CloneArray(arrayToSort))); CodeTimer.Time( String.Format("Type with {0} fields (ArraySorter)", num), 10, () => ArraySorter(CloneArray(arrayToSort))); } Console.ReadLine(); } static void Sort(TypeBase[] array) { Array.Sort(array, new TypeBaseComparer()); } static void ArraySorter(TypeBase[] array) { new ArraySorter<TypeBase>().OrderBy(a => a.ID).Sort(array); }
在比较时，我们将测试从1个字段的类型开始，每次将字段数量翻倍，直至512个字段——虽然夺得有些夸张，但对于试验来说，我还是希望差距能够明显一些。既然说Array.Sort<T>的性能受对象体积影响比较明显，而LINQ排序相对稳定，那么我们就来比较Array.Sort<T>以及与LINQ排序实现类似的ArraySorter的执行时间吧。请注意，除了两种排序方式之外，其他条件都完全相同：相同的数量，相同的类型，相同的初始顺序，以及相同的“比较依据”。
测试结果如下：
绘制成图表：
从图中可以看出明显的差别。当字段数量很少的时候，Array.Sort<T>的性能要比ArraySorter要高，这与我们之前的测试结果相符。但是在字段数量超过4个之后，ArraySorter的性能就开始领先了，且两者的差距随字段数量的增长会越来越大。因此，我们之前的观点是正确的。
这是为什么呢？在阅读以下内容时，您不如先自己思考一下？
原因分析
其实这还是一个和“局部性”有关的问题。局部性是影响性能非常主要的因素之一，我之前也不止一次谈过这个问题。那么在这里，局部性又是如何影响排序效率的呢？其实关键还是在于“比较器”上：
public class TypeBaseComparer : IComparer<TypeBase> { public int Compare(TypeBase x, TypeBase y) { return x.ID - y.ID; } }
TypeBaseComparer的实现非常简单，只是把两个TypeBase对象的ID值相减而已。显然，系统在执行这段程序的时候，会根据x或y的地址及ID字段的偏移量计算出一个地址，然后再去读取数据。不过我们知道，CPU在读取某个地址的的数据时，还会同时加载“一整条”的数据并缓存起来，这样再次读取附近的数据时会显得更快一些。那么试想一下，对于CPU来说，缓存及每个条目的大小是不变的，因此随着对象的体积增加，缓存中可以同时存在的对象数量便少了，这样虽然读取的次数不变，但是缓存的命中率就会随之下降。于是，对象体积增大，排序所消耗的时间也随之增加。
但是对于ArraySorter来说就完全不同了。根据ArraySorter的实现机制，它会首先根据keySelector得到排序字段——它在上例中就是个int值，IndexComparer然后在排序的时候将这个int数组保存起来，并且在排序时使用。因此，无论对象的体积是多少，在排序时ArraySorter永远只是在访问一个十分紧凑的int数组而已。排序结束后，ArraySorter也只是在操作一个个对象引用，它同样与对象的体积无关。由于排序其他条件不变，因此对象体积增大（造成局部性不佳）最终也只是导致keySelector工作的时候速度变慢，而其他部分统统不受影响。自然从某一时刻开始ArraySorter的性能会超过Array.Sort<T>，并且两者的差距会越来越大。
如果您对现在谈论的内容不很理解的话，可以了解一下与“局部性”有关的内容，并了解一下LINQ排序及ArraySorter的实现方式。
总结
可见，Array.Sort<T>与ArraySorter的性能高低并非是一句两句话可以说清楚的，在真实条件下选用哪种做法更有优势也不是一件容易确定的事情。不过，我们真需要把性能追求到这个地步吗？事实上，我相信在大部分实际的开发过程中，这点性能差距可以说是微乎其微。对于系统自带的Array.Sort<T>方法以及LINQ排序，其实它们并没有明显的替代关系。其实在某个特定的时候，您会发现其实两者间也只有一种符合条件——别多想，就用吧。
当然，一些明显的错误是需要避免的。例如，您在比较器中反复访问数据库的话，这就是您自己的问题了。
此外，我们这篇文章着重于测试和分析，但是如果可以直观地观察到“局部性”相关的数据岂不是更能说明问题吗？那么我们有什么办法通过实验来证明这一点呢？这问题其实也不大。例如，在使用Visual Studio 2008的Profiler时，我们可以让它同时监视L2 Cache的情况。这个实验的设计和执行就交由您亲自来吧。
经过了这几篇文章，您对于.NET框架中的排序类库，是否还有什么疑惑呢？
本文代码：http://gist.github.com/288765
相关文章
- 数组排序方法的性能比较（1）：注意事项及试验
- 数组排序方法的性能比较（2）：Array.Sort<T>实现分析
- 数组排序方法的性能比较（3）：LINQ排序实现分析
- 数组排序方法的性能比较（4）：LINQ方式的Array排序
- 数组排序方法的性能比较（5）：对象大小与排序性能
沙发?