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

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

public class IterationLookup<TItem>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> 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<TItem>
{
    private IList<Item> items = null;

    public IterationLookup(IEnumerable<TItem> items, Func<TItem, TKey> 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<RangeItem> ranges = GenerateRanges(); // returns List<T>

var iterLookup = new IterationLookup<RangeItems>(ranges, r => r.Id);
var linqLookup = new LinqLookup<RangeItems>(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<RangeItem> 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 loops и вызовов 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 implementatino, которое было ужасно медленным. Оказывается, это связано с оптимизацией компилятора делегата. LukeH предоставил лучшее и наиболее пригодное для использования решение, которое фактически заставило меня попробовать разные подходы к этому. Я пробовал различные подходы в методе GetItem (или GetPointData, как он назывался в Gist):

• обычный способ, который сделает большинство разработчиков (и реализован в Gist, а также не обновлялся после того, как результаты показали, что это не лучший способ сделать это):

  return this.items.FirstOrDefault(item => item.IsWithinRange(day));
  

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

  Func<TItem, bool> predicate = item => item.IsWithinRange(day);
  return this.items.FirstOrDefault(predicate);
  

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

  Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d);
  return this.items.FirstOrDefault(builder(day));
  

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

  Func<DateTime, Func<TItem, bool>> builder = d => item => item.IsWithinRange(d);
  Func<TItem, bool> predicate = builder(day);
  return this.items.FirstOrDefault(predicate);
  

• построитель предикатов уровня (статический или экземпляр):

  return this.items.FirstOrDefault(classLevelBuilder(day));
  

• внешний предикат и предоставляется как параметр метода

  public TItem GetItem(Func<TItem, bool> predicate)
  {
      return this.items.FirstOrDefault(predicate);
  }
  

  при выполнении этого метода я также принял два подхода:

  • предикат предоставляется непосредственно при вызове метода в цикле for:

    for (int i = 0; i < 1000000; i++)
    {
        linqLookup.GetItem(item => item.IsWithinRange(GetRandomDay()));
    }
    

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

    Func<DateTime, Func<Ranger, bool>> builder = d => r => r.IsWithinRange(d);
    for (int i = 0; i < 1000000; i++)
    {
        linqLookup.GetItem(builder(GetRandomDay()));
    }
    

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

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

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

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

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

• все остальные заняли место между 4200 мс - 4360 мс и поэтому считаются непригодными.

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

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

Ответы

// in IterationRangeLookupSingle<TItem, TKey>
public TItem GetPointData(DateTime point)
{
    // just a single line, this delegate is never used
    Func<TItem, bool> dummy = i => i.IsWithinRange(point);

    // the rest of the method remains exactly the same as before
    // ...
}

// in LinqRangeLookupSingle<TItem, TKey>
public TItem GetPointData(DateTime point)
{
    Func<DateTime, Func<TItem, bool>> builder = x => y => y.IsWithinRange(x);
    Func<TItem, bool> predicate = builder(point);

    return this.items.FirstOrDefault(predicate);
}

public class LinqLookup<TItem, TKey>
{
    private IList<Item> items = null;

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

    public TItem GetItem(Func<TItem, TKey> selector)
    {
        return this.items.FirstOrDefault(selector);
    }
}

for (int counter = 0; counter < 1000000; counter++)
{
    // execute this 1M times and time it 
    DateTime day = GetRandomDay(); 
    items.FirstOrDefault(i => i.IsWithinRange(day)); 
}