Why is Enumerable.Range faster than a direct yield loop?

Question

The code below is checking performance of three different ways to do same solution.

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

The results are:

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

It is not surprising that the "for loop" is faster than the other two solutions, because Enumerable.Aggregate takes more method invocations. However, it really surprises me that "Enumerable.Range" is faster than the "self-made IEnumerable". I thought that Enumerable.Range would have more overhead than the simple GetIntRange method.

What are the possible reasons for this?

Answer 1

Assuming this is a release build running, otherwise all comparisons are off as the JIT will not be working flat out.

You could look at the assembly with reflector and see what the 'yield' statement is being expanded too. The compiler will be creating a class to encapsulate the iterator. Maybe there is more housekeeping going on in the generated code than the implementation of Enumerable.Range which is likely hand-coded

Answer 2

Why should Enumerable.Range be any slower than your self-made GetIntRange? In fact, if Enumerable.Range were defined as

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

then it should be exactly as fast as your self-made GetIntRange. This is in fact the reference implementation for Enumerable.Range, absent any tricks on the part of the compiler or programmer.

You may want to compare your GetIntRange and System.Linq.Enumerable.Range with the following implementation (of course, compile in release mode, as Rob points out). This implementation may be slightly optimized with respect to what a compiler would generate from an iterator block.

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 3

My guess is that you're running in a debugger. Here are my results, having built from the command line with "/o+ /debug-"

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

There's still a slight difference, but it's not as pronounced. Iterator block implementations aren't quite as efficient as a tailor-made solution, but they're pretty good.

Answer 4

A slight difference in the Reflector output (as well as the argument check and extra level of internalisation definitely not relevant here). The essential code is more like:

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

That is, instead of another local variable, they apply an extra addition for every yield.

I have tried to benchmark this, but I can't stop enough external processes to get understandable results. I also tried each test twice to ignore the effects of the JIT compiler, but even that has 'interesting' results.

Here's a sample of my results:

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

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

compiled with

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