Enumerable.Rangeが直接的なyieldループよりも速いのはなぜですか?
-
03-07-2019 - |
質問
以下のコードは、同じソリューションを実行する3つの異なる方法のパフォーマンスをチェックしています。
public static void Main(string[] args)
{
// for loop
{
Stopwatch sw = Stopwatch.StartNew();
int accumulator = 0;
for (int i = 1; i <= 100000000; ++i)
{
accumulator += i;
}
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, accumulator);
}
//Enumerable.Range
{
Stopwatch sw = Stopwatch.StartNew();
var ret = Enumerable.Range(1, 100000000).Aggregate(0, (accumulator, n) => accumulator + n);
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, ret);
}
//self-made IEnumerable<int>
{
Stopwatch sw = Stopwatch.StartNew();
var ret = GetIntRange(1, 100000000).Aggregate(0, (accumulator, n) => accumulator + n);
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, ret);
}
}
private static IEnumerable<int> GetIntRange(int start, int count)
{
int end = start + count;
for (int i = start; i < end; ++i)
{
yield return i;
}
}
}
結果は次のとおりです。
time = 306; result = 987459712
time = 1301; result = 987459712
time = 2860; result = 987459712
「forループ」がEnumerable.Aggregateはより多くのメソッド呼び出しを行うため、他の2つのソリューションよりも高速です。しかし、「Enumerable.Range」が本当に驚いた。 「自作IEnumerable」よりも高速です。 Enumerable.Rangeは、単純なGetIntRangeメソッドよりもオーバーヘッドが大きいと考えました。
これの考えられる理由は何ですか?
解決
Enumerable.Range
が自作の GetIntRange
よりも遅いのはなぜですか?実際、 Enumerable.Range
が次のように定義されている場合
public static class Enumerable {
public static IEnumerable<int> Range(int start, int count) {
var end = start + count;
for(var current = start; current < end; ++current) {
yield return current;
}
}
}
その後、自作の GetIntRange
とまったく同じ速度で動作するはずです。これは実際には Enumerable.Range
のリファレンス実装であり、コンパイラまたはプログラマー側のトリックはありません。
GetIntRange
および System.Linq.Enumerable.Range
を次の実装と比較することもできます(もちろん、Robが指摘しているように、リリースモードでコンパイルします) 。この実装は、コンパイラーがイテレーターブロックから生成するものに関してわずかに最適化される場合があります。
public static class Enumerable {
public static IEnumerable<int> Range(int start, int count) {
return new RangeEnumerable(start, count);
}
private class RangeEnumerable : IEnumerable<int> {
private int _Start;
private int _Count;
public RangeEnumerable(int start, int count) {
_Start = start;
_Count = count;
}
public virtual IEnumerator<int> GetEnumerator() {
return new RangeEnumerator(_Start, _Count);
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
}
private class RangeEnumerator : IEnumerator<int> {
private int _Current;
private int _End;
public RangeEnumerator(int start, int count) {
_Current = start - 1;
_End = start + count;
}
public virtual void Dispose() {
_Current = _End;
}
public virtual void Reset() {
throw new NotImplementedException();
}
public virtual bool MoveNext() {
++_Current;
return _Current < _End;
}
public virtual int Current { get { return _Current; } }
object IEnumerator.Current { get { return Current; } }
}
}
他のヒント
あなたはデバッガで実行していると思います。コマンドラインから&quot; / o + / debug-&quot;
を使用してビルドした結果を次に示します。time = 142; result = 987459712
time = 1590; result = 987459712
time = 1792; result = 987459712
まだわずかな違いがありますが、それほど顕著ではありません。イテレータブロックの実装は、オーダーメイドのソリューションほど効率的ではありませんが、かなり優れています。
リリースビルドが実行されていると仮定すると、JITが完全に機能しないため、すべての比較はオフになります。
リフレクターでアセンブリを見ると、 'ステートメントも展開されています。コンパイラは、イテレータをカプセル化するクラスを作成します。生成されたコードでは、手作業でコーディングされている可能性が高いEnumerable.Rangeの実装よりも多くのハウスキーピングが行われている可能性があります
Reflectorの出力にわずかな違いがあります(また、引数のチェックと内部化の追加レベルもここではまったく関係ありません)。基本的なコードは次のようなものです。
public static IEnumerable<int> Range(int start, int count) {
for(int current = 0; current < count; ++current) {
yield return start + current;
}
}
つまり、別のローカル変数の代わりに、すべてのyieldに対して追加の追加を適用します。
これをベンチマークしようとしましたが、十分な外部プロセスを停止して理解できる結果を得ることができません。また、JITコンパイラの影響を無視するために各テストを2回試みましたが、それでも「興味深い」結果が得られます。
ここに私の結果のサンプルがあります:
Run 0: time = 4149; result = 405000000450000000 time = 25645; result = 405000000450000000 time = 39229; result = 405000000450000000 time = 29872; result = 405000000450000000 time = 4277; result = 405000000450000000 time = 26878; result = 405000000450000000 time = 26333; result = 405000000450000000 time = 26684; result = 405000000450000000 Run 1: time = 4063; result = 405000000450000000 time = 22714; result = 405000000450000000 time = 34744; result = 405000000450000000 time = 26954; result = 405000000450000000 time = 4033; result = 405000000450000000 time = 26657; result = 405000000450000000 time = 25855; result = 405000000450000000 time = 25031; result = 405000000450000000 Run 2: time = 4021; result = 405000000450000000 time = 21815; result = 405000000450000000 time = 34304; result = 405000000450000000 time = 32040; result = 405000000450000000 time = 3993; result = 405000000450000000 time = 24779; result = 405000000450000000 time = 29275; result = 405000000450000000 time = 32254; result = 405000000450000000
およびコード
using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
namespace RangeTests
{
class TestRange
{
public static void Main(string[] args)
{
for(int l = 1; l <= 2; ++l)
{
const int N = 900000000;
System.GC.Collect(2);
// for loop
{
Stopwatch sw = Stopwatch.StartNew();
long accumulator = 0;
for (int i = 1; i <= N; ++i)
{
accumulator += i;
}
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, accumulator);
}
System.GC.Collect(2);
//Enumerable.Range
{
Stopwatch sw = Stopwatch.StartNew();
var ret = Enumerable.Range(1, N).Aggregate(0, (long accumulator,int n) => accumulator + n);
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, ret);
}
System.GC.Collect(2);
//self-made IEnumerable<int>
{
Stopwatch sw = Stopwatch.StartNew();
var ret = GetIntRange(1, N).Aggregate(0, (long accumulator,int n) => accumulator + n);
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, ret);
}
System.GC.Collect(2);
//self-made adjusted IEnumerable<int>
{
Stopwatch sw = Stopwatch.StartNew();
var ret = GetRange(1, N).Aggregate(0, (long accumulator,int n) => accumulator + n);
sw.Stop();
Console.WriteLine("time = {0}; result = {1}", sw.ElapsedMilliseconds, ret);
}
System.GC.Collect(2);
Console.WriteLine();
} }
private static IEnumerable<int> GetIntRange(int start, int count)
{
int end = start + count;
for (int i = start; i < end; ++i)
{
yield return i;
}
}
private static IEnumerable<int> GetRange(int start, int count)
{
for (int i = 0; i < count; ++i)
{
yield return start + i;
}
}
} }
コンパイル済み
csc.exe -optimize+ -debug- RangeTests.cs