В предыдущих сериях
Микрооптимизации:
-
Сказка про 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, архитекторам приходится чем-то жертвовать в угоду другим целям, выпуская новые версии. И если у вас система чувствительна к производительности, стоит тщательно все проверять.
Автор: Александр
