foreach or for that is the question

в 20:00, , рубрики: .net, c#.net, for, foreach, метки: , ,

foreach or for that is the questionВопрос о выборе цикла for/foreach стар, как мир. Все мы слышали, что foreach работает медленнее for-а. Но не все знаем почему… А вообще так ли оно?

Когда я начинал изучать .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 оперативной памяти.

Массивы

foreach or for that is the question

Из диаграммы видно, что 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. Фактически на каждой итерации вызывается метод, а мы знаем, что это лишние накладные расходы. Тем более, как известно, делегаты вызываются не так быстро, как хотелось бы, отсюда и результат.

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

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

Списки

foreach or for that is the question

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

При итерации списков циклы 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 списки

foreach or for that is the question

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

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

Призеры

Среди массивов:
foreach or for that is the question

Среди списков:
foreach or for that is the question

В заключении

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

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

Автор: timyrik20

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js