Почему операции LINQ быстрее, чем обычный цикл?

Question

Мы с другом были немного озадачены во время дискуссий по программированию. В качестве примера мы создали фиктивную проблему наличия List<int> из n случайных целых чисел (обычно 1.000.000) и хотели создать функцию, которая вернула множество всех целых чисел, число которых было более одного. Довольно простой материал. Мы создали один оператор LINQ для решения этой проблемы и простой алгоритм сортировки вставки.

Теперь, когда мы протестировали скорость, с которой работал код (с использованием System.Diagnostics.StopWatch), результаты были сбивчивыми. Не только код LINQ превосходил простую сортировку, но он работал быстрее, чем , одинforeach/, который сделал только один цикл списка и не имел операций внутри (что на боковой дорожке я думал, что компилятор должен был обнаружить и удалить все вместе).

Если мы сгенерировали новый List<int> случайных чисел в одном и том же исполнении программы и снова запустили код LINQ, производительность увеличилась бы на порядки (обычно в тысячу раз). Производительность пустых петель была, конечно, одинаковой.

Итак, что здесь происходит? Является ли LINQ с использованием параллелизма превосходить обычные циклы? Как эти результаты возможны? LINQ использует quicksort, который работает в n * log (n), который по определению уже медленнее n.

А что происходит при скачке производительности во втором прогоне?

Мы были оба озадачены и заинтригованы этими результатами и надеялись на некоторые разъясняющие идеи сообщества, чтобы удовлетворить наше собственное любопытство.

Answer 1

Несомненно, вы фактически не выполнили запрос, вы просто определили его. LINQ создает дерево выражений, которое фактически не оценивается, пока вы не выполните операцию, требующую повторения перечисления. Попробуйте добавить операцию ToList() или Count() к запросу LINQ, чтобы заставить запрос быть оцененным.

Основываясь на вашем комментарии, я ожидаю, что это похоже на то, что вы сделали. Примечание. Я не тратил времени на выяснение, насколько эффективен запрос; Я просто хочу, чтобы -код, чтобы проиллюстрировать, как код может быть структурирован.

var dataset = ... 

var watch = Stopwatch.StartNew(); 

var query = dataset.Where(d => dataset.Count(i => i == d) > 1); 

watch.Stop(); // timer stops here 

foreach (var item in query) // query is actually evaluated here 
{ 
    ... print out the item... 
} 

Answer 2

Я бы предположил, что LINQ работает быстрее, чем «нормальный цикл», когда ваш алгоритм менее совершенен (или у вас есть некоторые проблемы в коде). Таким образом, LINQ будет быстрее сортировать, чем если бы вы не писали эффективный алгоритм сортировки и т. Д.

LINQ обычно «так быстро» или «достаточно близко» к скорости обычного цикла, и может быть быстрее (и проще) для кодирования/отладки/чтения. Это его преимущество - не скорость выполнения.

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

Answer 3

Если вы не скомпилировали с включенным «Оптимизированным кодом», возможно, вы увидите это поведение. (Это, безусловно, объясняет, почему пустая петля не была удалена.)

Код, лежащий в основе LINQ, однако, является частью уже скомпилированного кода, который, безусловно, был бы оптимизирован (JIT, NGen или аналогичным).