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. Количество элементов в массиве и списке равно 100 000 000. Машина, на которой проводились тесты, имеет на своём борту процессор 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 с кэшированием длины списка. Индексация списков не влияет на производительность так как JIT inline-ит её (индексация — это обычное свойство с параметром).

    foreach показал результат примерно в 2,5 раза медленнее for-а. Это связано с его сложной структурой которая отрабатывает за кулисами (вызов MoveNext, Current).

    List.ForEach так же как и Array.ForEach показал худший результат. Дело в том, что JIT не inline-ит виртуальные методы, а делегаты как известно всегда вызываются виртуально.

    Реализация этого метода выглядит так:

    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. Так же каждый раз проверяется, не изменился ли список во время итерации, и если изменился, то выбрасывается исключение.

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

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




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


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

    Призеры


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


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


    В заключении


    Не знаю как для Вас, но для меня эта статья оказалась очень интересной. Особенно процесс её написания. Оказывается foreach на массивах быстрее for-а с кэшированием длины. Спасибо JIT-у за оптимизации. foreach же на списках медленнее for-а это факт.

    С сегодняшними компьютерами не использовать цикл foreach только потому что он медленнее for-а, наверное, не совсем правильно. Ведь код с его использованием выглядит более декларативным. Конечно, если нужно ну очччень сильно оптимизировать код, то, наверное, лучше отдать предпочтение for-у.

    Спасибо за прочтение.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 26

      +14
      Давно уже нет никакого вопроса о выборе между одним и другим: какая семантика вам нужна, тем и пользуйтесь. Учитывая, что в значимой части случаев в реальной жизни вы имеете дело не с массивами и списками, а с enumerable, вопроса и вовсе не стоит.
        +1
        С тех пор, как тактовая частота упёрлась в физические пределы, этот вопрос снова появился. Мы уже не можем сказать пользователю «купите процессор побыстрее» — таких просто не существует.
          +4
          Зато можно купить процессор с большим числом ядер. И более декларативный стиль (foreach, LINQ) позволяет распараллеливать задачи прозрачно.

          Мелкая оптимизация — тупик. Оверхеда не так много, на нем особо не выиграть.

          По этому поводу мне нравится вот этот доклад Мартина Одерски: Future-proofing collections: from mutable to persistent to parallel. Про Scala, но и для C# выводы верны.
            –2
            Процессор с бОльшим числом ядер будет потреблять бОльшую мощность. И грустно было бы покупать чемодан с батарейками только из-за того, что программист поленился преобразовать список длиной в сотню миллионов элементов в массив… И оверхеда очень много: почти всё время работы процессора уходит на перетасовывание байтов в памяти, а не на расчёты.
            А, кстати, как foreach по списку распараллеливается штатными средствами .NET (без подключения всяких Microsoft Practices)?
              0
              К сожалению foreach в C# «оптимизированный» — не через лямбду. Так что придется переписать на ForEach или вообще использовать PLINQ.

              Например в scala аналог foreach — изначально сахар над методом, принимающим лямбду, так что параллелится без переписывания. Вообще в scala уже показано, что декларативная запись легко превращается в оптимизированный, но не наоборот. Тот же аналог foreach добавлением 1 слова (без каких-либо других изменений) превращается в параллельную или оптимизированную (без лямбды) версию.

              А про мощность: спорно. Важно только для мобильных устройств и сейчас они постепенно учатся отключать ядра при малой нагрузке. Так что большое количество слабых ядер по требованию оказывается выгоднее одного мощного ядра постоянно.
                +1
                А про мощность: спорно. Важно только для мобильных устройств и сейчас они постепенно учатся отключать ядра при малой нагрузке. Так что большое количество слабых ядер по требованию оказывается выгоднее одного мощного ядра постоянно.

                Ну… нам сейчас приходится ставить на борт сканера процессор с вдвое меньшей тактовой частотой, чтобы сэкономить дополнительные 6-10 ватт и дать пользователю возможность работать в автономном режиме лишний час. При том, что рынок требует и повышения плотности потока, и более разнообразных возможностей обработки в реальном времени. Тут не только о выборе циклов приходится думать, но и как бы не скопировать массив лишний раз. А уйти с C# не получается — нет ресурсов, да и гибкость потеряем.
                0
                Список в сотню миллионов элементов тем более не надо никуда преобразовывать — память жалко. Как раз для таких ситуаций и придуман IEnumerable (так что там и список-то лишний).
              +11
              Тоже неверно.

              Во-первых, я давно не видел программ, которые бы тормозили из-за разницы производительности между for и foreach — проблемы всегда были на стороне на порядок более медленных компонентов системы.

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

              Ну и в-третьих, если вам важна скорость работы программы в таких деталях, то не пишите на .net — промежуточные оптимизации все равно все убьют.
            +1
            Ваше объяснение результатов вряд ли верно в обоих случаях, потому что еденицы наносекунд на итерацию, тем более, разница всего в 1,5 нс в первом тесте, которую вы объяснили вызовом делегата, — это не то время, за которые происходит вызов.

            Скорее всего, там инлайн полный во всех случаях, разница в паре проверок границ лишних, может быть.

            Кстати, 2,5 нс на итерацию суммы простого массива в цикле — как-то медленно.
              0
              Нет, здесь все правильно. CLR не умеет инлайнить виртуальные вызовы, а любой вызов делегата — виртуальный. И это реально просаживает производительность в синтетических тестах, где в теле цикла практически ничего не делают.
                0
                Объясните, почему самый просто цикл — 2,5 нс. Должно быть 0,5, максимум 1.
                  0
                  А почему, собственно, должно?
                    0
                    Потому что его скорость ограничивает только латентность условного перехода, т. е. 2 такта на итерацию. 2,5 нс это 7,5 тактов, которые тут тратить просто не на что. Проверьте множитель процессора.
                      0
                      Скорее всего, просто тест забыли скомпилировать с /optimize+, или запустили из VS. И то, и другое подавляет оптимизации JIT (и, соответственно, в коде остается проверка на длину на каждой итерации).
              +2
              Мне кажется, что на несинтетических примерах замена for на foreach вообще заметной разницы в скорости не даст. А вот время разбирающихся в коде людей, если увлечься такой оптимизацией, можно и потерять.
                +1
                C# For vs. Foreach — для массивов foreach может оказаться быстрее, чем for, если требуется несколько раз обращаться к элементу по индексу.
                Согласен с комментариями выше — задумываться над выбором for/foreach не должно требоваться — компилятор должен оптимизировать — это его работа. Однако, знать что «под капотом» у обеих конструкций стоит, но не помешала бы статья про оптимизации циклов в .NET, дабы стало в очередной раз ясно, что преждевременная оптимизация — корень зла.
                  +2
                  Обычно стараюсь использовать foreach или .ForEach для краткости и чистоты кода. За исключением случаев, когда в цикле нужно менять элементы коллекции, тогда без for не обойдёшься. Пусть производительность и разная, но в большинстве случаев это не критично. PS: игроделы, не читайте последнее предложение :)
                    0
                    А вы уверены в правильности составленного бенчмарка?
                    Я сделал свою версию замеров производительности в рамках проекта BenchmarkDotNet: примеры ForeachArray и ForeachList. Мои результаты несколько отличаются от ваших (количество итераций — 200000000):
                    ArrayForWithoutOptimization : 143ms
                    ArrayForWithOptimization    : 143ms
                    ArrayForeach                : 142ms
                    ArrayForEach                : 556ms
                    
                    ListForWithoutOptimization  : 280ms
                    ListForWithOptimization     : 213ms
                    ListForeach                 : 628ms
                    ListForEach                 : 833ms
                    

                    По массивам вопросов нет, а вот о производительности итерирования по List-ам я готов подискутировать. Я считаю, что обычный for работает быстрее, как этого и следовало ожидать.
                      0
                      Выше приведены результаты для x64. Для чистоты эксперимента сделал тот же тест для x86 (в этом случае для List-ов пришлось вдвое уменьшить количество итераций, чтобы не было проблем с памятью):
                      ArrayForWithoutOptimization : 111ms
                      ArrayForWithOptimization    : 110ms
                      ArrayForeach                : 110ms
                      ArrayForEach                : 625ms
                      
                      ListForWithoutOptimization  : 106ms
                      ListForWithOptimization     : 106ms
                      ListForeach                 : 375ms
                      ListForEach                 : 451ms
                      

                      Конфигурация моей машины: Intel Core i7-3632QM CPU 2.20GHz, 8Гб ОЗУ
                      +1
                      Оверхед на циклах это абсолютная мелочь. Из критичных по производительности вещей с циклами гораздо чаще встречается неправильный выбор коллекций для работы (игнор существования HashSet или Dictionary там, где необходим поиск по значению элемента).
                        0
                        Могу подкинуть еще одну интересную тему, если хочется покопаться в .NET. Есть такой класс — Dictionaty<TKey, TValue>, для выяснения равенства значений там используется IEqualityComparer. Если почитать исходники, то можно увидеть, что если вызвать конструктор словаря без компарера в качестве параметра, то в качестве компарера будет использован EqualityComparer<TKey>.Default.
                        А он реализован так:

                        [Serializable]
                        internal class GenericEqualityComparer<t>: EqualityComparer<t> where T: IEquatable<t>
                        {
                             [Pure]
                             public override bool Equals(T x, T y) {
                                if (x != null) {
                                    if (y != null) return x.Equals(y);
                                    return false;
                                }
                                if (y != null) return false;
                                return true;
                            }
                        }
                        


                        Т.е. по логике вещей, что бы сравнить 2 целых числа, каждое из чисел нужно преобразовать в ссылку на интерфейс IEquatable<int>, а интерфейс как известно — reference-тип, что бы вызвать метод Equals нужно упаковать объект. И вот тут я немного не догоняю, выходит, что CLR либо умеет вызывать методы объектов value-типов не упаковывая их, что не вяжется с понятием интерфейса, либо поиск в словаре с компарером по умолчанию производит упаковку элементов, а значит приличное количество мусора при интенсивном поиске, о чем нам как-бы говорит сравнение параметров с null! Если порыться профилировщиком, то вроде бы этого не происходит. Интересно, для этого там введены специальные хаки — EnumComparer и ByteComparer?
                          +2
                          CLR умеет вызывать методы объектов value-типов, не упаковывая их. Не совсем понятно, почему это «не вяжется с понятием интерфейса». В приведенном вами коде нет ни одного значения reference-типа. Ведь переменные x и y имеют тип T, а не IEquatable. Про T известно, что он реализовывает IEquatable, но это не означает вызов методов через ссылку интерфейсного типа.

                          Если говорить о конкретной реализации, то при генерации кода JIT создает отдельный вариант метода с дженериками для каждой уникальной комбинации value-типов. Соответственно, в этом варианте все вызовы методов резолвятся в момент JIT-компиляции, т.к. все типы точно известны, и подстановки значения унаследованного типа быть не может (т.к. все value types — sealed).
                          +3
                          Статье явно не хватает сравнения и анализа генерируемого IL кода.
                            0
                            IL от C# отличаться сильно не будет (за исключением разворачивания foreach в for для массива) — что в C# написано, то в один к одному будет в IL.
                            Вся оптимизирующая магия выполняется JIT-компиляцией:
                            — значительная часть кода inline-ится
                            — выкидываются лишние проверки границ
                            и т.д.
                            0
                            Стоило также протестировать скорость выполнения linq-функций: Sum и Aggregate, раз уж для тестов была выбрана задача суммирования последовательности
                              0
                              Заодно советую автору изучить эту статью, тем более, что она вышла всего неделю назад:
                              habrahabr.ru/post/191636/

                              Only users with full accounts can post comments. Log in, please.