使用Lambda表达式编写递归函数(性能测试)
2009-09-27 13:23 by 老赵, 12633 visits为了补充引用资料,现在对之前Lambda表达式编写递归函数进行一番性能测试。测试的对象为辗转相除法求最大公约数,使用以下三种方式计算:
- 普通递归
- 使用SelfApplicable。
- 使用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由于构建了额外的委托对象,其压力也相对较大,不过它们都是可以快速回收的对象,因此一般也不会对程序性能造成什么问题。
总体来说,测试结果和料想的结果比较一致。
SF?