В предыдущих сериях
Микрооптимизации:
Сказка про Method as Parameter #dotnet #methods #gc
Инструменты анализа эффективности работы приложения. PerfView #performance_analysis #trace #perfview
Пародия на замыкания #dotnet #methods #gc
yield return #dotnet #il-code
Про тредпул:
ThreadPool.Intro #dotnet #threadpool
ThreadPool. async/await #dotnet #threadpool #il_code
ThreadPool.Chain #dotnet #threadpool
Про низкоуровневое:
Reciprocal throughput #microoptimization #low-level
Сказка про Branch prediction #microoptimization #low-level
Разное:
Сказка про Guid.NewGuid() #os_specific #dotnet #microoptimization
Ходят слухи, что foreach быстрее for. А ещё ходят слухи, что for быстрее foreach. Пора разобраться, что быстрее!
Художественное отступление, шутка на текущую тему. Для того, чтобы узнать самое интересное, читать текст под катом совершенно не обязательно.
— Саня, Саня, а давай проверим, что лучше плавает? Мой самолёт или твой поезд?
— Ого, пошли на речку, проверим!
…
— Ха, твой поезд утонул раньше моего самолёта!
— Ну и ладно. А давай проверим, что лучше летает? Утюг или кирпич?
— Давай, сейчас я утюг из дома возьму, а ты кирпич со стройки возьми
…
— Кидаем, раз, два, три!
— Ого, утюг дальше улетел. Это наверное потому, что у него форма аэродинамическая!
— Давай ещё что-нибудь проверим. Как думаешь, из чего лучше парашют получится, из простыни или скатерти? Можно с чердака проверить.
…
— Эй, бездари, чего без дела шляетесь? А ну уроки делать!
— Ну мааам. Мы тут вообще-то исследованиями физическими занимаемся.
— Уроки сделаешь, потом исследовать будешь. Кстати, ты утюг не трогал? Никак найти не могу.
Сначала определим область применимости, где можно взаимозаменять for и foreach. В первую очередь это массивы. Также, это списки — List. А ещё, сюда можно отнести интерфейс списка — IList. Под этим интерфейсом можно спрятать как обычный List, так и массив (делать свои реализации мы не будем). Всякие извращенные случаи, например словари, где можно устроить for по ключам-int'ам, рассматривать не будем.
Заготовим наши коллекции:
public class ForeachVsFor { private List<int> list; //Список private IList<int> iListOverList; //Список под интерфейсом IList private int[] array; //Массив private IList<int> iListOverArray; //Массив под интерфейсом IList [GlobalSetup] public void Setup() { var length = 45;//It's a good number. Not too small, not too big. var ints = new List<int>(length); for (var i = 0; i < length; i++) { ints.Add(i); } list = ints; iListOverList = ints; array = ints.ToArray(); iListOverArray = array; } }
Дабы исследуемый цикл не был совершенно без тела, будем делать на каждой итерации простую операцию — сложение. Будем складывать все числа в коллекции. А ещё, чтобы добавить перчинки, давайте будем проверять и на Net6, и на Net7!
Массивы
Начнём от простого к сложному, то есть с массивов. Как вы думаете, что быстрее:
[Benchmark] public int ForArray() { var summ = 0; for (int i = 0; i < array.Length; i++) { summ += array[i]; } return summ; } [Benchmark] public int ForeachArray() { var summ = 0; foreach (var e in array) { summ += e; } return summ; } [Benchmark] //Этот код присутствует здесь для тех, кто помнит про safety-check'и //в индексации массива, которые перепроверяют границы массива (https://habr.com/ru/companies/skbkontur/articles/737858/). public unsafe int ForUnsafeArray() { var summ = 0; var length = array.Length; fixed (int* ptr = array) { var pointer = ptr; var bound = pointer + length; while (pointer != bound) { summ += *pointer; pointer += 1; } } return summ; }
Результаты бенчмарка для массива под катом.
| Method | Runtime | Mean | Gen0 | Allocated | |---------------------- |--------- |----------:|-------:|----------:| | ForArray | .NET 6.0 | 25.52 ns | - | - | | ForeachArray | .NET 6.0 | 15.87 ns | - | - | | ForUnsafeArray | .NET 6.0 | 17.75 ns | - | - | |---------------------- |--------- |----------:|-------:|----------:| | ForArray | .NET 7.0 | 24.37 ns | - | - | | ForeachArray | .NET 7.0 | 15.71 ns | - | - | | ForUnsafeArray | .NET 7.0 | 18.22 ns | - | - |
Для начала обратим внимание, что foreach действительно быстрее for на массивах, причем намного.
Далее, ForUnsafe действительно намного быстрее обычного For. В чем разница между For и ForUnsafe мы уже знаем — в лишней проверке на ненарушение границ массива на каждой итерации при индексации.
И ForUnsafe лишь чуть-чуть хуже Foreach. Не будем изучать эту разницу под микроскопом в ASM-коде.
Между Net6 и Net7 разница совсем не существенная.
Списки
Перейдём к спискам, то есть List. У них под капотом, как известно, тоже массив. Но проверим и его, всё-таки методы у него свои. Как вы думаете, что быстрее:
[Benchmark] public int ForList() { var summ = 0; for (int i = 0; i < list.Count; i++) { summ += list[i]; } return summ; } [Benchmark] public int ForeachList() { var summ = 0; foreach (var e in list) { summ += e; } return summ; }
Результаты бенчмарка для списка под катом.
| Method | Runtime | Mean | Gen0 | Allocated | |---------------------- |--------- |----------:|-------:|----------:| | ForList | .NET 6.0 | 32.96 ns | - | - | | ForeachList | .NET 6.0 | 49.89 ns | - | - | |---------------------- |--------- |----------:|-------:|----------:| | ForList | .NET 7.0 | 32.25 ns | - | - | | ForeachList | .NET 7.0 | 36.08 ns | - | - | Старые запуски на массиве, чтобы были перед глазами (только Net7) |---------------------- |--------- |----------:|-------:|----------:| | ForArray | .NET 7.0 | 24.37 ns | - | - | | ForeachArray | .NET 7.0 | 15.71 ns | - | - |
Для начала обратим внимание, что в случае списков for действительно быстрее foreach, причем намного (для массивов было наоборот!). Но только на Net6! А на Net7 разница уже не такая существенная, хотя и все равно присутствует. Не будем изучать, почему в Net7 лучше. Лучше — и замечательно.
Отдельно отметим, что оба варианта сильно проигрывают обоим вариантам для массива.
Массив под интерфейсом IList
Перейдём к интерфейсам. У нас есть переменная типа IList, в которую мы просто присвоили наш массив. Проверим, изменится ли что-нибудь при работе с массивом не напрямую, а через интерфейс IList.
[Benchmark] public int ForIListOverArray() { var summ = 0; for (int i = 0; i < iListOverArray.Count; i++) { summ += iListOverArray[i]; } return summ; } [Benchmark] public int ForeachIListOverArray() { var summ = 0; foreach (var e in iListOverArray) { summ += e; } return summ; }
Результаты бенчмарка для массива под IList под катом.
| Method | Runtime | Mean | Gen0 | Allocated | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverArray | .NET 6.0 | 210.78 ns | - | - | | ForeachIListOverArray | .NET 6.0 | 197.25 ns | 0.0076 | 32 B | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverArray | .NET 7.0 | 220.61 ns | - | - | | ForeachIListOverArray | .NET 7.0 | 230.32 ns | 0.0076 | 32 B | Старые запуски, чтобы были перед глазами (только Net7) |---------------------- |--------- |----------:|-------:|----------:| | ForList | .NET 7.0 | 32.25 ns | - | - | | ForeachList | .NET 7.0 | 36.08 ns | - | - | |---------------------- |--------- |----------:|-------:|----------:| | ForArray | .NET 7.0 | 24.37 ns | - | - | | ForeachArray | .NET 7.0 | 15.71 ns | - | - |
Первое, что бросается в глаза — это то, что foreach теперь мусорит объектами!
Второе, что бросается в глаза — foreach на Net7 стал хуже, чем на Net6!
Ну и третье, что бросается в глаза — обращения к IList'у примерно на порядок хуже, чем обращения просто к списку или массиву!
Список под интерфейсом IList
Повторим предыдущий эксперимент с интерфейсом IList. У нас есть переменная типа IList, в которую мы просто присвоили наш список. Проверим, изменится ли что-нибудь, при работе со списком не напрямую, а через интерфейс IList.
[Benchmark] public int ForIListOverList() { var summ = 0; for (int i = 0; i < iListOverList.Count; i++) { summ += iListOverList[i]; } return summ; } [Benchmark] public int ForeachIListOverList() { var summ = 0; foreach (var e in iListOverList) { summ += e; } return summ; }
Результаты бенчмарка для списка под IList под катом.
| Method | Runtime | Mean | Gen0 | Allocated | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverList | .NET 6.0 | 190.77 ns | - | - | | ForeachIListOverList | .NET 6.0 | 309.41 ns | 0.0095 | 40 B | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverList | .NET 7.0 | 187.43 ns | - | - | | ForeachIListOverList | .NET 7.0 | 355.90 ns | 0.0095 | 40 B | Старые запуски, чтобы были перед глазами (только Net7) |---------------------- |--------- |----------:|-------:|----------:| | ForList | .NET 7.0 | 32.25 ns | - | - | | ForeachList | .NET 7.0 | 36.08 ns | - | - | |---------------------- |--------- |----------:|-------:|----------:| | ForArray | .NET 7.0 | 24.37 ns | - | - | | ForeachArray | .NET 7.0 | 15.71 ns | - | - | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverArray | .NET 7.0 | 220.61 ns | - | - | | ForeachIListOverArray | .NET 7.0 | 230.32 ns | 0.0076 | 32 B |
Как и в предыдущем случае, foreach мусорит объектами; foreach на Net7 заметно хуже, чем на Net6; обращения к IList'у примерно на порядок хуже, чем обращения просто к списку или массиву.
Интересные дополнительные наблюдаемые эффекты: Foreach на IList'е под которым List значительно хуже, чем на том IList, под которым array. А для For наоборот.
Почему так не эффективны обращения к IList
Полный ответ на этот вопрос был бы достаточно объемным. Но давайте сделаем первый шажок. Посмотрим на IL-код, например метода ForeachIListOverList.
Красным выделен переход от одной итерации цикла к другой. Синим — вызовы виртуальных методов GetCurrent и MoveNext у enumerator'а. Который чуть выше мы и создали, чем и намусорили — я выделил это зелёным цветом и подчеркнул, что создался там класс, то есть объект на хипе.
Теперь давайте взглянем на IL-код метода ForeachList.
Красным выделен переход от одной итерации цикла к другой. Синим — вызовы уже не виртуальных, а обычных методов GetCurrent и MoveNext у enumerator'а. Который чуть выше мы и создали. Но мы им не намусорили — я выделил это зелёным цветом и подчеркнул, что создался там valuetype, то есть структура на стеке. Да, дотнет умный и когда уверен в ситуации, для обычного List'а создает специальный легковесный Enumerator, который структура.
В остальном код одинаковый. Из чего следует, что вот эти виртуальные вызовы очень дорогие. И это действительно так. Это легко понять, если углубиться в то, как работают интерфейсы. Сейчас разбирать это мы не будем, иначе размер статьи увеличится в несколько раз.
Что можно улучшить
Давайте попытаемся уменьшить число виртуальных вызовов. В случае с foreach у нас ничего не выйдет. Метода bool TryMoveNext(out T value), увы, не существует. Но давайте посмотрим на код с for в случае с IList'ом. Например, на ForIListOverList.
Красным отмечен цикл. Синим — виртуальные вызовы методов. GetItem — это и есть индексация. А вот GetCount — похоже, что это вызов свойства .Count! Действительно, если это интерфейс, откуда дотнету знать, что реализация под ним всегда будет возвращать одно и то же значение на вызов свойства Count? Получается, на каждой итерации мы вызываем дорогой виртуальный метод Count. Но если мы знаем, что коллекция внутри не меняется, мы можем воспользоваться этим и закешировать размер коллекции, чтобы не «извлекать» её заново на каждой итерации цикла.
[Benchmark] public int ForIListOverList() { var summ = 0; for (int i = 0; i < iListOverList.Count; i++) { summ += iListOverList[i]; } return summ; } [Benchmark] public int ForIListOverList2() { var summ = 0; var upperBound = iListOverList.Count; for (int i = 0; i < upperBound; i++) { summ += iListOverList[i]; } return summ; }
Аналогичный код я написал и для случая iListOverArray. Проверим, поможет ли.
| Method | Runtime | Mean | Gen0 | Allocated | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverList | .NET 6.0 | 190.77 ns | - | - | | ForIListOverList2 | .NET 6.0 | 115.69 ns | - | - | | ForIListOverArray | .NET 6.0 | 210.78 ns | - | - | | ForIListOverArray2 | .NET 6.0 | 125.25 ns | - | - | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverList | .NET 7.0 | 187.43 ns | - | - | | ForIListOverList2 | .NET 7.0 | 113.02 ns | - | - | | ForIListOverArray | .NET 7.0 | 220.61 ns | - | - | | ForIListOverArray2 | .NET 7.0 | 124.65 ns | - | - |
Работает! Версии с циферкой 2, те, где мы закешировали размер коллекции, действительно быстрее. Если открыть IL-код, то вы убедитесь, что внутри тела цикла действительно пропал вызов GetCount. Он вызывается один раз до цикла и кешируется, что мы и написали в C#-коде. И заметно, что уменьшив число вызовов виртуальных методов в два раза, производительность увеличилась тоже почти в два раза, что ещё раз подтверждает их высокую стоимость.
Почему на Net7 обращение к IList'у медленнее, чем на Net6?
К сожалению, у меня нет на это ответа. Если сравнить ASM-код всего нашего бенчмарка на Net6 и Net7, кроме собственно вызова виртуальных методов, то он абсолютно идентичен (на 99%, но различия не выглядят значимыми для производительности). То есть вся разница именно где-то внутри дотнета при работе с интерфейсами и\или энумераторами. Эта история требует какого-то дополнительного исследования и вероятно, она не ограничится только лишь IList'ом. При этом, можно отметить такие наблюдения:
Код с For-циклами по IList'у работает одинаково на Net6 и Net7;
Код с Foreach-циклами по IList'у на Net7 ощутимо медленнее;
Весь прочий код со списками или массивами, что for, что foreach, без IList'а, либо одинаков на Net6 и Net7, либо Net7 чуть-чуть побыстрее.
Если кто-то знает причины этой деградации, поделитесь ими в комментариях!
Полная таблица бенчмарка
// * Summary * BenchmarkDotNet=v0.13.4, OS=Windows 10 (10.0.19045.2486) Intel Core i7-4771 CPU 3.50GHz (Haswell), 1 CPU, 8 logical and 4 physical cores .NET SDK=7.0.102 [Host] : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2 .Net 6.0 : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2 .Net 7.0 : .NET 7.0.2 (7.0.222.60605), X64 RyuJIT AVX2 | Method | Runtime | Mean | Gen0 | Allocated | |---------------------- |--------- |----------:|-------:|----------:| | ForIListOverList | .NET 6.0 | 190.77 ns | - | - | | ForIListOverList2 | .NET 6.0 | 115.69 ns | - | - | | ForeachIListOverList | .NET 6.0 | 309.41 ns | 0.0095 | 40 B | | ForList | .NET 6.0 | 32.96 ns | - | - | | ForeachList | .NET 6.0 | 49.89 ns | - | - | | ForArray | .NET 6.0 | 25.52 ns | - | - | | ForeachArray | .NET 6.0 | 15.87 ns | - | - | | ForUnsafeArray | .NET 6.0 | 17.75 ns | - | - | | ForIListOverArray | .NET 6.0 | 210.78 ns | - | - | | ForIListOverArray2 | .NET 6.0 | 125.25 ns | - | - | | ForeachIListOverArray | .NET 6.0 | 197.25 ns | 0.0076 | 32 B | | ForIListOverList | .NET 7.0 | 187.43 ns | - | - | | ForIListOverList2 | .NET 7.0 | 113.02 ns | - | - | | ForeachIListOverList | .NET 7.0 | 355.90 ns | 0.0095 | 40 B | | ForList | .NET 7.0 | 32.25 ns | - | - | | ForeachList | .NET 7.0 | 36.08 ns | - | - | | ForArray | .NET 7.0 | 24.37 ns | - | - | | ForeachArray | .NET 7.0 | 15.71 ns | - | - | | ForUnsafeArray | .NET 7.0 | 18.22 ns | - | - | | ForIListOverArray | .NET 7.0 | 220.61 ns | - | - | | ForIListOverArray2 | .NET 7.0 | 124.65 ns | - | - | | ForeachIListOverArray | .NET 7.0 | 230.32 ns | 0.0076 | 32 B |
Выводы
Непосредственные
foreach быстрее for на массивах, по крайней мере на int[]. Но unsafe-реализация for может догнать foreach.
for быстрее foreach на списках, по крайней мере на
List<int>. Хотя, на Net7 foreach значительно ускорили. Но for он так и не догнал.Обращения к IList'у как к коллекции что с помощью for, что с помощью foreach, очень дороги на каждой итерации из-за виртуальных вызовов методов. При этом, foreach на IList'е аллоцирует объект энумератора. А ещё, foreach на IList'е деградирует на Net7 по сравнению с Net6.
Более полезные
В местах, действительно чувствительных к производительности, не место этим всяким ООПшным штучкам с интерфейсами. Виртуальные вызовы крайне дороги. Даже если от интерфейсов никуда не деться, старайтесь минимизировать их вызовы, например, кешировать то, что можно закешировать. Иначе легко может оказаться, что 90% времени работы программы потрачено не на ваш полезный код, а на проделки дотнета.
Впрочем, если подходить к вопросу оптимизаций работы именно с интерфейсами (особенно своими собственными, не дотнетными), то иногда можно кое-что сделать. В том же Net7 появились возможности в связке sealed-классов с PGO.
Никогда не делайте предположений, что что-то быстрее чего-то, не проведя бенчмарков на приближенных к реальности данных в нужном окружении. Реальность намного сложнее, чем мы можем себе представить. Как можно было заметить, в одних условиях побеждает одно решение, а в других другое.
Не всегда всё новое лучше всего старого. Иногда, даже в таких вещах как DotNet, архитекторам приходится чем-то жертвовать в угоду другим целям, выпуская новые версии. И если у вас система чувствительна к производительности, стоит тщательно все проверять.
