Warum ist Enumerable.Range schneller als eine direkte Rendite Schleife?

Question

Der folgende Code prüft die Leistung von drei verschiedenen Arten derselben Lösung zu tun.

    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;
        }
    }
}

Die Ergebnisse sind:

time = 306; result = 987459712
time = 1301; result = 987459712
time = 2860; result = 987459712

Es ist nicht verwunderlich, dass die „for-Schleife“ ist schneller als die beiden anderen Lösungen, weil Enumerable.Aggregate mehr Methodenaufrufe nimmt. Aber es überrascht mich wirklich, dass „Enumerable.Range“ ist schneller als die „selbstgemachte IEnumerable“. Ich dachte, dass Enumerable.Range würde mehr Aufwand als die einfache GetIntRange Methode hat.

Was sind die möglichen Gründe dafür?

Answer 1

Warum jeder langsamer als selbstgemachte Enumerable.Range GetIntRange sein sollte? In der Tat wurde, wenn Enumerable.Range definiert als

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;
        }
    }
}

, dann sollte es genau so schnell, wie Ihr selbst gemacht GetIntRange sein. Dies ist in der Tat die Referenzimplementierung für Enumerable.Range, fehlen irgendwelche Tricks auf dem Teil des Compilers oder Programmierer.

Sie möchten Ihre GetIntRange und System.Linq.Enumerable.Range mit der folgenden Umsetzung vergleichen (natürlich im Release-Modus kompilieren, als Rob weist darauf hin). Diese Implementierung kann leicht mit Bezug auf optimiert werden, was ein Compiler aus einem Iteratorblock erzeugen würde.

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; } }
    }
}

Answer 2

Meine Vermutung ist, dass Sie in einem Debugger ausführen. Hier sind meine Ergebnisse, nachdem sie von der Kommandozeile gebaut mit „/ o + / debug -“

time = 142; result = 987459712
time = 1590; result = 987459712
time = 1792; result = 987459712

Es gibt immer noch einen kleinen Unterschied, aber es ist nicht so ausgeprägt. Iteratorblock Implementierungen sind nicht ganz so effizient wie eine maßgeschneiderte Lösung, aber sie sind ziemlich gut.

Answer 3

Unter der Annahme, dies ist ein Release-Build ausgeführt wird, da sonst alle Vergleiche ausgeschaltet sind, wie der JIT nicht flach aus arbeiten.

Sie können bei der Montage aussehen mit Reflektor und sehen, was die ‚Ausbeute 'Aussage wird auch erweitert. Der Compiler wird eine Klasse werden die Erstellung der Iterator zu verkapseln. Vielleicht gibt es mehr Hausarbeit in den generierten Code geht als die Umsetzung von Enumerable.Range, die wahrscheinlich von Hand codiert

ist

Answer 4

Ein geringfügiger Unterschied in dem Reflektor-Ausgang (sowie das Argument Prüfung und zusätzliche Ebene der Internalisierung auf jedem Fall hier nicht relevant). Der wesentliche Code ist mehr wie:

public static IEnumerable<int> Range(int start, int count) {
    for(int current = 0; current < count; ++current) {
        yield return start + current;
    }
}

Das heißt, anstelle eines anderen lokalen Variablen, sie gelten eine zusätzliche Ergänzung für jede Ausbeute.

Ich habe Benchmark versucht, aber ich kann nicht genug externe Prozesse stoppen, um verständliche Ergebnisse zu erzielen. Ich habe auch versucht jeden Test zweimal die Auswirkungen der JIT-Compiler zu ignorieren, aber auch das hat ‚interessant‘ Ergebnisse.

Hier ist eine Probe meiner Ergebnisse:

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

und der Code

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;
        }
    }
} }

kompiliert mit

csc.exe -optimize+ -debug- RangeTests.cs