foreach + break vs linq Разница в производительности FirstOrDefault

Question

foreach + break vs linq Разница в производительности FirstOrDefault

У меня есть два класса, которые выполняют выборку данных диапазона дат для определенных дней.

public class IterationLookup
{
    private IList items = null;

    public IterationLookup(IEnumerable items, Func keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(DateTime day)
    {
        foreach(TItem i in this.items)
        {
           if (i.IsWithinRange(day))
           {
               return i;
           }
        }
        return null;
    }
}


public class LinqLookup
{
    private IList items = null;

    public IterationLookup(IEnumerable items, Func keySelector)
    {
        this.items = items.OrderByDescending(keySelector).ToList();
    }

    public TItem GetItem(DateTime day)
    {
        return this.items.FirstOrDefault(i => i.IsWithinRange(day));
    }
}

Затем я провожу тесты скорости, которые показывают, что версия Linq примерно в 5 раз медленнее . имеет смысл, если я буду хранить элементы локально, не перечисляя их с помощью ToList . Это значительно замедлит работу, потому что при каждом вызове FirstOrDefault linq также будет выполнять OrderByDescending . Но это не так, поэтому я действительно не знаю, что происходит. Linq должен работать очень похоже на итерацию.

Это фрагмент кода, который измеряет мои тайминги

IList ranges = GenerateRanges(); // returns List

var iterLookup = new IterationLookup(ranges, r => r.Id);
var linqLookup = new LinqLookup(ranges, r => r.Id);

Stopwatch timer = new Stopwatch();

timer.Start();
for(int i = 0; i < 1000000; i++)
{
    iterLookup.GetItem(GetRandomDay());
}
timer.Stop();
// display elapsed time

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
    linqLookup.GetItem(GetRandomDay());
}
timer.Stop();
// display elapsed time

Почему я знаю, что он должен работать лучше? Потому что, когда я пишу очень похожий код без использования этих классов поиска, Linq работает очень похоже на foreach итераций ...

// continue from previous code block

// items used by both order as they do in classes as well
IList items = ranges.OrderByDescending(r => r.Id).ToList();

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
    DateTime day = GetRandomDay();
    foreach(RangeItem r in items)
    {
        if (r.IsWithinRange(day))
        {
            // RangeItem result = r;
            break;
        }
    }
}    
timer.Stop();
// display elapsed time

timer.Restart();
for(int i = 0; i < 1000000; i++)
{
   DateTime day = GetRandomDay();
   items.FirstOrDefault(i => i.IsWithinRange(day));
}
timer.Stop();
// display elapsed time

По моему мнению, это очень похожий код. FirstOrDefault , насколько мне известно, также выполняет итерацию только до тех пор, пока не дойдет до действительного элемента или пока не достигнет конца. И это как-то похоже на foreach с break .

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

Вопрос

Что я делаю не так в своем классе LINQ, что он работает так медленно?
Что я делаю не так в своем классе Iteration, чтобы он работал в два раза медленнее, чем прямой цикл foreach ?

Какое время измеряется?

Я делаю следующие шаги:

Сгенерируйте диапазоны (как показано ниже в результатах)
Создайте экземпляры объектов для IterationLookup, LinqLookup (и мои оптимизированные класс диапазона дат BitCountLookup, который здесь не обсуждается)
Запустить таймер и выполнить 1 миллион поисков в случайные дни в пределах максимального диапазона дат (как видно из результатов) с использованием ранее созданного класса IterationLookup.
Запустить таймер и выполнить 1 миллион поисков в случайные дни в пределах максимального диапазона дат (как видно из результатов) с помощью ранее созданного класса LinqLookup.
Запустить таймер и выполнить 1 миллион поисков (6 раз) с использованием ручных циклов foreach + break и вызовов Linq.

Как видите, создание экземпляра объекта не измеряется .

Приложение I: Результаты более миллиона поисков

Диапазоны, отображаемые в этих результатах, не перекрываются, что должно сделать оба подхода еще более похожими в случае, если версия LINQ не прерывает цикл при успешном сопоставлении (что весьма вероятно) .

Generated Ranges:

ID Range        000000000111111111122222222223300000000011111111112222222222
                123456789012345678901234567890112345678901234567890123456789
09 22.01.-30.01.                     |-------|
08 14.01.-16.01.             |-|
07 16.02.-19.02.                                              |--|
06 15.01.-17.01.              |-|
05 19.02.-23.02.                                                 |---|
04 01.01.-07.01.|-----|
03 02.01.-10.01. |-------|
02 11.01.-13.01.          |-|
01 16.01.-20.01.               |---|
00 29.01.-06.02.                            |-------|

Lookup classes...

- Iteration: 1028ms
- Linq: 4517ms   !!! THIS IS THE PROBLEM !!!
- BitCounter: 401ms

Manual loops...

- Iter: 786ms
- Linq: 981ms
- Iter: 787ms
- Linq: 996ms
- Iter: 787ms
- Linq: 977ms
- Iter: 783ms
- Linq: 979ms

Приложение II: GitHub: Gist-код для тестирования

Я разместил Gist, чтобы вы могли сами получить полный код и посмотреть, что происходит. Создайте приложение консоли и скопируйте в него Program.cs и добавьте другие файлы, которые являются частью этой сущности.

Возьмите здесь .

Приложение III: Заключительные мысли и измерительные тесты

Самой проблемной вещью, конечно же, была реализация LINQ, которая была ужасно медленной. Оказывается, все это связано с оптимизацией компилятора делегата. LukeH предоставил лучшее и наиболее удобное решение , которое фактически заставило меня попробовать разные подходы к этому. Я пробовал различные подходы в методе GetItem (или GetPointData , как он называется в Gist):

обычным способом, который сделали бы большинство разработчиков (и реализован в Gist тоже не обновлялся после того, как результаты показали, что это не лучший способ сделать это):
```
 return this.items.FirstOrDefault (item => item.IsWithinRange (day)); 
 
```

путем определения локальной переменной-предиката:

 Func  predicate = item => item.IsWithinRange (day); 
вернуть this.items.FirstOrDefault (предикат);

локальный построитель предикатов:

 Func > builder = d => item => item.IsWithinRange (d); {{1} } вернуть this.items.FirstOrDefault (строитель (день));

локальный построитель предикатов и локальная переменная предиката:

 Func > builder = d => item => item.IsWithinRange (d); 
Func  predicate = builder (день); 
вернуть this.items.FirstOrDefault (предикат);

построитель предикатов уровня класса (статический или экземплярный):
```
 вернуть this.items.FirstOrDefault (classLevelBuilder (day)); 
 
```
предикат, определенный извне и предоставленный как параметр метода
```
 public TItem GetItem (Func  predicate) 
 {
return this.items.FirstOrDefault (предикат); 
} 
 
```
при выполнении этого метода я также использовал два подхода:
1. предикат предоставляется непосредственно при вызове метода в для цикл:
```
 for (int i = 0; i  item.IsWithinRange (GetRandomDay ())); {{1} }} 
 
```
2. построитель предикатов, определенный вне для цикла :
```
 Func > builder = d => r => r.IsWithinRange (d ); 
для (int i = 0; i 
```

Результаты - что работает лучше всего

Для сравнения, когда с использованием класса итераций требуется ок. 770 мс для выполнения 1 миллиона поисков в случайно сгенерированных диапазонах.

Конструктор локальных предикатов 3 оказался лучше всего оптимизированным для компилятора, поэтому он работает почти так же быстро, как и обычные итерации. 800 мс .
Построитель предикатов 6.2, определенный вне для цикла : 885 мс
Предикат 6.1, определенный в для цикла: 1525 мс
все остальные заняли где-то между 4200 мс - 4360 мс и поэтому считаются непригодными для использования.

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

Самым большим сюрпризом для меня является то, что делегаты (или предикаты) могут занимать столько времени.

49

c# performance linq .net-4.0 foreach

задан Community 23 May 2017 в 02:24

0 ответов

Другие вопросы по тегам:

c# performance linq .net-4.0 foreach

foreach + break vs linq Разница в производительности FirstOrDefault

Это фрагмент кода, который измеряет мои тайминги

Вопрос

Какое время измеряется?

Приложение I: Результаты более миллиона поисков

Приложение II: GitHub: Gist-код для тестирования

Приложение III: Заключительные мысли и измерительные тесты

Результаты - что работает лучше всего

Конструктор локальных предикатов 3 оказался лучше всего оптимизированным для компилятора, поэтому он работает почти так же быстро, как и обычные итерации. 800 мс .

Построитель предикатов 6.2, определенный вне `для цикла` : 885 мс

Предикат 6.1, определенный в `для` цикла: 1525 мс

0 ответов

Похожие вопросы:

foreach + break vs linq Разница в производительности FirstOrDefault

Это фрагмент кода, который измеряет мои тайминги

Вопрос

Какое время измеряется?

Приложение I: Результаты более миллиона поисков

Приложение II: GitHub: Gist-код для тестирования

Приложение III: Заключительные мысли и измерительные тесты

Результаты - что работает лучше всего

Конструктор локальных предикатов 3 оказался лучше всего оптимизированным для компилятора, поэтому он работает почти так же быстро, как и обычные итерации. 800 мс .

Построитель предикатов 6.2, определенный вне для цикла : 885 мс

Предикат 6.1, определенный в для цикла: 1525 мс

0 ответов

Похожие вопросы:

Построитель предикатов 6.2, определенный вне `для цикла` : 885 мс

Предикат 6.1, определенный в `для` цикла: 1525 мс