数组排序方法的性能比较(5):对象大小与排序性能
2010-01-29 00:09 by 老赵, 7167 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):对象大小与排序性能
沙发?