Почему Enumerable.Range быстрее, чем цикл прямого выхода? - PullRequest
Новая
       33

Почему Enumerable.Range быстрее, чем цикл прямого выхода?

11 голосов
/ 03 января 2009

Приведенный ниже код проверяет производительность трех разных способов сделать одно и то же решение. 

    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 принимает больше вызовов методов. Однако меня действительно удивляет, что Enumerable.Range работает быстрее, чем самодельный IEnumerable. Я думал, что Enumerable.Range будет иметь больше издержек, чем простой метод GetIntRange.

Каковы возможные причины этого?

Ответы [ 4 ]

11 голосов
/ 03 января 2009

Почему 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 со следующей реализацией (конечно, как указывает Роб, компилировать в режиме выпуска). Эта реализация может быть немного оптимизирована относительно того, что компилятор будет генерировать из блока итератора. 

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; } }
    }
}
5 голосов
/ 03 января 2009

Я предполагаю, что вы работаете в отладчике. Вот мои результаты, собрав из командной строки команду "/ o + / debug -" 

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

Есть небольшая разница, но она не так выражена. Реализации блоков итераторов не так эффективны, как индивидуальные решения, но они довольно хороши.

4 голосов
/ 03 января 2009

Предполагается, что это сборка релиза, иначе все сравнения отключены, поскольку JIT не будет работать без изменений.

Вы можете посмотреть на сборку с помощью рефлектора и посмотреть, что также расширяет оператор yield. Компилятор будет создавать класс для инкапсуляции итератора. Возможно, в сгенерированном коде происходит больше служебной работы, чем в реализации Enumerable.Range, которая, вероятно, написана вручную

2 голосов
/ 29 мая 2010

Небольшая разница в выходных данных рефлектора (а также проверка аргументов и дополнительный уровень интернализации здесь не имеют значения). Основной код больше похож на: 

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

То есть вместо другой локальной переменной они применяют дополнительное прибавление к каждому доходу.

Я пытался это сравнить, но не могу остановить достаточно внешних процессов, чтобы получить понятные результаты. Я также дважды пробовал каждый тест, чтобы игнорировать эффекты JIT-компилятора, но даже у этого есть «интересные» результаты.

Вот пример моих результатов: 

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
...