foreach or for that is the question

Когда я начинал изучать .NET, один человек сказал мне, что foreach работает в 2 раза медленнее for-а, без каких-либо на то обоснований, и я принял это как должное. Теперь, когда чьих-то слов мне мало, я решил написать эту статью.

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

Итак, поехали!

Рассмотрим следующий код:

foreach (var item in Enumerable.Range(0, 128)) {   Console.WriteLine(item); } 

Цикл foreach является синтаксическим сахаром и в данном случае компилятор разворачивает его примерно в следующий код:

IEnumerator<int> enumerator = Enumerable.Range(0, 128).GetEnumerator(); try  {    while (enumerator.MoveNext())    {      int item = enumerator.Current;      Console.WriteLine(item);    }  } finally  {   if (enumerator != null)   {    enumerator.Dispose();   } } 

Зная это можно легко предположить, почему foreach должен быть медленнее for-a. При использовании foreach-а:

• создается новый объект — итератор;
• на каждой итерации идет вызов метода MoveNext;
• на каждой итерации идет обращение к свойству Current, что равносильно вызову метода;

Вот и все! Хотя нет, не все так просто…

Есть еще один нюанс! К счастью или, к сожалению C#/CLR имеют кучу оптимизаций. К счастью, потому что код работает быстрее, к сожалению, потому что разработчикам об этом приходится знать (все же я считаю к счастью, причем к большому).

Например, поскольку массивы являются типом, сильно интегрированным в CLR, то для них имеется большое количество оптимизаций. Одна из них касается цикла foreach.

Таким образом, важным аспектом производительности цикла foreach является итерируемая сущность, поскольку в зависимости от нее он может разворачиваться по-разному.

В статье мы будем рассматривать итерирование массивов и списков. Помимо for-a и foreach-a будем так же рассматривать итерирование с помощью статического метода Array.ForEach, а так же экземплярного List.ForEach.

static double ArrayForWithoutOptimization(int[] array) {    int sum = 0;    var watch = Stopwatch.StartNew();    for (int i = 0; i < array.Length; i++)      sum += array[i];     watch.Stop();     return watch.Elapsed.TotalMilliseconds; }  static double ArrayForWithOptimization(int[] array) {    int length = array.Length;    int sum = 0;    var watch = Stopwatch.StartNew();     for (int i = 0; i < length; i++)       sum += array[i];     watch.Stop();      return watch.Elapsed.TotalMilliseconds; }  static double ArrayForeach(int[] array) {   int sum = 0;   var watch = Stopwatch.StartNew();    foreach (var item in array)     sum += item;   watch.Stop();   return watch.Elapsed.TotalMilliseconds; }  static double ArrayForEach(int[] array) {   int sum = 0;   var watch = Stopwatch.StartNew();   Array.ForEach(array, i => { sum += i; });   watch.Stop();   return watch.Elapsed.TotalMilliseconds; } 

Тесты выполнялись при включенном флаге оптимизировать код в Release. Количество элементов в массиве и списке равно 100000000. Машина, на которой проводились тесты, имеет на своём борту процессор Intel Core i-5 и 8 GB оперативной памяти.

Массивы

Из диаграммы видно, что for/foreach на массивах работают одинаковое время. Это дело рук той самой оптимизации, которая разворачивает цикл foreach в for, с использованием длины массива в качестве максимальной границы итерирования. Кстати, не важно кэшируем мы длину или нет при итерировании с помощью for-а, результат практически один и тот же.

Как бы странно это не было, но при использовании массивов, кэширование длины может сказаться негативно. Дело в том, что когда JIT видит array.Length в качестве границы итерирования в цикле, то он выносит проверку индекса на попадание в нужные границы за цикл, тем самым проверка делается только один раз. Эту оптимизацию очень легко разрушить, и случай когда мы кэшируем переменную уже не оптимизируется.

Метод же Array.ForEach показал самый худший результат. Его реализация выглядит достаточно просто:

public static void ForEach<T>(T[] array, Action<T> action)  {   for (int index = 0; index < array.Length; ++index)     action(array[index]);  } 

Тогда почему же он работает так медленно? Ведь за кулисами он просто использует обычный for. Все дело в вызове делегата action. Фактически на каждой итерации вызывается метод, а мы знаем, что это лишние накладные расходы. Тем более, как известно, делегаты вызываются не так быстро, как хотелось бы, отсюда и результат.

С массивами все разъяснили. Переходим к спискам, там ситуация не менее интереснее.

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

Списки

Вот это результат!!!

При итерации списков циклы for/foreach дают различные результаты. Дело в том, что здесь нет никакой оптимизации, и foreach разворачивается в создание итератора и дальнейшую работу с ним. Но это не самое интересное.

Интереснее то, что for без оптимизации работает медленнее foreach-а!!! Почему это так? При использовании for-а без кэширования длины списка на каждой итерации идет обращение к свойству Count (вызов метода get_Count), а так же обращение к индексатору (вызов метода get_Item). При использовании итератора, то есть цикла foreach идет вызов метода MoveNext, а так же обращение к свойству Current. Получается, по два вызова метода в каждом случае. Тогда почему один цикл медленнее другого? Тут в силу вступает следующий факт: итератором для List<>, да и вообще для обобщенных коллекций выступает изменяемая структура (да это зло, но разработчики пошли на это сознательно взамен на производительность). Значит, ее методы вызываются с помощью инструкции call, в отличие от callvirt, которая используется при обращении к свойству Count и индексатору. Как известно, call вызывается быстрее, чем callvirt, поскольку не требует проверок на null.

Метод List.ForEach показал себя с лучшей стороны, его скорость сродни скорости foreach. Его реализация выглядит так:

public void ForEach(Action<T> action) {   int num = this._version;    for (int index = 0; index < this._size && num == this._version; ++index)      action(this._items[index]);    if (num == this._version)      return;    ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); } 

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

Интересен факт, что у массивов метод ForEach является статическим, в то время как у списков он экземплярный. Я полагаю, это сделано во благо увеличения производительности. Как известно, список основан на обычном массиве, а потому в методе ForEach идет обращение по индексу к массиву, что в разы быстрее обращения по индексу через индексатор.

Массивы VS списки

Конкретные цифры

• циклы for (с и без кэширования длины) и foreach для массивов работают одинаковое время;
• цикл Array.ForEach примерно в два раза медленнее циклов for/foreach;
• for (без кэшировании длины) на списках работает примерно в 3 раза медленнее, чем на массивах;
• for (с кэшировании длины) на списках работает примерно в 2 раза медленнее, чем на массивах;
• foreach на списках медленнее foreach на массивах примерно в 2 раза;
• List.ForEach и foreach работает примерно одинаковое время на списках;

Призеры

Среди массивов:

Среди списков:

В заключении

Не знаю как для Вас, но для меня эта статья оказалась очень интересной. Особенно процесс её написания. Я был крайне удивлен тем, что цикл foreach на массивах показал результат, не уступающий for-у, а на списках результат превосходящий for. Думаю, теперь после прочтения этой статьи никто не скажет, что foreach медленнее, чем for, потому что на самом деле ЭТО НЕ ТАК.

Спасибо за прочтение.