Hello World
Spiga

数组排序方法的性能比较(5):对象大小与排序性能

2010-01-29 00:09 by 老赵, 5906 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

相关文章

Creative Commons License

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

Add your comment

21 条回复

  1. DiryBoy
    *.*.*.*
    链接

    DiryBoy 2010-01-29 00:26:00

    沙发?

  2. 老赵
    admin
    链接

    老赵 2010-01-29 00:54:00

    @DiryBoy
    图片和表格能看到吗?

  3. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-29 02:14:00

    Jeffrey Zhao:
    @DiryBoy
    图片和表格能看到吗?


    反正我是看不到……

  4. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-29 02:34:00

    可以看到。

  5. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-29 08:35:00

    RednaxelaFX:

    Jeffrey Zhao:
    @DiryBoy
    图片和表格能看到吗?


    反正我是看不到……




    要写得了代码,查得出异常;杀得了木马,翻得了围墙。

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

    小城故事 2010-01-29 08:47:00

    如果字段是引用类型的,老赵是否试过?

  7. 老赵
    admin
    链接

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

    @小城故事
    引用类型和int的区别在哪里?

  8. 老赵
    admin
    链接

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

    RednaxelaFX:

    Jeffrey Zhao:
    @DiryBoy
    图片和表格能看到吗?


    反正我是看不到……


    奇怪,我这边不那个啥也能看到。

  9. DiggingDeeply
    *.*.*.*
    链接

    DiggingDeeply 2010-01-29 09:26:00

    看的到

  10. 老赵
    admin
    链接

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

    @DiggingDeeply
    我却看不到了,好吧好吧,某死人玩意儿抽风了。

  11. 老赵
    admin
    链接

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

    看不到的表格和图片的朋友可以瞅瞅这个:
    http://cid-fba4447598b1d752.skydrive.live.com/self.aspx/Public/array-sort-5.zip

  12. 雪痕-shawen
    *.*.*.*
    链接

    雪痕-shawen 2010-01-29 10:01:00

    老赵,经常看你的博客,能在这请教个问题么?

    我最近程序用jQuery中的ui.tabs.js 这个插件,(tab应用了母版)每个tab都是加载的一个aspx页面,当我在这个ajax加载的页面用了一个GridView和DropdownList控件,当DropdownList选项发生变化的时候GridView中的数据刷新,但是好像不起作用,而且我在上面做了其他查询,当我点击查询按钮的时候,页面发生跳转,而不是在tab所在的页面执行操作?

    还有,在这个页面中用了My97DataPicker控件后,在tab页面也无法选择日期时间?

    为什么在单独的页面就没问题,在tab页中用就会有问题呢?

    急切希望老赵或者老赵的支持者们告诉我怎么解决?
    QQ:38756478

  13. 老赵
    admin
    链接

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

    @雪痕-shawen
    我不懂前台的说……

  14. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2010-01-29 10:19:00

    我居然没那个啥也看到了

  15. LanceZhang
    *.*.*.*
    链接

    LanceZhang 2010-01-29 11:48:00

    spreadsheets.google.com
    貌似被墙了,看不到结果。。。

  16. 幸运草
    *.*.*.*
    链接

    幸运草 2010-01-29 13:30:00

    有时我们的测试环境要尽可能的接近使用环境能达到我们测试的目的。

  17. 老赵
    admin
    链接

    老赵 2010-01-29 13:32:00

    @幸运草
    恩恩,那是,解决实际问题和研究问题表现的思路还是有区别的。
    这就好比算法理论上的时间复杂度不能想都不想直接用一样。

  18. 幸运草
    *.*.*.*
    链接

    幸运草 2010-01-29 13:40:00

    很佩服老赵对技术的“痴”,从你的文章中学到了不少东西。

  19. 雪痕-shawen
    *.*.*.*
    链接

    雪痕-shawen 2010-01-29 16:10:00

    @Jeffrey Zhao

    我把你当成万能的了!!哈哈...

  20. DiryBoy
    *.*.*.*
    链接

    DiryBoy 2010-01-29 19:12:00

    Jeffrey Zhao:
    @DiryBoy
    图片和表格能看到吗?


    可以。

  21. 冯岩
    *.*.*.*
    链接

    冯岩 2010-02-01 16:23:00

    雪痕-shawen:
    老赵,经常看你的博客,能在这请教个问题么?

    我最近程序用jQuery中的ui.tabs.js 这个插件,(tab应用了母版)每个tab都是加载的一个aspx页面,当我在这个ajax加载的页面用了一个GridView和DropdownList控件,当DropdownList选项发生变化的时候GridView中的数据刷新,但是好像不起作用,而且我在上面做了其他查询,当我点击查询按钮的时候,页面发生跳转,而不是在tab所在的页面执行操作?

    还有,在这个页面中用了My97DataPicker控件后,在tab页面也无法选择日期时间?

    为什么在单独的页面就没问题,在tab页中用就会有问题呢?

    急切希望老赵或者老赵的支持者们告诉我怎么解决?
    QQ:38756478


    你这问题只有自己去发现问题和解决问题了,是特定情况,并且你使用了第三方开发的库,JQUERY以及ui.tabs.js 同时又使用第三方的My97DataPicker日期控件!出现问题也很正常,但像这类问题不要希望于网上的一些"牛人"帮你解答,这问题没有技术难度,但不可否认回答起来很难,甚至无法回答.它们常常基于特定的运行环境,以及你的项目代码!别人无法模拟,甚至也没有时间来模拟一个你这样的环境!
    你应该自己试着使用排除法来反查问题的所在!然后缩小问题范围,最后如果确定了是第三方组件之间的兼容问题的话,你可能需要放弃一些组件,或者采用曲线救国的方式,例如使用IFRAME,把出现问题不兼容的放在IFRAME中(如果你非要使用第三方组件)!
    网上的一些牛人包括老赵都很忙,可以向他们请教问题,但一般最好是基于设计思想,或是知识点来问!基于特定环境或是特定代码的提问,他们也很头疼的!

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我