ホントに、tail.は遅いのか?
前回、前々回とF#や、C#、果てはILまで追っかけつつ検証してきた、tail.なワケですが、tail.有りと無しで果たしてどれほどの差があるのか?
んでもって、条件により結果は変わってくるのか?てーコトを検証してみた。
ただ、C#では例え末尾再帰に合致したとしても、tail.プレフィクス付きのコンパイルをしてくれないので、条件を合わせるため、DynamicMethodとして、検証対象を生成した上で検証してマス
tail.無しのサンプルメソッドは以下の通り
static Func<long,long,long> CreateNonTailOptimizedFunction() { var ret = new DynamicMethod("NonOptimized", typeof (long), new[] {typeof (long), typeof (long)}); var gen = ret.GetILGenerator(); var lbl = gen.DefineLabel(); gen.Emit(OpCodes.Ldarg_1); gen.Emit(OpCodes.Brtrue, lbl); gen.Emit(OpCodes.Ldarg_0); gen.Emit(OpCodes.Ret); gen.MarkLabel(lbl); gen.Emit(OpCodes.Ldarg_0); gen.Emit(OpCodes.Ldarg_1); gen.Emit(OpCodes.Add); gen.Emit(OpCodes.Ldarg_1); gen.Emit(OpCodes.Ldc_I8, 1L); gen.Emit(OpCodes.Sub); gen.Emit(OpCodes.Call, ret); gen.Emit(OpCodes.Ret); return (Func<long, long, long>) ret.CreateDelegate(typeof (Func<long, long, long>)); }
冗長だけど、tail.付きのサンプルメソッドは以下の通り。
static Func<long,long,long> CreateTailOptimizedFunction() { var ret = new DynamicMethod("Optimized", typeof(long), new[] { typeof(long), typeof(long) }); var gen = ret.GetILGenerator(); var lbl = gen.DefineLabel(); gen.Emit(OpCodes.Ldarg_1); gen.Emit(OpCodes.Brtrue, lbl); gen.Emit(OpCodes.Ldarg_0); gen.Emit(OpCodes.Ret); gen.MarkLabel(lbl); gen.Emit(OpCodes.Ldarg_0); gen.Emit(OpCodes.Ldarg_1); gen.Emit(OpCodes.Add); gen.Emit(OpCodes.Ldarg_1); gen.Emit(OpCodes.Ldc_I8, 1L); gen.Emit(OpCodes.Sub); gen.Emit(OpCodes.Tailcall); gen.Emit(OpCodes.Call, ret); gen.Emit(OpCodes.Ret); return (Func<long, long, long>)ret.CreateDelegate(typeof(Func<long, long, long>)); }
最後に、検証用のドライバメソッドは以下の通り。
static void Main(string[] args) { var n = 5000000; var optimized = CreateTailOptimizedFunction(); var nonOptimized = CreateNonTailOptimizedFunction(); Console.WriteLine(optimized(0, n)); Console.WriteLine(nonOptimized(0, n)); GC.Collect(); GC.WaitForPendingFinalizers(); GC.Collect(); var round = 10; var optimizedLst = new TimeSpan[round]; var nonOptimizedLst = new TimeSpan[round]; var watch = new Stopwatch(); for (int i = 0; i < round; i++) { watch.Restart(); optimized(0, n); watch.Stop(); optimizedLst[i] = watch.Elapsed; } for (int i = 0; i < round; i++) { watch.Restart(); nonOptimized(0, n); watch.Stop(); nonOptimizedLst[i] = watch.Elapsed; } //ここから以下は、結果をCSVに書き出すための処理。 var wtr = new data::CsvWriter("result.csv", "Round", "n", "NonOptimized", "Optimized"); var descriptor = wtr.AddDescriptor<TimeSpan>(); descriptor.RegistPresenter(arg => arg.TotalMilliseconds); optimizedLst.Zip(nonOptimizedLst, (a, b) => new {Optimized = a, NonOptimized = b}) .ForEach((elem, arg) => { wtr.Write(arg.ToString()); wtr.Write(n.ToString()); wtr.Write(elem.NonOptimized); wtr.Write(elem.Optimized); }); wtr.Close(); }
で、こいつらを検証していくワケですが、デフォルトのスタックサイズだと、差が出にくいので、editbin.exeで、スタックサイズを250MBに設定し直しているので、その点ご了承の程。