ToArrayを高速化する話
IEnumerable
https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,ed118118b642d9d4
要素数が分かるICollectionと分からないIEnumerableで実装を分けるのは実に合理的です。 このやり方が最速であるかというとIEnumerable側の実装については幾つか改善余地があります。 主に配列の初期値と拡張時の倍率です。
ベンチマークの結果は以下の通りです。大体、20%高速化していると考えられます。
Method | Mean | Error | StdDev |
---|---|---|---|
ToArrayFast | 134.3 us | 0.5700 us | 0.5053 us |
ToArray | 160.7 us | 0.7790 us | 0.7287 us |
ベンチマークのソースは以下のようになります。Guidの生成時間が計算に含められないように、あらかじめ作っておきます。
private class GuidGenerator : IEnumerable<Guid> { private readonly Guid[] _guids = new Guid[10000]; public GuidGenerator() { for (int idx = 0; idx < _guids.Length; idx++) _guids[idx] = System.Guid.NewGuid(); } public IEnumerator<Guid> GetEnumerator() { for (int idx = 0; idx < _guids.Length; idx++) yield return _guids[idx]; } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } private readonly GuidGenerator _guids = new GuidGenerator(); [Benchmark] public void ToArrayFast() { var items = _guids.ToArrayFast(); } [Benchmark] public void ToArray() { var items = _guids.ToArray(); }
実装はこちらです。
public static class CollectionExtensions { public static T[] ToArrayFast<T>(this IEnumerable<T> items) where T : struct => new Buffer<T>(items).ToArray(); } internal struct Buffer<TElement> { private const int InitialBufferSize = 64; private const int ExpandRatio = 4; private readonly int _count; private readonly TElement[] _items; public Buffer(IEnumerable<TElement> source) { if (source is ICollection<TElement> collection) { _count = collection.Count; if (_count == 0) { _items = Array.Empty<TElement>(); } else { _items = new TElement[_count]; collection.CopyTo(_items, 0); } } else { _count = 0; _items = new TElement[InitialBufferSize]; foreach (var item in source) { if (_items.Length == _count) Array.Resize(ref _items, _count * ExpandRatio); _items[_count++] = item; } if (_count == 0) _items = Array.Empty<TElement>(); else if (_items.Length != _count) Array.Resize(ref _items, _count); } } public TElement[] ToArray() => _items; }
細微な部分ではまだ最適化余地が残っていますが、要点は如何にして Array.Copy や Array.Resize を呼び出す頻度を下げるか、ということになります。
言い換えると過剰なメモリを確保したりGCが過度に働かないか、ということになります。
最後に確定するバッファ以外のメモリは全てGen0であることと、メモリの確保回数は通常のToArrayより少ないことを考えれば瞬間で僅かに大きいメモリを持ったとしても問題ではありません。
なお、ここで少し考慮すべきポイントは確保したメモリは0Fillされる分だけメモリ書き込みが発生するという事です。 加えて大きすぎるとLOH(Large Object Heap / 85000バイト以上のバッファ)化してなお性質の悪いことになります。
Array.Resizeを減らしたいからといって突然大きくするとそれはそれでトータルでは性能を損ないます。
計測と分析を要する箇所です。
# C#7.3にふさわしいやり方もいろいろ検討してみたのですが、自分のやった範囲では何をしても遅くなりました。誰かアイデアありませんか?