Как ускорить yield return?
От: eugals Россия  
Дата: 22.02.10 14:17
Оценка: 2 (1)
Привет, я тут решил потестировать скорость обхода списка с помощью различных конструкций.

Исходный код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Test
{
    public static class ListExt
    {
        public static void Walk<T>(this List<T> source, Action<T> predicate)
        {
            foreach (var v in source)
                predicate(v);
        }

        public static IEnumerable<T> Walk<T>(this List<T> source)
        {
            foreach (var v in source)
                yield return v;
        }
    }

    class Program
    {
        public static void Test(string desc, Action act)
        {
            var watch = new Stopwatch();
            GC.Collect();
            watch.Start();
            for (int i = 0; i < 300; ++i)
                act();
            watch.Stop();
            Console.WriteLine("{0}: {1}", desc, watch.ElapsedMilliseconds);
        }

        static void Main(string[] args)
        {
            int n = 50000;
            var list = new List<long>(n);
            for (int i = 0; i < n; ++i)
                list.Add(i);

            long sum;

            sum = 0;
            Test("Plain 'Sum' ", delegate()
            {
                sum = list.Sum();
            });

            sum = 0;
            Test("foreach     ", delegate()
            {
                foreach (var v in list)
                    sum += v;
            });

            sum = 0;
            Test("for         ", delegate()
            {
                for (int i = 0; i < list.Count; ++i)
                    sum += list[i];
            });

            Test("Linq+Sum    ", delegate()
            {
                sum = (from x in list select x).Sum();
            });

            //Test("Linq        ", delegate()
            //{
            //    (from l in list where (sum += l) < 0 select l); 
            //});

            sum = 0;
            Action<long> visitor = delegate(long x) { sum += x; };
            Test("visitor     ", delegate()
            {
                list.Walk(visitor);
            });

            sum = 0;
            Test("co-procedure", delegate()
            {
                foreach (var x in list.Walk())
                    sum += x;
            });
        }
    }
}


Результаты получились такие (VS2008/Release с оптимизацией кода):

Plain 'Sum' : ~150-200
foreach     : ~71-75
for         : ~45
Linq+Sum    : ~350
visitor     : ~87
co-procedure: ~209


Собственно, весь заезд затевался только для сравнения делегатов и сопроцедур (последние две строчки в результатах).
Как видим, yield return оказался больше чем в два раза медленнее (вероятно оптимизатор как-то занлайнил вызов делегата).

Вопрос, нет ли у обчества каких либо соображений как можно заставить сопроцедуры работать быстрее?
Re: Как ускорить yield return?
От: Воронков Василий Россия http://elalang.net
Дата: 22.02.10 15:07
Оценка: +1 -1
Здравствуйте, eugals, Вы писали:

E>Результаты получились такие (VS2008/Release с оптимизацией кода):


E>
E>Plain 'Sum' : ~150-200
E>foreach     : ~71-75
E>for         : ~45
E>Linq+Sum    : ~350
E>visitor     : ~87
E>co-procedure: ~209
E>



Что-то вы вообще не то намерили. Во-первых в таких тестах расходы на вызов делегата, который вы используете при тестировании, могут вносить очень сильный шум в итоговые замеры. И то, что у вас в итоге получилось вызывает большие вопросы.

Например, Plain 'Sum' — это вообще-то метод расширения, определенный специально для IEnumerable<Int32> и IEnumerable<Int64>, внутри которого совершается банальный foreach с суммированием. Теперь посмотрите на свои цифры и скажите, откуда такая разница с просто foreach. Ее просто не должно быть. А это автоматически ставит под сомнение все остальные цифры.

Переделайте тест, попробуйте запускайть его в дебаг билде.
Ela, functional language
Re: Как ускорить yield return?
От: Пельмешко Россия blog
Дата: 22.02.10 15:31
Оценка: 9 (2)
Здравствуйте, eugals, Вы писали:

E>Как видим, yield return оказался больше чем в два раза медленнее (вероятно оптимизатор как-то занлайнил вызов делегата).


1. Запомните на ближайшее будущее, что косвенные вызовы не инлайнятся!!! Это относится и к виртуальным функциям, и к делегатам.
2. Посмотрите рефлектором на преобразование, которое выполняется компилятором C# для создания итератора. State-машина конечно же будет медленнее чем просто foreach + вызовы делегата. К тому же foreach по List<T> быстрее, чем foreach по IEnumerable<T>

E>Вопрос, нет ли у обчества каких либо соображений как можно заставить сопроцедуры работать быстрее?


В C# итераторы никак не ускоришь, единственное возможное улучшение в будущих версиях языка — yield many (yield! в F#), которые позволит вместо:
foreach (var v in source)
    yield return v;
делать:
yield many source;
что снизит алгоритмическую сложность перебора подобных итераторов...

Соответственно, если итераторы Вас не устраивают по скорости, то просто стоит отказаться от их использования
Re[2]: Как ускорить yield return?
От: eugals Россия  
Дата: 22.02.10 16:22
Оценка:
Здравствуйте, Пельмешко, Вы писали:

спасибо за ответ.

П>В C# итераторы никак не ускоришь, единственное возможное улучшение в будущих версиях языка — yield many

А оно скоро будет? Можно ссылочку где про него было?
Re[2]: Как ускорить yield return?
От: eugals Россия  
Дата: 22.02.10 16:35
Оценка: +1
Здравствуйте, Воронков Василий, Вы писали:

ВВ>Во-первых в таких тестах расходы на вызов делегата, который вы используете при тестировании, могут вносить очень сильный шум в итоговые замеры.

Сомневаюсь, что вызов одного несчастного делегата как-то скажется по сравнению с циклом по 50000 элементам.
Впрочем, я пробовал и без этого делегата — результаты те же.


ВВ>Например, Plain 'Sum' — это вообще-то метод расширения, определенный специально для IEnumerable<Int32> и IEnumerable<Int64>, внутри которого совершается банальный foreach с суммированием.

Это мне известно.
ВВ>Теперь посмотрите на свои цифры и скажите, откуда такая разница с просто foreach.
Предполагаю, что оптимизатор (или JIT) просто не смог этот экстеншн качественно проинлайнить.
ВВ>Ее просто не должно быть.
И тем не менее результат налицо. Полные исходники у всех перед глазами — можете запустить у себя, если не верите моим замерам.


ВВ>Переделайте тест, попробуйте запускайть его в дебаг билде.

Меня не интересуют "стерильные" результаты полученные под дебагом. Я взял конкретный код, вполне корректный код, собрал его с конкретными (вполне рациональными) опциями компилятора и получил те значения, которые получил.
Re[3]: Как ускорить yield return?
От: Пельмешко Россия blog
Дата: 22.02.10 16:46
Оценка: 14 (2)
Здравствуйте, eugals, Вы писали:

E>А оно скоро будет? Можно ссылочку где про него было?


В C# 4.0 точно не будет и дальше неизвестно, но это достаточно популярный feature request, вроде в 4.0 просто не успели.

Хороший пост про данную проблему: Wes Dyer &mdash; All About Iterators.

Там можно обнаружить ссылку на данный paper, в котором проблема обсуждается более "матанисто" и предлагается реализация:
Bart Jacobs, Erik Meijer, Frank Piessens, and Wolfram Schulte &mdash; Iterators revisited: proof rules and implementation
Re[3]: Как ускорить yield return?
От: Воронков Василий Россия http://elalang.net
Дата: 22.02.10 16:50
Оценка:
Здравствуйте, eugals, Вы писали:

ВВ>>Теперь посмотрите на свои цифры и скажите, откуда такая разница с просто foreach.

E>Предполагаю, что оптимизатор (или JIT) просто не смог этот экстеншн качественно проинлайнить.

Это как? Статический вызов не был заинлайнен, и из-за этого производительности упала в три раза? При этом "вызов одного несчастного делегата как-то скажется по сравнению с циклом по 50000 элементам". Интересная у вас логика.

ВВ>>Переделайте тест, попробуйте запускайть его в дебаг билде.

E>Меня не интересуют "стерильные" результаты полученные под дебагом. Я взял конкретный код, вполне корректный код, собрал его с конкретными (вполне рациональными) опциями компилятора и получил те значения, которые получил.

Вот только вы в действительности и получили самый что ни на есть "стерильный" результат, от которого на практике пользы 0.0. Ибо в реальном коде между Sum и аналогичным foreach не будет сколько-нибудь заметной разницы.
Ela, functional language
Re[3]: Как ускорить yield return?
От: TK Лес blogs.gotdotnet.ru
Дата: 22.02.10 17:40
Оценка:
Здравствуйте, eugals, Вы писали:

П>>В C# итераторы никак не ускоришь, единственное возможное улучшение в будущих версиях языка — yield many

E>А оно скоро будет? Можно ссылочку где про него было?

Без изменения существующих интерфейсов такое нормально работать не будет.
А если менять интерфейсы то, только вместе с runtime. т.е в ближайшие лет 5-6 этого ждать не стоит.
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re[4]: Как ускорить yield return?
От: Sinix  
Дата: 22.02.10 18:32
Оценка:
Здравствуйте, TK, Вы писали:

TK>Без изменения существующих интерфейсов такое нормально работать не будет.

TK>А если менять интерфейсы то, только вместе с runtime. т.е в ближайшие лет 5-6 этого ждать не стоит.
Ну почему же? Всегда можно заменить yield many на foreach...yield return). Правда я вообще не представляю, как yield many может повлиять на производительность.
Re[4]: Как ускорить yield return?
От: Пельмешко Россия blog
Дата: 22.02.10 18:32
Оценка: 13 (2)
Здравствуйте, TK, Вы писали:

TK>Без изменения существующих интерфейсов такое нормально работать не будет.

TK>А если менять интерфейсы то, только вместе с runtime. т.е в ближайшие лет 5-6 этого ждать не стоит.

Это почему же?

Ничего не надо менять, преобразование только в компиляторе, runtime никаким местом не надо менять, Вы бы хоть ознакомились сначала с paper, там описано как уже сейчас руками можно сделать реализацию yield foreach, включая оптимизацию хвостовых yield foreach.

Можно обойтись без поддержки со стороны BCL вообще, но всё же код таких итераторов можно неплохо переиспользовать — достаточно добавить в BCL один класс (публичный, к сожалению) и спрятать его подальше (в F# это класс Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase<T>, а генерируемые компилятором классы-итераторы являются его наследниками). И всё, никаких breaking changes, никакие интерфейсы менять не надо, старый код будет компилироваться в итераторы старого образца (фактически новые нужны только при использовании yield foreach), даже синтаксису ничего не мешает — сейчас токены "yeild" и "foreach", следующие друг за другом, не имеют какого-либо значения.

Так о каких изменениях существующих интерфейсов Вы говорите?
Re[5]: Как ускорить yield return?
От: Пельмешко Россия blog
Дата: 22.02.10 18:51
Оценка: 9 (1)
Здравствуйте, Sinix, Вы писали:

S> Правда я вообще не представляю, как yield many может повлиять на производительность.


Вот так:
http://blogs.msdn.com/blogfiles/wesdyer/WindowsLiveWriter/TheCostofIterators_A895/image031.png

Попробуйте на нынешних итераторах что-нибудь сильно рекурсивное написать, тогда может даже невооружённым глазом заметна будет разница

Образно говоря, с yield return получается, что внутри итератора стек из специальных энумераторов, которые могут вернуть либо значение, либо энумератор (либо ещё хвостовой энумератор). Если на MoveNext() энумератор возвращает энумератор, то его запихивают в вершину стека и перебирают дальше его. По завершению перебора энумератор выбрасывается из вершины стека и перебор продолжается, если в стеке есть ещё энумераторы.

То есть если у Вас сейчас итератор вызвал сам себя (или другой итератор) 1000 раз, то чтобы получить очередное значение, надо добраться до энумератора, который вложен в 1000 экземпяров итераторов — MoveNext() и get_Current() будет вызваны 1000 раз... А у yield return-итератора нужный энумератор всегда лежит на вершине стека, один MoveNext() считай...

На графике у итератора квадратичная сложность, но я что-то не догоняю почему
Re[4]: Как ускорить yield return?
От: eugals Россия  
Дата: 22.02.10 19:04
Оценка:
Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, eugals, Вы писали:


E>>Предполагаю, что оптимизатор (или JIT) просто не смог этот экстеншн качественно проинлайнить.

ВВ>Это как? Статический вызов не был заинлайнен, и из-за этого производительности упала в три раза?
Читайте внимательнее пожалуйста, я написал не "заинлайнен", а "проинлайнен". То есть, оптимизатор не сумел упростить внутренности Sum<>, возможно потому, что оно реализовано в другой сборке.

ВВ>Вот только вы в действительности и получили самый что ни на есть "стерильный" результат, от которого на практике пользы 0.0.

Это слишком сильное утверждение. Практика бывает разная. В Вашей практите может и 0.0. А моей приведенные пример вполне осмысленны.
Re[6]: Как ускорить yield return?
От: Пельмешко Россия blog
Дата: 22.02.10 19:06
Оценка:
Здравствуйте, Пельмешко, Вы писали:

Упс, ошибся:

П>Образно говоря, с yield foreach получается, что внутри итератора стек из специальных энумераторов...

П>А у yield foreach-итератора нужный энумератор всегда лежит на вершине стека, один MoveNext() считай...

Btw, ну ведь красота же:
let rec fromTo x y =
    seq { if x <= y then
             yield  x
             yield! fromTo (x+1) y }
Re[5]: Как ускорить yield return?
От: Воронков Василий Россия http://elalang.net
Дата: 22.02.10 19:19
Оценка: -2
Здравствуйте, eugals, Вы писали:

E>>>Предполагаю, что оптимизатор (или JIT) просто не смог этот экстеншн качественно проинлайнить.

ВВ>>Это как? Статический вызов не был заинлайнен, и из-за этого производительности упала в три раза?
E>Читайте внимательнее пожалуйста, я написал не "заинлайнен", а "проинлайнен". То есть, оптимизатор не сумел упростить внутренности Sum<>, возможно потому, что оно реализовано в другой сборке.

Ну, видимо, дело в том, что такой термин как "проинлайнен", причем кардинально отличающийся по смыслу от "заинлайнен", я слышу впервые.
И что же, кстати говоря, в этом коде можно "проинлайнить", кроме раскрытия foreach в for? Пример такого упрощения можете провести? А может стоит проще поступить — сравнить IL вашего метода и Sum?

ВВ>>Вот только вы в действительности и получили самый что ни на есть "стерильный" результат, от которого на практике пользы 0.0.

E>Это слишком сильное утверждение. Практика бывает разная. В Вашей практите может и 0.0. А моей приведенные пример вполне осмысленны.

И в чем же заключается ваша практика? В написании бессмысленных примеров?
Ela, functional language
Re[5]: Как ускорить yield return?
От: TK Лес blogs.gotdotnet.ru
Дата: 22.02.10 23:34
Оценка:
Здравствуйте, Пельмешко, Вы писали:

П>Ничего не надо менять, преобразование только в компиляторе, runtime никаким местом не надо менять, Вы бы хоть ознакомились сначала с paper, там описано как уже сейчас руками можно сделать реализацию yield foreach, включая оптимизацию хвостовых yield foreach.


А у нас теперь один компилятор на всех?

П>Так о каких изменениях существующих интерфейсов Вы говорите?


Так, введение GeneratedSequenceBase<T> вместо IEnumerable<T> фактически и есть подобное изменение... Его надо либо возвращать всем либо, решение будет "неполноценным". Такой интерфейс должен быть часть BCL, а не "приблудой" одного из компиляторов...
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re[6]: RE: TraceSource
От: Пельмешко Россия blog
Дата: 23.02.10 01:26
Оценка:
Здравствуйте, TK, Вы писали:
TK>Здравствуйте, Пельмешко, Вы писали:
П>>Ничего не надо менять, преобразование только в компиляторе, runtime никаким местом не надо менять, Вы бы хоть ознакомились сначала с paper, там описано как уже сейчас руками можно сделать реализацию yield foreach, включая оптимизацию хвостовых yield foreach.
TK>А у нас теперь один компилятор на всех?

Вы о чем? Итераторы с yield! из F# и сейчас прекрасно можно использовать в C#, они же возвращают IEnumerable<T> и тому языку, который их будет перебирать, глубоко наплевать как они внутри там работают.
П>>Так о каких изменениях существующих интерфейсов Вы говорите?
TK>Так, введение GeneratedSequenceBase<T> вместо IEnumerable<T> фактически и есть подобное изменение... Его надо либо возвращать всем либо, решение будет "неполноценным". Такой интерфейс должен быть часть BCL, а не "приблудой" одного из компиляторов...

Это не интерфейс. Рискну предположить, что Вы меня так и не поняли...
class GeneratedSequenceBase<T> : IEnumerable<T>, IEnumerator<T>
...то есть выглядит так же, как ныняшний класс со state-машиной, генерируемый для yield return. Эти генерируемые классы приватные и вложенные, наружу он возвращаются приведенными к IEnumerable<T>. В случае yield foreach-итератором будит абсолютно то же самое, наружу лишь IEnumerable<T>!

Класс GeneratedSequenceBase<T> может быть использован компилятором закулисами лишь для yield foreach итераторов, чтобы меньше кода генерировать, а публичным он должен быть чтобы компилятор мог от него унаследоваться из других сборок, генерируя класс-итератор. Юзер никогда этот GeneratedSequenceBase<T> скорее всего и не увидит
Re[7]: Как ускорить yield return?
От: Аноним  
Дата: 23.02.10 02:31
Оценка:
Здравствуйте, Пельмешко, Вы писали:

П>Btw, ну ведь красота же:

П>
П>let rec fromTo x y =
П>    seq { if x <= y then
П>             yield  x
П>             yield! fromTo (x+1) y }
П>


Интересно, как можно вот такую красоту сохранить, а варнинг (о рекурсивной ссылке на не-функцию) убрать?
let rec fib = Seq.cache <| seq {
    yield 0I
    yield 1I
    yield! Seq.map2 (+) fib (Seq.skip 1 fib )}
Re[6]: Как ускорить yield return?
От: Sinix  
Дата: 23.02.10 04:56
Оценка:
Здравствуйте, Пельмешко, Вы писали:

П>Здравствуйте, Sinix, Вы писали:


S>> Правда я вообще не представляю, как yield many может повлиять на производительность.


П>Вот так:


Дык это ж бубль гум хвостовая рекурсия. И обходится оно, как всегда, заведением собственного стека.

П>То есть если у Вас сейчас итератор вызвал сам себя (или другой итератор) 1000 раз, то чтобы получить очередное значение, надо добраться до энумератора, который вложен в 1000 экземпяров итераторов — MoveNext() и get_Current() будет вызваны 1000 раз... А у yield return-итератора нужный энумератор всегда лежит на вершине стека, один MoveNext() считай...

Ну, можно ещё и не так извратиться. Можно по 2 раза всех переспрашивать. И рандомно встряхивать стек. чтоб совсем уж быстро было.

П>Попробуйте на нынешних итераторах что-нибудь сильно рекурсивное написать, тогда может даже невооружённым глазом заметна будет разница


Не очень заметна. Специально не мерял, но узким местом не становилось.

  private static IEnumerable<T> UngroupRecurseEnumerator<T>(
      IEnumerable<T> source, Func<T, IEnumerable<T>> getItemsFunction)
    {
      Stack<IEnumerator<T>> stack = new Stack<IEnumerator<T>>();
      stack.Push(source.GetEnumerator());
      do
      {
        IEnumerator<T> enumerator = stack.Peek();
        if (enumerator.MoveNext())
        {
          T current = enumerator.Current;
          stack.Push(getItemsFunction(current).GetEnumerator());
          yield return current;
        }
        else
        {
          stack.Pop();
        }
      }
      while (HasValues(stack));
    }
Re[8]: Как ускорить yield return?
От: Пельмешко Россия blog
Дата: 23.02.10 11:53
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Интересно, как можно вот такую красоту сохранить, а варнинг (о рекурсивной ссылке на не-функцию) убрать?

А>
А>let rec fib = Seq.cache <| seq {
А>    yield 0I
А>    yield 1I
А>    yield! Seq.map2 (+) fib (Seq.skip 1 fib )}
А>


Ну это с трудом уже красотой назовёшь, но избавится от "варнинга" можно, использую ref-ячейки и отложенные последовательности:
module Seq =

    (*  cache_rec : (seq<'a> -> #seq<'a>) -> seq<'a>  *)
    let cache_rec f =
        let self = ref Seq.empty
        let fake = Seq.delay <| fun () -> !self
        let seq  = Seq.cache <| f fake
        self := seq
        seq

let fib =
    Seq.cache_rec (fun self -> seq {
        yield  0I
        yield  1I
        yield! Seq.map2 (+) self (Seq.skip 1 self)
    })
Re[9]: Как ускорить yield return?
От: Аноним  
Дата: 23.02.10 20:32
Оценка:
Здравствуйте, Пельмешко, Вы писали:

использую ref-ячейки и отложенные последовательности:
П>
П>module Seq =

П>    (*  cache_rec : (seq<'a> -> #seq<'a>) -> seq<'a>  *)
П>    let cache_rec f =
П>        let self = ref Seq.empty
П>        let fake = Seq.delay <| fun () -> !self
П>        let seq  = Seq.cache <| f fake
П>        self := seq
П>        seq
П>


Интересно, спасибо.

Кстати кажется можно переписать без использования рефов и присвоения:
module Seq =

    let cache_rec f =
        let rec x _ = Seq.delay (fun () -> f <| y () )
        and y _ = Seq.cache <| x ()
        f <| x ()


Но однако ж
fib = 0 : 1 : zipWith (+) fib (tail fib)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.