※ 大仰なタイトルですが、下記記事の一部分を引き伸ばした内容になります。
上記記事の Branching の項目で、分岐レス化による最適化が解説されている。
詳細は元記事参照として、Compare 的な処理が例として挙げられており、興味深かった。
まずは素直な書き方。
static int Compare(int x, int y) { if (x < y) return -1; if (x > y) return 1; return 0; }
普通に思える。どこに改善の余地があるのだろうか。
分岐最適化時代は以下。
static int Compare(int x, int y) { int gt = (x > y) ? 1 : 0; int lt = (x < y) ? 1 : 0; return gt - lt; }
？？？
ILを見ると一目瞭然。
// ひとつめの Compare IL_0000: ldarg.0 IL_0001: ldarg.1 IL_0002: bge.s IL_0006 IL_0004: ldc.i4.m1 IL_0005: ret IL_0006: ldarg.0 IL_0007: ldarg.1 IL_0008: ble.s IL_000c IL_000a: ldc.i4.1 IL_000b: ret IL_000c: ldc.i4.0 IL_000d: ret
// ふたつめの Compare IL_0000: ldarg.0 IL_0001: ldarg.1 IL_0002: cgt IL_0004: ldarg.0 IL_0005: ldarg.1 IL_0006: clt IL_0008: stloc.0 IL_0009: ldloc.0 IL_000a: sub IL_000b: ret
前者は分岐のジャンプ（bge.s IL_0006のような）があるが、後者は分岐がないのが見て取れる。
元記事の内容を繰り返す以上のことはできそうにないので原理等は元記事参照として、元記事にCompare の例によるベンチマークはなかったので測ってみる。（BenchmarkDotNet）
なお、ベンチマークとして正しくないのを承知のうえで下記のようにした。
- ベンチマーク内で分岐予測を撹乱する良い方法が分からなかったので、都度乱数生成した数値を比較する
- 数値の比較が処理として相対的に軽すぎるので、大量にループさせる
ベンチマークコード折りたたみ
[ShortRunJob] public class CompareBenchmark { private static int Compare(double x, double y) { if (x < y) return -1; if (x > y) return 1; return 0; } private static int CompareBranchless(double x, double y) { int gt = (x > y) ? 1 : 0; int lt = (x < y) ? 1 : 0; return gt - lt; } private readonly Random rand = Random.Shared; private const int N = 1 << 16; [Benchmark(Baseline = true)] public int Regular() { int result = 0; for (int i = 0; i < N; i++) { result += Compare(rand.NextDouble(), rand.NextDouble()); } return result; } [Benchmark] public int Branchless() { int result = 0; for (int i = 0; i < N; i++) { result += CompareBranchless(rand.NextDouble(), rand.NextDouble()); } return result; } }
| Method | Mean | Error | StdDev | Ratio | |----------- |-----------:|---------:|--------:|------:| | Regular | 1,205.4 μs | 72.52 μs | 3.98 μs | 1.00 | | Branchless | 911.3 μs | 97.30 μs | 5.33 μs | 0.76 |
図り方の関係で絶対値に意味はないが、分岐ミスがある状況での影響は明らかそう。
本当に必要とされる領域は限られるとは思うが、単純に恩恵があるタイプの知識だし、人が書いていたときに知っていれば意味が取れるので、知っておきたいと感じた。
