Hello World
Spiga

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

2009-09-27 13:23 by 老赵, 12583 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

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

使用Live Messenger联系我