Question

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

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 и вызовы 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
<b>- Linq: 4517ms   !!! THIS IS THE PROBLEM !!!</b>
- 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);
}
```
при выполнении этого метода я также использовал два подхода:
1. предикат, предоставляемый непосредственно при вызове метода в цикле for:
```
for (int i = 0; i < 1000000; i++)
{
    linqLookup.GetItem(item => item.IsWithinRange(GetRandomDay()));
}
```
2. построитель предиката, определенный вне цикла for:
```
Func<DateTime, Func<Ranger, bool>> builder = d => r => r.IsWithinRange(d);
for (int i = 0; i < 1000000; i++)
{
    linqLookup.GetItem(builder(GetRandomDay()));
}
```

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

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

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

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

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

James Michael Hare · Answer 1 · 21 ноября 2011

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

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

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

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

Обновление

На самом деле, даже без какой-либо оптимизации, компиляция в режиме релиза на моей машине я не вижу 5-кратной разницы. Я только что выполнил 1 000 000 поисков на Item, который имеет только поле DateTime, с 5000 пунктов в списке. Конечно, мои данные и т. Д. Отличаются, но вы можете увидеть, что времена действительно очень близки, когда вы абстрагируете делегата:

итерация: 14279 мс, 0,014279 мс / вызов

linq w opt: 17400 мс, 0,0174 мс / вызов

Эти различия во времени очень незначительны и заслуживают улучшения читаемости и удобства обслуживания при использовании LINQ. Однако я не вижу 5-кратной разницы, и это заставляет меня поверить, что в вашем тестовом жгуте мы чего-то не видим.

LukeH · Answer 2 · 22 ноября 2011

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

Если я добавлюодна строка метода GetPointData в вашем классе IterationRangeLookupSingle, затем он замедляется до того же темпа ползания, что и LinqRangeLookupSingle.Попробуйте:

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

(я не уверен, почему компилятор и / или джиттер не могут просто игнорировать лишний делегат, который я добавил выше. Очевидно, делегат необходим в вашем LinqRangeLookupSingle классе.)

Один из возможных обходных путей - составить предикат в LinqRangeLookupSingle так, чтобы point передавался ему в качестве аргумента.Это означает, что делегат нужно создавать только один раз , а не каждый раз, когда вызывается метод GetPointData.Например, следующее изменение ускорит версию LINQ, так что она в значительной степени сопоставима с версией foreach:

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

Gabe · Answer 3 · 21 ноября 2011

Предположим, у вас есть такой цикл:

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

Этот цикл создаст 1 000 000 лямбда-объектов для вызова i.IsWithinRange доступа к day. После каждого создания лямбды делегат, который вызывает i.IsWithinRange, вызывается в среднем 1 000 000 * items.Length / 2 раза. Оба этих фактора не существуют в вашем цикле foreach, поэтому явный цикл быстрее.

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

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

Вопрос

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

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

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

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

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

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

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

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

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

Ответы [ 3 ]

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

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

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

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

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

Вопрос

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

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

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

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

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

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

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

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

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

Ответы [ 3 ]

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

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

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

Нет похожих вопросов

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

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