Hello World
Spiga

使用Lambda表达式编写递归函数(性能测试)

2009-09-27 13:23 by 老赵, 11348 visits

为了补充引用资料,现在对之前Lambda表达式编写递归函数进行一番性能测试。测试的对象为辗转相除法求最大公约数,使用以下三种方式计算:

  1. 普通递归
  2. 使用SelfApplicable。
  3. 使用Fix

后两者代码列举如下,它们在前一篇文章中已经有过描述:

public delegate TResult SelfApplicable<T1, T2, TResult>(
    SelfApplicable<T1, T2, TResult> self, T1 arg1, T2 arg2);

public static class LambdaRecursion
{
    public static Func<T1, T2, TResult> Fix<T1, T2, TResult>(
        Func<Func<T1, T2, TResult>, Func<T1, T2, TResult>> f)
    {
        return (x, y) => f(Fix(f))(x, y);
    }

    public static Func<T1, T2, TResult> Self<T1, T2, TResult>(
        SelfApplicable<T1, T2, TResult> self)
    {
        return (x, y) => self(self, x, y);
    }
}

性能比较的工具还是CodeTimer,测试代码如下:

class Program
{
    static int Fib(int x, int y)
    { 
        return y == 0 ? x : Fib(y, x % y);
    }

    static void Main(string[] args)
    {
        Fib(1, 2); // JIT“预热”
        var gcdMake = LambdaRecursion.Self<int, int, int>(
            (f, x, y) => y == 0 ? x : f(f, y, x % y));
        var gcdFix = LambdaRecursion.Fix<int, int, int>(
            f => (x, y) => y == 0 ? x : f(y, x % y));

        CodeTimer.Initialize();

        new List<int> { 10000, 100000, 1000000, 10000000 }.ForEach(n =>
        {
            CodeTimer.Time("Normal * " + n, n, () => Fib(12345, 29083));
            CodeTimer.Time("Make * " + n, n, () => gcdMake(12345, 29083));
            CodeTimer.Time("Fix * " + n, n, () => gcdFix(12345, 29083));
        });

        Console.WriteLine("press enter to exit...");
        Console.ReadLine();
    }
}

我们将三种方法各执行一万,十万,一百万及一千万遍,结果如下:

Normal * 10000
        Time Elapsed:   1ms
        CPU Cycles:     3,348,351
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Make * 10000
        Time Elapsed:   2ms
        CPU Cycles:     5,817,875
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Fix * 10000
        Time Elapsed:   16ms
        CPU Cycles:     39,522,627
        Gen 0:          7
        Gen 1:          0
        Gen 2:          0

Normal * 100000
        Time Elapsed:   12ms
        CPU Cycles:     31,708,838
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Make * 100000
        Time Elapsed:   17ms
        CPU Cycles:     43,155,337
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Fix * 100000
        Time Elapsed:   116ms
        CPU Cycles:     294,786,352
        Gen 0:          72
        Gen 1:          0
        Gen 2:          0

Normal * 1000000
        Time Elapsed:   125ms
        CPU Cycles:     316,509,017
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Make * 1000000
        Time Elapsed:   171ms
        CPU Cycles:     431,639,898
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Fix * 1000000
        Time Elapsed:   1,161ms
        CPU Cycles:     2,931,048,868
        Gen 0:          727
        Gen 1:          0
        Gen 2:          0

Normal * 10000000
        Time Elapsed:   1,258ms
        CPU Cycles:     3,165,804,593
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Make * 10000000
        Time Elapsed:   1,710ms
        CPU Cycles:     4,306,322,216
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

Fix * 10000000
        Time Elapsed:   11,057ms
        CPU Cycles:     27,856,077,942
        Gen 0:          7273
        Gen 1:          1
        Gen 2:          0

从执行时间上看,直接递归的性能最好,Self次之,但相差不大(似乎与call vs. callvirt + 多传一个参数的差距差不多),但Fix方式消耗的时间就为前两者的7倍左右了。

从GC压力上看,直接递归与Sel对GC都没有丝毫压力(在递归过程中没有创建任何对象),但Fib由于构建了额外的委托对象,其压力也相对较大,不过它们都是可以快速回收的对象,因此一般也不会对程序性能造成什么问题。

总体来说,测试结果和料想的结果比较一致。

Creative Commons License

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

Add your comment

4 条回复

  1. 颜斌
    *.*.*.*
    链接

    颜斌 2009-09-27 14:09:00

    SF?

  2. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-09-28 01:05:00

    居然抢到了板凳 T T

    要说Self方法“没有创建任何对象”可能有误导性,加上限定词比较好:“在递归过程中”没有创建新的委托对象。传入Self()的委托是一个,从Self返回的委托是第二个,至少在刚开始的时候创建了这两个委托对象。另外C#编译器实现lambda的方式使得写成lambda的委托会被cache住,有时候你会觉得这个很讨厌……

    using System;
    
    static class Program {
        static void Main(string[] args) {
            Action a = () => {};
        }
    }

    变成了
    using System;
    
    static class Program {
        static Action CS$<>9__CachedAnonymousMethodDelegate1;
    
        static void Main(string[] args) {
            Action action = (CS$<>9__CachedAnonymousMethodDelegate1 != null) ? CS$<>9__CachedAnonymousMethodDelegate1 : (CS$<>9__CachedAnonymousMethodDelegate1 = new Action(Program.<Main>b__0));
        }
    }

    乍一看会让人担心被cache的委托有没有可能挂住了什么庞大的东西,然后因为是被static变量挂住所以变成root set的一部分,怕怕。实际状况不是特别严重……

    然后还有个CLR的实现细节,在这个测试中被大量的循环次数给淹没了:创建委托的地点的不同,会是创建出来的委托里的Invoke实现不同;调用方法也是如此。
    老赵在计时前先调用了一次Fib来确保它被JIT编译,这本来是没错的。但由于Main方法在Fib方法之前被调用,也就是Main比Fib先被JIT编译,所以在Main里对Fib的调用点(callsite)就无法编译为直接的call,而要编译为一层间接的call,例如说
    call dword ptr [0x56781234]
    保存在0x56781234的一开始是一个preJIT stub,在JIT后则替换为实际的方法入口地址。

    要让Fib被最高效的发挥作用,可以用这样的code pattern:
    class Program {
      static void DriveFib() {
        Fib(); // 这个调用点会编译为直接call
      }
      static void Fib(...) { ... }
      static void Main(string[] args) {
        // 热身
        Fib(...);
        // 实际测试放在DriveFib里
        DriveFib();
      }
    }

    这个code pattern关键不是代码中方法声明的顺序,而是code-path上方法被调用的顺序(关系到JIT的顺序)

    不过老赵的例子里由于Fib消耗的时间主要是在递归调用上而不是在Main对Fib的调用上,所以这个细节的影响被淹没了。

    然后,老赵只对Fib做了热身,却没给那几个lambda对应生成的方法有热身的机会,让那几个lambda的起步比刘翔杯具……

    在JIT一个方法时,如果里面有创建委托的代码,CLR会看看目标是否已JIT;假设目标方法是静态方法,那么如果目标已JIT,调用这个委托的Invoke就会是这样的间接调用:
    ;; 调用委托的Invoke方法:
    ;; 假设指向委托的引用已在ecx
    mov eax, dword ptr [ecx+0xC]
    mov ecx, dword ptr [ecx+4]
    call eax
    => 跑到_methodPtr指向的代码里
    去掉第一个参数,然后
    jmp dword ptr [eax]
    => 跑到_methodPtrAux指向的代码里
    jmp 0x56781234
    => 跳转到实际目标

    如果某个方法被JIT的时候,其中的委托所指向的静态方法还为被JIT,那上面_methodPtrAux指向的代码就会有很大不同,经过繁复的捣腾跑到JIT里去;要调用3次之后才会被修改为一个直接的jmp。所以对应静态方法的lambda也有一些热身用的code pattern。这个就留给读者去实现了(啊啊!我终于用上这句了,泪)

    不过这个细节的影响也在大量循环中被淹没了……

    结论是:群众纷纷表示这些细节不知道也罢 :-p

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

    装配脑袋 2009-09-28 08:36:00

    用CER准备左右的方法和委托~

  4. 老赵
    admin
    链接

    老赵 2009-09-28 09:19:00

    RednaxelaFX:
    不过这个细节的影响也在大量循环中被淹没了……
    结论是:群众纷纷表示这些细节不知道也罢 :-p


    信RednaxelaFX,原地满状态复活。
    这个真是群众纷纷表示影响不大了。
    关于细节,咱空下来瞅瞅。现在去写文章鸟……

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我