Created
October 10, 2018 04:42
-
-
Save ufcpp/0b9a8a8d4ea6b8eb6505ec0c624b65f8 to your computer and use it in GitHub Desktop.
MoveNext/Current 型列挙と TryMoveNext の比較
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using BenchmarkDotNet.Attributes; | |
using BenchmarkDotNet.Running; | |
using System; | |
using System.Collections; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Runtime.CompilerServices; | |
/// <summary> | |
/// MoveNext/Current で2回 virtual call するのが嫌で、1つにまとめようというもの。 | |
/// | |
/// <typeparamref name="T"/> の共変性を確保するために、戻り値が T で out の方が bool になってしまう。 | |
/// なので結構使い勝手は悪い。 | |
/// out 引数とか、タプルを使った (T, bool) で共変性を担保できないっていう .NET の問題。 | |
/// </summary> | |
interface IFastEnumerator<out T> | |
{ | |
T TryMoveNext(out bool success); | |
} | |
/// <summary> | |
/// <see cref="IEnumerable{T}"/> 同様、<see cref="IFastEnumerator{T}"/> を返すだけのインターフェイスも。 | |
/// ただ、今回のベンチマークでは enumerator の方だけパフォーマンスを見るんで、こいつは使ってない。 | |
/// </summary> | |
interface IFastEnumerable<out T> | |
{ | |
IFastEnumerator<T> GetEnumerator(); | |
} | |
/// <summary> | |
/// <see cref="IEnumerator{T}"/> 実装。 | |
/// 単に配列を列挙。 | |
/// <see cref="Array.GetEnumerator"/> を呼ぶのでもいいんだけど、比較のために自作。 | |
/// パフォーマンス優先でチェックをさぼってる。MoveNext を int がオーバーフローするまで呼ぶと MoveNext が再び true を返すようになるけど、そんな使い方はしないという前提。 | |
/// </summary> | |
class NormalEnumerator : IEnumerator<int> | |
{ | |
private readonly int[] _data; | |
public NormalEnumerator(int[] data) => _data = data; | |
private int _i = -1; | |
public int Current => _data[_i]; | |
public bool MoveNext() => ++_i < _data.Length; | |
object IEnumerator.Current => Current; | |
public void Dispose() { } | |
public void Reset() => throw new NotImplementedException(); | |
} | |
/// <summary> | |
/// <see cref="NormalEnumerator"/> と同じことを <see cref="IFastEnumerator{T}"/> で実装。 | |
/// </summary> | |
class FastEnumerator : IFastEnumerator<int> | |
{ | |
private readonly int[] _data; | |
public FastEnumerator(int[] data) => _data = data; | |
private int _i = -1; | |
public int TryMoveNext(out bool success) | |
{ | |
var i = ++_i; | |
var data = _data; | |
if((uint)i < (uint)data.Length) | |
{ | |
success = true; | |
return data[i]; | |
} | |
else | |
{ | |
success = false; | |
return default; | |
} | |
} | |
} | |
/// <summary> | |
/// 配列に対する和の計算を、<see cref="NormalEnumerator"/> と <see cref="FastEnumerator"/> を介するのでどのくらい違うかを試す。 | |
/// あと、具象型を渡す(non-virtual なのでインライン化を期待できる)と、インターフェイスを渡す(virtual なのでインライン化されない)でどのくらい差が付くかも試す。 | |
/// | |
/// 実行例: | |
/// Method | Mean | Error | StdDev | | |
/// ----------------- |---------:|---------:|---------:| | |
/// NonVirtualNormal | 165.8 ns | 2.225 ns | 2.082 ns | | |
/// NonVirtualFast | 161.2 ns | 2.208 ns | 2.065 ns | | |
/// VirtualNormal | 449.6 ns | 2.595 ns | 2.300 ns | | |
/// VirtualFast | 271.3 ns | 2.338 ns | 2.072 ns | | |
/// | |
/// non-virtual な場合(具象型を直接渡す場合)はどの道インライン化で最適化がかかるのでそんなに差が出ない。 | |
/// | |
/// 問題は virtual に呼んだ場合(インターフェイスを介して呼んだ)で、4割くらい差が出る。 | |
/// 今回の場合、MoveNext/Current/TryMoveNext の呼び出し以外にやってることがほとんどないので、virtual call の負担の差がはっきりと出る(たぶん上限)。 | |
/// あと、MoveNext/Current の場合、インデックスの範囲チェック(i < length)とアクセス(data[i])がわかれることで、配列の最適化が効きにくくなってるはず。 | |
/// </summary> | |
public class ForeachBenchmark | |
{ | |
int[] _data; | |
[GlobalSetup] | |
public void Setup() | |
{ | |
_data = Enumerable.Range(0, 100).ToArray(); | |
} | |
[Benchmark] | |
public int NonVirtualNormal() => NonVirtualSum(new NormalEnumerator(_data)); | |
[Benchmark] | |
public int NonVirtualFast() => NonVirtualSum(new FastEnumerator(_data)); | |
[Benchmark] | |
public int VirtualNormal() => VirtualSum(new NormalEnumerator(_data)); | |
[Benchmark] | |
public int VirtualFast() => VirtualSum(new FastEnumerator(_data)); | |
[MethodImpl(MethodImplOptions.NoInlining)] | |
static int NonVirtualSum(NormalEnumerator e) | |
{ | |
var sum = 0; | |
while (e.MoveNext()) | |
{ | |
var x = e.Current; | |
sum += x; | |
} | |
return sum; | |
} | |
[MethodImpl(MethodImplOptions.NoInlining)] | |
static int NonVirtualSum(FastEnumerator e) | |
{ | |
var sum = 0; | |
while (true) | |
{ | |
var x = e.TryMoveNext(out var success); | |
if (!success) break; | |
sum += x; | |
} | |
return sum; | |
} | |
[MethodImpl(MethodImplOptions.NoInlining)] | |
static int VirtualSum(IEnumerator<int> e) | |
{ | |
var sum = 0; | |
while (e.MoveNext()) | |
{ | |
var x = e.Current; | |
sum += x; | |
} | |
return sum; | |
} | |
[MethodImpl(MethodImplOptions.NoInlining)] | |
static int VirtualSum(IFastEnumerator<int> e) | |
{ | |
var sum = 0; | |
while (true) | |
{ | |
var x = e.TryMoveNext(out var success); | |
if (!success) break; | |
sum += x; | |
} | |
return sum; | |
} | |
} | |
class Program | |
{ | |
static void Main() | |
{ | |
BenchmarkRunner.Run<ForeachBenchmark>(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment