Hello World
Spiga

数组排序方法的性能比较(2):Array.Sort<T>实现分析

2010-01-22 00:06 by 老赵, 8907 visits

昨天我们比较了Array.Sort<T>方法与LINQ排序的性能,知道了LINQ排序的性能以较大幅度落后于Array.Sort<T>方法。而对于Array.Sort<T>来说,性能最高的是其中使用Comparer<int>.Default作为比较器的重载方法。在前文的末尾我们做出了推测:由于排序算法已经近乎一个标准了(快速排序),因此从算法角度来说,Array.Sort<T>方法和LINQ排序上不应该有那么大的差距,因此造成两者性能差异的原因,应该是具体实现方式上的问题。

下载.NET框架的代码

既然是比较实现的区别,那么阅读代码是很直接的选择。谈到阅读.NET代码,我们往往会使用.NET Reflector将框架的程序集反编译为C#代码——不排除有朋友喜欢观察IL,并认为它们更直接,更底层。不过我倒觉得在绝大部分情况下,IL能看出的东西从C#也能看出而C#无法了解的IL也帮不上忙,因此许多“由IL发现问题”的文章其实只是自己和自己在爽。

不过,虽然.NET Reflector将程序集反编译成非常优秀的C#代码,但是还是无法恢复之前的不少信息。例如,局部变量名无法得知,这就给理解代码意图造成了困难。再例如,为了可读性我们可能会将一些条件语句分开写,而C#编译器则可能把它们连做一块儿。至于注释等明显会被去除的东西就更不用说了。因此,在能直接读到代码的情况下,我并不倾向于使用.NET Reflector。

您可能会说:这不是废话么,不过有些类库——如.NET框架并没有提供源代码,这又有什么办法呢?其实微软也已经公布了.NET框架相当部分程序集的源代码(几乎所有v2.0的程序集,如mscrolib,System,System.Web等等),而且它们其实都可以使用NetMassDownloader直接下载到本地。随员代码发布的还有方便调试的pdb文件,不过这是另一个话题了,我们现在只关心源代码。

因此,我建议您将所有微软提供的源代码都下载到本地。在看不懂.NET Reflector的反编译结果时,不妨参考一下源代码——还是包含注释的源代码。

Array.Sort<T>方法实现

各Array.Sort<T>方法的重载最终都会委托给下面这个重载来执行:

public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
{
    ...

    if (length > 1)
    {
        // <STRIP>
        // TrySZSort is still faster than the generic implementation.
        // The reason is Int32.CompareTo is still expensive than just using "<" or ">". 
        // </STRIP>
        if (comparer == null || comparer == Comparer<T>.Default)
        {
            if (TrySZSort(array, null, index, index + length - 1))
            {
                return;
            }
        }

        ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
    }
}

我们知道,从逻辑上说,Array.Sort<T>方法会使用IComparer<T>类型的比较器来判断两个元素的大小。不过在这里,.NET框架作了一个“特例”,它在用户没有提供比较器,或是直接使用默认比较器的时候利用TrySZSort方法进行排序。如果TrySZSort方法如果返回true,则表示排序完成,直接返回。如果它返回false,则继续使用内置的排序方法进行处理。那么TrySZSort又是如何实现的呢?

private static extern bool TrySZSort(Array keys, Array items, int left, int right);

这是一个extern方法,说明它是由CLR直接实现的,我们无法得知它的具体算法或是意图。不够从注释中可以得知,这个做法的目的是提高性能(明白注释的优势了吧)。每次使用IComparer<T>的Compare方法进行比较的时候相当于是一次虚方法的调用,CLR需要计算它的偏移量,也无法将其内联。这个细节相对于直接进行int的大小比较来说,也是有较大开销的。使用TrySZSort这种外部方法进行排序,有助于提高在特定情况下的执行效率。

因此,我们应该可以有足够信心来推断出TrySZSort的作用。TrySZSort方法的作用是对一些可以直接进行比较的原生类型(如int等)进行排序,如果它发现自己无法支持数组中元素的类型,那么就返回false,否则便排序后并返回true。如果TrySZSort返回false,便会使用ArraySortHelper进行排序。而其中的实现便是标准(真的很标准)的快速排序,如果您感兴趣的话可以自行阅读其中的代码。

值得注意的是,Array是定义在System命名空间下的类型,而ArraySortHelper则定义在System.Collections.Generic命名空间下。在阅读微软提供的源代码时有个麻烦之处便是不容易导航,例如ArraySortHelper类便让我一顿好找。不过,其实我们也可以配合.NET Reflector中强大的导航功能来快速定位到某个类的位置,然后直接去查找它对应的文件。当然,如果您索引了文件内容,也可以查找类似“class ArraySortHelper”这样的关键字,也可以很快找到特定文件。

Array.Sort<T>其他重载的性能

以上,我们已经知道为什么使用Comparer<int>.Default作为比较器时性能最高了,因为对于int类型来说,Array.Sort<T>方法会使用最快的TrySZSort方法进行排序。而如果我们使用自定义的Int32Comparer进行比较的话,Compare方法调用的开销是无可避免的,根据实验结果,使用Int32Comparer的执行时间比前者有80%的增加也可以接受。

那么使用委托进行排序的时候为什么比Int32Comparer更慢一些呢?且看其代码:

public static void Sort<T>(T[] array, Comparison<T> comparison)
{
    ...

    IComparer<T> comparer = new FunctorComparer<T>(comparison);
    Sort<T>(array, comparer);
}

其实原因很简单,因为.NET框架使用了FunctorComparer封装了comparison委托。这样在每次比较时,它相对于Int32Comparer来说还增加了委托执行的开销——这又相当于一次虚方法的调用:需要寻址,无法内联。

至此,我们已经分析了Array.Sort<T>各重载的实现方式,也了解了三种Array.Sort<T>重载性能有别的原因。刚好,不久前姜敏兄又回应了我的文章,认为使用Person类,而不是int类型进行比较的时候,仍旧是LINQ排序比较快——由此他认为两种做法的性能和类型也有关系。您认为这个说法正确吗?其实从实现上看,Array.Sort<T>几乎已经是最优的做法了。相反,LINQ排序由于会生成额外的序列,性能想要超过Array.Sort<T>几乎是件不可能的事情。但事实真是如此吗?

那这测试结果……我也写了一个Person类的测试(http://gist.github.com/282796),还是Array.Sort<T>比较快。那么为什么两个结果会有所不同呢?这是一个值得探讨的问题。

相关文章

Creative Commons License

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

Add your comment

43 条回复

  1. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2010-01-22 07:33:00

    早啊 老赵可以多分享一些学习框架的工具

  2. Jack Fan
    *.*.*.*
    链接

    Jack Fan 2010-01-22 08:56:00

    让我怎么说呢,只能顶了!感觉在看福尔摩斯推理小说!逻辑很紧密、很强大!

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

    四有青年 2010-01-22 09:29:00

    楼主一上班,大家就有好文可读,支持下。

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

    小城故事 2010-01-22 09:34:00

    老赵的工具很强大!Reflector的代码昨天没看懂。

    TrySZSort对于Int等值类型及String肯定有性能很高的比较方式,对于一般引用类型,Array.Sort(array)和Array.Sort<T>(array)还是会调用该类型实现的 IComparable.CompareTo方法。

  5. 老赵
    admin
    链接

    老赵 2010-01-22 09:38:00

    四有青年:楼主一上班,大家就有好文可读,支持下。


    这倒和上班无关,只是正好有个话题了。

  6. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-22 10:14:00

    hmm...又可以灌点水了

    在.NET里,数组可以分成SZArray和非SZArray两种。SZ就是single-dimensional, zero-based index,也就是我们一般用的数组。非SZ的数组可以是一维的但下标不从0开始(在C#里得调用特别的方法才能创建者种数组,没有专门语法支持),也可以是多维数组(也就是ElementType[a,b,c]形式的)。很多快速的数组例程都是只针对SZ数组,所以……不过平时大家甚少用非SZ数组,所以没啥特别需要注意的。
    TrySZSort()的作用是对元素类型为CLR直接支持的原始类型的SZ数组做快排;如果元素类型没有直接支持则返回false。

    在CLRv2里调用接口方法的开销并不总是很大,许多时候只是比调用普通的虚方法细微慢一点而已。在调用接口方法的调用点上会记录receiver的类型信息,同一类型的receiver在一个接口方法调用点上出现3次就会使那个调用点变为一个monomorphic inline cache,然后在累积出现100次预测错误时退化到megamorphic状态。

    例如说有这样的IFoo接口:

    interface IFoo { void Bar(); }
    class Foo : IFoo { public void Bar() { } }

    那么在这样一个调用点:

    foo.Bar();

    如果发现这个foo一直是Foo类型的,那么那个调用点逻辑上就会变成:

    if (foo.GetType().TypeHandle == typeof(Foo).TypeHandle) {
    call Foo::Bar()
    } else {
    cacheMiss++;
    if (cacheMiss >= 100) GotoMegamorphic();
    lookup IFoo::Bar() and call
    }

    这是monomorphic状态,也就是假设经过这个调用点的receiver总是同“一”类型的。
    Megamorphic状态的话则不做这种特例检查,而是通过一个特化的hashtable来做查询和跳转。

    可惜的是在CLRv2里,这种方法的inline cache一旦退化到megamorphic状态后就无法回到monophormic状态了,因而无法有效的处理所谓程序的阶段迁移(phase shift)。举例说,如果有类似这样的代码:

    interface IFoo { void Bar(); }
    class Foo1 : IFoo { public void Bar() { } }
    class Foo2 : IFoo { public void Bar() { } }
    
    //...
    var array = new IFoo[] {
      new Foo1(), new Foo1(), // ...(50个Foo1实例)
      new Foo2(), new Foo2(), // ...(150个Foo2实例)
    };
    foreach (var f in array) {
      f.Bar();
    }


    那么f.Bar()的f是Foo1时就一直比较快,过了会儿那个调用点的f都是Foo2了,速度就骤然降了下来并退化到megamorphic状态……
    头3轮循环的时候那个stub还处于收集类型信息的初始状态,等到第3轮发现receiver都是Foo1类型的,就开始创建特化的monomorphic inline cache,然后Foo1的状况就特别快。等到receiver变成Foo2为主的时候,每次f.Bar()调用都使得一个计数器加一,那个计数器到100了就把调用点转变到megamorphic状态,于是……

  7. 老赵
    admin
    链接

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

    @RednaxelaFX
    欢迎欢迎!

  8. 菩提树下的杨过
    *.*.*.*
    链接

    菩提树下的杨过 2010-01-22 10:33:00

    赵劼,网名老赵,洋名Jeffrey Zhao,目前就职于盛大创新院。

    今天突然发现老赵已经到盛大了!去年我也差点把简历投到盛大了,恭喜老赵这么快就抱到了大腿:)

  9. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2010-01-22 10:57:00

    等我把DirectCompute和OpenCL的.NET封装做好,先实现一个显卡·并行双调排序和显卡·并行快排试试,那性能提升就不用这么一点一滴的挤出来啦,呵呵。

  10. 老赵
    admin
    链接

    老赵 2010-01-22 11:05:00

    @装配脑袋
    排int之类的可能相对容易实现,但是能向现在这样支持IComparer<T>吗?

  11. 姜敏
    *.*.*.*
    链接

    姜敏 2010-01-22 11:11:00

    Ivony...:
    那个测试程序的性能点我已经测出来了。

    竟然是那个不起眼的地方,哈哈。。。。。不过想想也是,一个方法不论多么简单,如果被调用很多次也会出现问题的。

    LINQ的确有优势啊。。。。


    话说"LINQ的确有优势啊",是和我的测试一致,还是打问号的一样,嘎嘎,希望有朋友和我的测试结果有相同的人啊,同时我修改了代码,大家认为我的测试linq排序时,实际只排序了一次,我在循环中重新new一个,但结果一样,linq还是强,大家可以拿我的代码重新测试.

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

    韦恩卑鄙 alias:v-zhewg 2010-01-22 11:13:00

    一般看到reflector里面的内容调用externel的函数我就放心洗洗睡了

  13. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-22 11:17:00

    装配脑袋:等我把DirectCompute和OpenCL的.NET封装做好,先实现一个显卡·并行双调排序和显卡·并行快排试试,那性能提升就不用这么一点一滴的挤出来啦,呵呵。


    嗯,这个要顶的

  14. 老赵
    admin
    链接

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

    姜敏:
    话说"LINQ的确有优势啊",是和我的测试一致,还是打问号的一样,嘎嘎,希望有朋友和我的测试结果有相同的人啊,同时我修改了代码,大家认为我的测试linq排序时,实际只排序了一次,我在循环中重新new一个,但结果一样,linq还是强,大家可以拿我的代码重新测试.


    看了你的代码,你的基本概念啊……
    1、你还是没有CloneArray,复制了引用什么都不算的,你测试LINQ排序还是没有包括CloneArray的开销。
    2、说你只排序一次的人也不正确,因为LINQ本身就是不影响原有序列的,不过CloneArray的开销还是需要的。

  15. 磬石
    *.*.*.*
    链接

    磬石 2010-01-22 11:23:00

    那个下载源码的软件怎么这么多都提示Not available啊。。都是微软没有开放的吗?还是我没有用对?

  16. 老赵
    admin
    链接

    老赵 2010-01-22 11:25:00

    @磬石
    微软开放的源代码,从绝对数量上很多,相对数量上很少。

  17. 姜敏
    *.*.*.*
    链接

    姜敏 2010-01-22 11:28:00

    Jeffrey Zhao:

    姜敏:
    话说"LINQ的确有优势啊",是和我的测试一致,还是打问号的一样,嘎嘎,希望有朋友和我的测试结果有相同的人啊,同时我修改了代码,大家认为我的测试linq排序时,实际只排序了一次,我在循环中重新new一个,但结果一样,linq还是强,大家可以拿我的代码重新测试.


    看了你的代码,你的基本概念啊……
    1、你还是没有CloneArray,复制了引用什么都不算的,你测试LINQ排序还是没有包括CloneArray的开销。
    2、说你只排序一次的人也不正确,因为LINQ本身就是不影响原有序列的,不过CloneArray的开销还是需要的。



    老赵,我的测试代码中也包含你的代码,你的那部分我就没有修改过,但结果还是和你不同.

  18. 老赵
    admin
    链接

    老赵 2010-01-22 11:32:00

    @姜敏
    这样吧,你确认你是Release编译,并且不是在VS里按F5,或者确定VS里的Suppress JIT Optimization取消掉了吗?默认是打开的。

  19. 老赵
    admin
    链接

    老赵 2010-01-22 11:36:00

    @姜敏
    看到这个提示:http://www.cnblogs.com/Ivony/archive/2010/01/22/1653987.html
    你把Person的属性改成Field试试看?

  20. 姜敏
    *.*.*.*
    链接

    姜敏 2010-01-22 11:37:00

    Jeffrey Zhao:
    @姜敏
    这样吧,你确认你是Release编译,并且不是在VS里按F5,或者确定VS里的Suppress JIT Optimization取消掉了吗?默认是打开的。



    第一:在release下,linq强一些,如果是debug就强太多了.

    第二:我是按的F5运行的.


    第三:VS里的Suppress JIT Optimization没有修改,话说在哪修改成关闭?

  21. 老赵
    admin
    链接

    老赵 2010-01-22 11:42:00

    @姜敏
    忘了,呵呵,身边没有环境,你先自己找找看?我回家后找给你。

  22. 姜敏
    *.*.*.*
    链接

    姜敏 2010-01-22 11:52:00

    Jeffrey Zhao:
    @姜敏
    忘了,呵呵,身边没有环境,你先自己找找看?我回家后找给你。



    嘿嘿,我点击生成的exe后发现,我写的测试代码,可能是你说的少了clonearray的开销,所以性能更强,但我排序的就是list<t>,非要转换成arry吗?直接多次排序list<t>如何?

    你的那段代码,终于和你的结果一样,linq要差.

    老赵写一个直接排序list<t>的方法然后和linq方式比较看看。

    往往生成的结果集都是list<t>,而并非person[]

  23. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-22 11:53:00

    姜敏:

    Jeffrey Zhao:
    @姜敏
    这样吧,你确认你是Release编译,并且不是在VS里按F5,或者确定VS里的Suppress JIT Optimization取消掉了吗?默认是打开的。



    第一:在release下,linq强一些,如果是debug就强太多了.

    第二:我是按的F5运行的.


    第三:VS里的Suppress JIT Optimization没有修改,话说在哪修改成关闭?


    Tools -> Options... -> Debugging -> Suppress JIT optimizations on module load (Managed only)

    F5运行跟Ctrl+F5运行的性能表现不同是正常现象

  24. AlexKenyon
    *.*.*.*
    链接

    AlexKenyon 2010-01-22 11:54:00

    很好很强大,偶像啊

  25. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-22 12:00:00

    其实Debug版本没有太多的参考价值,我看了Debug版本的那个Compare方法的IL,充斥这大量莫名其妙和无用的东东:

    .method public hidebysig newslot virtual final
    instance int32 Compare(class Exam11.Person x,
    class Exam11.Person y) cil managed
    {
    // 代码大小 23 (0x17)
    .maxstack 2
    .locals init ([0] int32 CS$1$0000)
    IL_0000: nop
    IL_0001: ldarg.1
    IL_0002: ldflda int32 Exam11.Person::ID
    IL_0007: ldarg.2
    IL_0008: ldfld int32 Exam11.Person::ID
    IL_000d: call instance int32 [mscorlib]System.Int32::CompareTo(int32)
    IL_0012: stloc.0
    IL_0013: br.s IL_0015
    IL_0015: ldloc.0
    IL_0016: ret
    } // end of method PersonComparer::Compare

  26. 老赵
    admin
    链接

    老赵 2010-01-22 12:49:00

    姜敏:
    老赵写一个直接排序list<t>的方法然后和linq方式比较看看。

    往往生成的结果集都是list<t>,而并非person[]


    List多次排序没意义,因为排好一次就已经顺序了,再排的话没有可比性。
    你看一下List.Sort代码,就是直接使用了Array.Sort,所以性能是一样的。
    使用Array是因为需要CloneArray,比较Array和LINQ就够了。

  27. 幸存者
    *.*.*.*
    链接

    幸存者 2010-01-22 12:50:00

    Jeffrey Zhao:

    姜敏:
    话说"LINQ的确有优势啊",是和我的测试一致,还是打问号的一样,嘎嘎,希望有朋友和我的测试结果有相同的人啊,同时我修改了代码,大家认为我的测试linq排序时,实际只排序了一次,我在循环中重新new一个,但结果一样,linq还是强,大家可以拿我的代码重新测试.


    看了你的代码,你的基本概念啊……
    1、你还是没有CloneArray,复制了引用什么都不算的,你测试LINQ排序还是没有包括CloneArray的开销。
    2、说你只排序一次的人也不正确,因为LINQ本身就是不影响原有序列的,不过CloneArray的开销还是需要的。


    他那篇文章中的代码的问题并不是linq只排序一次,而是用linq排序的List在之前已经用List<T>.Sort排过序了,也就是说用linq做的是对一个有序的List进行排序,而用List<T>.Sort的那段代码才是只有第一次排序是真正的排序,其余几次都是对有序List再“排序”。
    另外,我觉得用linq倒是没必要CloneArray,因为linq本身不影响原列表,关键是测试Array.Sort的时候不应该把CloneArray的开销算进去。

  28. 老赵
    admin
    链接

    老赵 2010-01-22 12:59:00

    @幸存者
    原来如此,是我看错了,呵呵。
    你说的没错,要么在LINQ排序时CloneArray,要么在Array.Sort时扣除CloneArray。

  29. 幸存者
    *.*.*.*
    链接

    幸存者 2010-01-22 13:00:00

    @Ivony...
    其实我觉得生成IL的过程即使是Rlease编译,其优化也相当有限。关键是JIT的部分,并且即使是Release编译运行,有没有Debugger Attach到进程对JIT生成代码影响也挺大的。

  30. Ivony...
    *.*.*.*
    链接

    Ivony... 2010-01-22 13:19:00

    幸存者:
    @Ivony...
    其实我觉得生成IL的过程即使是Rlease编译,其优化也相当有限。关键是JIT的部分,并且即使是Release编译运行,有没有Debugger Attach到进程对JIT生成代码影响也挺大的。




    的确是这样,不过,应该不论用Release还是Debug,如果直接用F5启动,都会附加Debugger吧?

  31. 老赵
    admin
    链接

    老赵 2010-01-22 13:34:00

    @Ivony...
    如果在VS里使用Release编译并取消“Supress JIT Optimization”的话,就不会附加Debugger了,这点VS也会提示的。

  32. 俊采星驰
    *.*.*.*
    链接

    俊采星驰 2010-01-22 13:58:00

    你好!我想请问下用mvc开发的一个权限系统到时候能否用户webform开发的项目上来呢!我们老师想让我用mvc来开发一个权限管理模块,但其它的业务系统可能又会用webform开发!还有希望老赵能给些mvc学习的资料我是初学者看了老赵的视频没看懂!!
    谢谢~~

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

    韦恩卑鄙 alias:v-zhewg 2010-01-22 14:15:00

    Jeffrey Zhao:
    @Ivony...
    如果在VS里使用Release编译并取消“Supress JIT Optimization”的话,就不会附加Debugger了,这点VS也会提示的。


    -0-我都是很稳妥的去点exe 华哈哈

  34. hoodlum1980
    *.*.*.*
    链接

    hoodlum1980 2010-01-22 14:45:00

    如果是渐进阶相同,那么两个算法在时间复杂度基本是相同的(因为这个指标并不是去比较两个算法对同一个问题的解决速度,而是衡量他们关于问题规模增大时时间消耗的增长速度,指数级的增长速度对于计算机来说就是不可解的,因为硬件的提速在这种增长速度下根本不值一提)。很多人经常对相同渐进阶的算法可能会存在一个n倍的时间差距感到大惊小怪,而觉得这个n倍有多么了不起这是一种误解,因为常数系数的差异和增加通常是由于算法在考虑到普适性,稳定性,可靠性等方面造成的。

  35. 老赵
    admin
    链接

    老赵 2010-01-22 14:53:00

    @hoodlum1980
    恩恩,这其实也是理论和实际的区别。
    普通研究算法时,谈到复杂度等问题时,其实都是在说随问题规模增大时的变化规律。
    如果有两个时间复杂度A和B,且A比B高,这只是说明随着问题规模增大时,总会有某一时刻(如趋向于无穷大)A的耗时超过B。
    但是,在实际开发过程中,由于不是一个理想环境(例如A和B中的原子操作速度不同),且A的常数可能较B来的小,由于数据规模达不到某个临界点,则可能还是应该使用复杂度来的高的A算法而不是B。
    这种场景其实比比皆是,例如在一个确定数据规模很小的排序(如不超过5个元素),一般就用冒泡排序而不是快速排序了。

  36. C雷
    *.*.*.*
    链接

    C雷 2010-01-22 16:31:00

    来老赵这里报到一下!

  37. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2010-01-22 17:04:00

    @RednaxelaFX
    我想问问RFX大大,你是看了哪些书才了解了这么多的呢?

  38. JimLiu
    *.*.*.*
    链接

    JimLiu 2010-01-22 18:33:00

    我昨天看了 你的文章之后,也查源代码去了……

  39. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2010-01-25 20:02:00

    @麒麟.NET

    麒麟.NET:
    @RednaxelaFX
    我想问问RFX大大,你是看了哪些书才了解了这么多的呢?


    请叫我FX谢谢……
    我的知识面是在语言实现方面特化的,在这个领域内的知识我所知道的也不算多。这些都不是*你必须知道的.NET*的知识,作为应用程序员花很多时间去“知道”这些的意义并不大,因为基本上用不到。换了问我数据库优化或者socket编程或者ASP.NET或者语音识别之类的我就一头雾水了……

    其实有几本相关的非常经典的书我都还没来得及读,像是Smalltalk-80的blue book和讲CLOS的MetaObject Protocol的。我读过的一些VM相关的强悍的书有例如《Shared Source CLI Essentials》的第一版(这个我有原版;第二版一直没出实体书,只有PDF的草稿)、《Virtual Machines: Versatile Platforms for Systems and Processes》(这个买了影印版)。

    不过与VM的实现相关的许多信息都“藏”在论文堆中,而没有成书。

    ECMA-335和JVM规范讲的都是规范而不是实现,要读前者的话配合《The Common Language Infrastructure Annotated Standard》比较好;
    《Inside the Java Virtual Machine》同样讲的是规范所定义的概念;
    《Essential .NET, Vol 1》讲了一些实现不过书本身非常老了(但仍然非常值得.NET程序员一读);《CLR via C#》跟这个是同一类,也非常值得.NET程序员一读;
    《Virtual Machine Design and Implementation in C/C++》与《Virtual Machines》(Iain Craig那本,这本我也有原本但觉得好亏)其实都没用到什么强悍的实现技巧。后者好歹还提了一下threaded code,但inline caching之类的主题根本没提及。
    《Distributed Virtual Machines: Inside the Rotor CLI》这本我还没怎么读,里面的状况不是太清楚。
    《Garbage Collection》这本虽然老但是必读,读了之后会发现它的思想到现在都还不老(注意,是思想不老,不是实现不老)。
    《Advanced Compiler Design and Implementation》(俗称鲸书)这本里讲到的一些技巧可以用在JIT的实现中。这本我读的是中文版,感觉还挺顺的。当然讲编译原理的书里提到的优化技巧普遍可以用在JIT中,但这本讲到了些具体的有趣的。

    书里没讲,此类知识要淘就得到论文堆里了。关于Self的实现的论文一大堆都值得读,Oberon相关的也非常值得读,后面就到大量的讲JVM实现的论文也值得读,还有些别的VM例如PyPy、TraceMonkey的也值得读。要读这些论文最好是有个ACM帐号,这个要是在大学里的话就不是问题,已经毕业了的话就拜托一下学弟学妹们帮忙吧。……或者自己有钱买个帐号更好。
    读blog也行,有不少blog里会有零散的相关信息,要找的话请自行放狗。找起来会挺吃力的。
    然后就是源码,很多知识藏在代码的注释里。许多人很强悍的想法未必有时间写成详细的文档,但在代码里或许会有不错的注释,多读读也没坏处(在有时间的前提下,嗯时间……)
    再不行就上逆向工程吧。虽说对有些商业产品的逆向工程属于灰色地带,但在天朝出于自我学习的目的还是可以合法做很多事情的orz。我对CLRv2的了解主要是通过读CLR开发者的blog、参考SSCLI 2.0与自己写例子做逆向工程来获取的。

  40. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2010-01-26 09:27:00

    @RednaxelaFX
    谢谢指点:)

  41. tianxd
    *.*.*.*
    链接

    tianxd 2010-03-06 09:56:00

    哦也

  42. 晓岩
    123.145.125.*
    链接

    晓岩 2010-04-09 12:58:53

    老赵~你怎么不把你的asp.net mvc系列的出书啊???-

  43. softfair
    8.35.201.*
    链接

    softfair 2013-06-29 16:05:26

    这篇blog里,有你很多的评论回复,老赵的排序都是用 array([ ])的形式,我把他传数组的地方都改成了List,运行了发现性能还是 Linq快,这是为什么呢?

    我的部分修改代码:

    var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray();
    
    List<Person> list = new List<Person>();
    Person p;
    for (int i = 0; i < 1000 * 500; i++)
    {
        p = new Person();
        p.firstName = string.Format("{0} firstName", array[i]);
        p.lastName = string.Format("{0} lastName", array[i]);
        p.ID = array[i];
        list.Add(p);
    }
    

    上面代码,生成List 实例

    static List<Person> CloneArray(List<Person> source)
    {
        var dest = new Person[source.Count];
        var sour = source.ToArray();
        Array.Copy(sour, dest, source.Count);
    
        sour = null;
    
        return dest.ToList<Person>();
    
    }
    

    上面代码CloneArray,把List 转换成Array,再复制,最后变回List。

    static void SortWithCustomComparer(List<Person> array)
    {
        array.Sort(new PersonComparer());
    }
    
    public class PersonComparer : IComparer<Person>
    {
        public int Compare(Person x, Person y)
        {
            return x.ID-y.ID;
        }
    }
    

    我的Peson类

    public class Person
    {
        public string firstName;
        public string lastName;
        public int ID;
    }
    

    主函数:

    CodeTimer.Initialize();
    
    // CodeTimer.Time("SortWithDefaultComparer", 100,
    //    () => SortWithDefaultComparer(CloneArray(list)));
    
    CodeTimer.Time("SortWithCustomComparer", 100,
        () => SortWithCustomComparer(CloneArray(list)));
    
    // CodeTimer.Time("SortWithDelegate", 100,
    //    () => SortWithDelegate(CloneArray(list)));
    
    CodeTimer.Time("SortWithLinq", 100,
        () => SortWithLinq(CloneArray(list)));
    
    CodeTimer.Time("SortWithCustomComparer", 100,
        () => SortWithCustomComparer(CloneArray(list)));
    
    CodeTimer.Time("SortWithLinq", 100,
        () => SortWithLinq(CloneArray(list)));
    

    这里主函数调2遍,查看输出:

    并且 Suppress JIT Optimization取消,是Release版本,直接运行exe,结果还是Linq的快一点。

    我这里主要的不同点是在 函数参数主要是传List参数,一个最大的差别是在 CloneArray(List source),我每次都是Linq快一点,这是为什么?

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我