きっかけ
いままで 10 年ほど C# を愛用してきて C# でコードを組むときは可読性や開発効率などアプリ層観点でしかロジックを眺めてこなかったが、競技プログラミングに C# が使えるのだろうかという疑問をふと抱いたため、30 年ぶりに C++ も書いてみたりして比較衡量し C# をよりプリミティブな面から研究してみた。いろいろと考察したところ、C# も C# 7.0 あたり以降で拡張導入された機能を活かせば戦えるのではないかと。
C# で性能を追求するテクニックはいくつかあるが、今回はその中でラムダ式 (C# 3 以降) とローカル関数 (C# 7.0 以降) の性能比較をしてみたい。
結論
いきなり結論。クロージャローカル関数 (local closure) がベスト、静的ラムダ式 (lambda static) がセカンドベスト、クロージャラムダ式 (lambda closure) がワースト。両端の幅は 10% ～ 20% くらい。驚くのは local CLOSURE がベストであるということ。LINQ の術語によく使う lambda static はまあまあ優秀だが絶対王者ではない。(<< は揺らがない順序関係、< は環境などによっては揺らぐ可能性がある順序関係。)
(inferior) lambda closure << local static << lambda static < local closure (superior)
実用としては、保守性・可読性の観点から通常通り静的なラムダ式で書くことでよいが、外部変数を取り込むときはラムダ式の使用は禁止にしてローカル関数で定義するのが望ましい、と考えられる。
理由
なぜこうなるのか。closure が static より速いとも言えないし、local が lambda より速いとも言えない。一見まちまちに見えるこの結果にも理由があり、いろいろなサイト *1*2 で解説されているところを考察すると見えてくるものがある。
背景：ラムダ式は匿名オブジェクトの一種であり、匿名型と同様にコンパイラがオブジェクトを生成し、「(名前管理空間としての) クラス 」に属するように構成される
ラムダ式は記号のように見えるし、プログラマにとってはソースコードの地の文に置かれる関数と取り扱い方が異なるが、コンパイラや VM にとっては一般のクラス・メソッドと同じく「オブジェクト」である。関数は機能 (function) という抽象概念に見えるが、ノイマン型コンピュータではメモリに載るオブジェクト (= データセット) であり、.NET においてはクラスを単位として管理されるオブジェクトである。したがって、すべてのメソッドはクラスに紐づけられる。というか、C/C++ とは違い、 C# ではそもそもクラスから独立して単独で関数定義することができない。
理由１：.NET においては、静的クラス・静的メソッドよりもインスタンスクラス・インスタンスメソッドを重視して最適化されている
C# / .NET はオブジェクト指向言語 / フレームワークであるため、定義することの少ない静的クラス・静的メソッドよりもインスタンスクラス・インスタンスメソッド寄りに最適化するのは当然である。
そしてそのために、静的メソッドよりもインスタンスメソッドの方が実行効率が高い、という現象が起きる。逆に言うと、はやりの関数型プログラミングからすれば望ましい、内部状態 (インスタンス) を管理する必要のない参照透過的な「静的メソッド」であっても、なんと、(インスタンスメンバー変数を参照するなどして) 敢えてインスタンスメソッドにしてしまう方が .NET では実行効率が向上する！
これが下記になる理由。
local static << local closure lambda static < local closure
理由２：ラムダ式はオブジェクト化されるが、クラスオブジェクトと同等の最適化は期待できない
ラムダ式はクラスから独立しているようにプログラマからは見えるが、VM 内ではクラスに紐づいて管理されている。ということは、実行時にオブジェクト化のコストがかかることになる。オブジェクト化自体のコストはインスタンスクラス・静的クラスも同じだが、匿名オブジェクト (ラムダ式・匿名関数・匿名型) はクラスオブジェクトと同等の最適化がなされない、という点がもう１つのポイントになる。
プログラマからは同一に見える匿名オブジェクトでもコンパイラ / VM にとっては同一か否か判別できない。例えば、匿名型インスタンス new { Index = 1, Value = 1 } と別に記述したもう１つの new { Index = 1, Value = 1 } はプロパティの並び順が同じであるためコンパイラは同じ「型・クラス」と認識してくれるが、同じ値であっても VM は同じ「インスタンス」とまでは認識してくれない。それと同じようにラムダ式も同じオブジェクトとは認識してくれないケースがある。それがクロージャだ。
クロージャは、自身が参照するすべての変数を管理しなければならない。内部変数は通常の関数におけるローカル変数に相当するが、外部変数は外部変数で管理が必要である。ラムダ式にとっての状態遷移しうる外部変数の位置づけはインスタンスメソッドにおけるメンバー変数と同等であるため、プログラマがクロージャラムダ式を定義するとコンパイラは外部変数をメンバー変数とする匿名クラスを定義する。このとき外部変数はヒープに確保される。
さて、同一の外部変数 int y をキャプチャーする同一記述のクロージャラムダ式 (int x) => x + y が複数あったとして、それらが同じクラスの同じメンバーメソッドになるであろうか？ プログラマの視点では、理屈上、同一であると認識できる。が、コンパイラにとっては構文解析を超高度化しないと実際にはムリであろう。というわけで、同一記述のクロージャラムダ式であっても VM は同一とは認識せず、別個にクラス・オブジェクト化すると思われる。ということは、同一に見えても別クラスとなり、したがって記述箇所の異なるラムダ式は同一記述であっても別の関数オブジェクトが利用され、同一のコントロールフローが利用される頻度も低下する。結果として、キャッシュ効率も悪くなり、コード最適化の効果も薄いため最適化がかからない、ということになる。クラスメソッドやローカル関数で int add(int x) => x + this.y; と書いた場合は、VM は関数ポインタでメソッドを、メンバー変数で this.y を一意に特定できる。したがって、こちらは多頻度利用され、最適化もされると期待できる。
これが下記になる理由。
lambda closure << local static lambda closure << lambda static
計測プログラム
回 LINQ で計算する処理を
回 for イテレーションして計測する。
using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Runtime.CompilerServices; public class StopWatch : Stopwatch { public void DispElapsed(string text) { base.Stop(); Console.WriteLine($"{text} : {base.ElapsedMilliseconds} ms"); base.Reset(); base.Start(); } [MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)] public static void Main() { var sw = new StopWatch(); int y = 3; int func1(int x) => x / 7 + 3; // static local function int func2(int x) => x / 7 + y; // closure local function sw.Start(); for (int i = 0; i < 1000; ++ i) Enumerable.Range(0, 1000000).Select( x => x / 7 + 3 ).Count(); // static lambda sw.DispElapsed("lambda static "); for (int i = 0; i < 1000; ++ i) Enumerable.Range(0, 1000000).Select( func1 ).Count(); sw.DispElapsed("local static "); for (int i = 0; i < 1000; ++ i) Enumerable.Range(0, 1000000).Select( x => x / 7 + y ).Count(); // closure lambda sw.DispElapsed("lambda closure"); for (int i = 0; i < 1000; ++ i) Enumerable.Range(0, 1000000).Select( func2 ).Count(); sw.DispElapsed("local closure"); } }
計測した結果、下記のような結果に。何度か計測しても同じ環境上ならほぼ同じ結果になる。ハードウェアは同一の i9-10900 + RAM 32GB。
おわりに
LINQ は、言語間比較の際に誤った評価手法で「遅い」と結論付けられ、不当な扱いをされることの多いかわいそうな子。
LINQ の遅延評価を即時評価に切り替えるために .ToArray() や.ToList() でオブジェクト実体化しているケースがあるが、その評価手法は間違っていることが多い。
.ToArray() も .ToList() もどちらもヒープにメモリ確保してそこにデータをコピーするが、その性能が LINQ が実行したい本質 (今回のラムダ式やローカル関数) に比べて圧倒的に悪いため、実体化自体を計測したいのでなければ意味をなさない。
.Count() であれば、全量をシーケンシャルに操作しつつも、余分に消費する変数が int (count) １つ分であるため、(計算結果は保持されないが) LINQ 自体の計算速度の評価としては適切となる。
4.0 GHz CPU の場合、 回まわして約 3,000 ms というのは１回あたり 12 Clock Cycle に相当する。整数除算 x 1 + 整数加算 x 1で 12 Clock Cycle は非常に妥当で、計算、イテレーション、関数呼び出しのコストは、いずれもまったく悪くない。LINQ が遅くなるのはオブジェクト実体化のやり方が誤っているか下手なのだと思う。
LINQ を用いてオブジェクト実体化 (計算結果格納) を伴う実コードの性能評価をする際は、オブジェクト実体化を１回のみ、効率的に実行する方法を含めて検討しなければならない。
ただ C# は値型配列であってもヒープにメモリ確保するため、.ToArray() を回避して簡単・簡潔に stackalloc[] にする方法が欲しい。stackalloc[] が関数を超えられないため仕方ないのだが、stackalloc[] に書き込むためだけに
Span<int> sa = stackalloc int[n]; foreach (var (result, i) in seq.Select( (x, i) => (func(x), i) )) { sa[i] = result; }
という LINQ (関数型) と foreach (手続型) が混在するコードを書くのもね ... あるいはこうか。わざわざ unsafe 持ち出しても、ジェネリックでデータ型を記述できなくなる上に記述量が増えているからボツかな。。。
public class Test { public static void Main() { var seq = Enumerable.Range(0, n).Select( x => func(x) ); Span<int> span; unsafe { int* sa = stackalloc int[n]; span = new Span<int>(seq.Write(sa), n); } } } public static class Extension { [MethodImpl(AggressiveInlining)] unsafe public static int* Write(this IEnumerable<int> src, int* dst) { foreach (var (x, i) in src.Select( (x, i) => (x, i) )) dst[i] = x; return dst; } }
