Проход по массиву: прямой, обратный или итератор?

#c_sharp #массивы #net

Предположим есть массив, тип данных и длина любые, например:

byte[] arr = new byte[16777216];


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

foreach (byte b in arr)
    sum += b;


по индексу прямым ходом

for (int i = 0; i < arr.Length; i++)
    sum += arr[i];


либо обратным

for (int i = arr.Length - 1; i >= 0; i--)
    sum += arr[i];


?

Есть ли какие-то общие рекомендации, или всё будет сильно зависеть от типа элемента
массива?

upd.

Я конечно же попробовал сравнить эти подходы (код, который я использовал, ниже),
и получил примерно следующие результаты:

C:\...\bin\x64\Release>ConsoleApplication2.exe
foreach: 11135 msec
for forward: 11141 msec
for backward: 15147 msec

C:\...\bin\x86\Release>ConsoleApplication2.exe
foreach: 11304 msec
for forward: 69305 msec
for backward: 68075 msec


Мне не совсем понятны две вещи. Первое - это внушительная разница между for и foreach
для x86. Я попытался изучить вопрос поверхностно, но такого сходу не встретил, в основном
пишут, что for/foreach должны быть сравнимы. Т.е. возможно я просто как-то неправильно
сравниваю, или это конкретно из-за того, что операция в цикле сумма. И второе - с чем
(хотя бы примерно) может быть связано то, что в x64 обратный ход на 10-15% медленнее.

Вот код, который я использовал:

public static void Main()
{
    Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
    Thread.CurrentThread.Priority = ThreadPriority.Highest;

    const int repeats = 2000;
    byte[] arr = new byte[16777216];

    Random rnd = new Random();
    rnd.NextBytes(arr);

    long sum = 0;

    Stopwatch sw = new Stopwatch();

    long ms_foreach = 0;
    long ms_for_fwd = 0;
    long ms_for_back = 0;

    for (int r = 0; r < repeats; r++)
    {
        sum = 0;
        sw.Reset();
        sw.Start();
        foreach (byte b in arr)
            sum += b;
        sw.Stop();
        ms_foreach += sw.ElapsedMilliseconds;

        sum = 0;
        sw.Reset();
        sw.Start();
        for (int i = 0; i < arr.Length; i++)
            sum += arr[i];
        sw.Stop();
        ms_for_fwd += sw.ElapsedMilliseconds;

        sum = 0;
        sw.Reset();
        sw.Start();
        for (int i = arr.Length - 1; i >= 0; i--)
            sum += arr[i];
        sw.Stop();
        ms_for_back += sw.ElapsedMilliseconds;
    }

    Console.WriteLine("foreach: {0} msec", ms_foreach);
    Console.WriteLine("for forward: {0} msec", ms_for_fwd);
    Console.WriteLine("for backward: {0} msec", ms_for_back);
}


Код проверял на разных машинах и компилировал под .net 2.0, 3.5, 4.0, 4.5 - результаты
схожи.
    

Ответы

Ответ 1

Ок, почему может быть, а может и не быть разницы. 

[MethodImpl(MethodImplOptions.NoInlining)]
public static long ForEach(byte [] arr)
{
    long sum = 0;
    foreach (byte b in arr)
        sum += b;
    return sum;
}

[MethodImpl(MethodImplOptions.NoInlining)]
public static long ForForward(byte[] arr)
{
    long sum = 0;
    for (int i = 0; i < arr.Length; i++)
        sum += arr[i];
    return sum;
}

[MethodImpl(MethodImplOptions.NoInlining)]
public static long ForBackward(byte[] arr)
{
    long sum = 0;
    for (int i = 0; i < arr.Length; i++)
        sum += arr[i];
    return sum;
}


Ваш код на C# проходит две стадии копмиляции. 

Первая - компиляция в IL. После нее, очевидно, методы будут скопмилированы в чуть
разный код на IL. Сам по себе foreach будет превращен в обычный перебор массива по
элементам, без вызова IEnumerable:

.method public hidebysig static int64  ForEach(uint8[] arr) cil managed noinlining
{
  // Code size       30 (0x1e)
  .maxstack  2
  .locals init ([0] int64 sum,
           [1] uint8[] V_1,
           [2] int32 V_2,
           [3] uint8 b)
  IL_0000:  ldc.i4.0
  IL_0001:  conv.i8
  IL_0002:  stloc.0
  IL_0003:  ldarg.0
  IL_0004:  stloc.1
  IL_0005:  ldc.i4.0
  IL_0006:  stloc.2
  IL_0007:  br.s       IL_0016
  IL_0009:  ldloc.1
  IL_000a:  ldloc.2
  IL_000b:  ldelem.u1
  IL_000c:  stloc.3
  IL_000d:  ldloc.0
  IL_000e:  ldloc.3
  IL_000f:  conv.u8
  IL_0010:  add
  IL_0011:  stloc.0
  IL_0012:  ldloc.2
  IL_0013:  ldc.i4.1
  IL_0014:  add
  IL_0015:  stloc.2
  IL_0016:  ldloc.2
  IL_0017:  ldloc.1
  IL_0018:  ldlen
  IL_0019:  conv.i4
  IL_001a:  blt.s      IL_0009
  IL_001c:  ldloc.0
  IL_001d:  ret
} // end of method Program::ForEach


Вариант для For будет отличатся от него отсутствием одной локальной переменной -
[3] uint8 b, и, соответственно, будет меньше на пару операций.

После этого, при непосредственном выполнении, код компилируется JIT-ом в машинный.
Вот результат (на моей машине) для x64:

ForEach:

            long sum = 0;
00007FFB5E8604F0  xor         eax,eax  
            foreach (byte b in arr)
00007FFB5E8604F2  mov         rdx,rcx  
00007FFB5E8604F5  xor         ecx,ecx  
00007FFB5E8604F7  mov         r8d,dword ptr [rdx+8]  
00007FFB5E8604FB  test        r8d,r8d  
00007FFB5E8604FE  jle         00007FFB5E86051A  
00007FFB5E860500  movsxd      r9,ecx  
00007FFB5E860503  movzx       r9d,byte ptr [rdx+r9+10h]  
                sum += b;
00007FFB5E860509  and         r9d,0FFFFFFFFh  
00007FFB5E860510  add         rax,r9  
00007FFB5E860513  inc         ecx  
            foreach (byte b in arr)
00007FFB5E860515  cmp         r8d,ecx  
00007FFB5E860518  jg          00007FFB5E860500  
00007FFB5E86051A  ret  


For:

            long sum = 0;
00007FFB5E860530  xor         eax,eax  
            for (int i = 0; i < arr.Length; i++)
00007FFB5E860532  xor         edx,edx  
00007FFB5E860534  mov         r8d,dword ptr [rcx+8]  
00007FFB5E860538  test        r8d,r8d  
00007FFB5E86053B  jle         00007FFB5E860557  
                sum += arr[i];
00007FFB5E86053D  movsxd      r9,edx  
00007FFB5E860540  movzx       r9d,byte ptr [rcx+r9+10h]  
00007FFB5E860546  and         r9d,0FFFFFFFFh  
00007FFB5E86054D  add         rax,r9  
            for (int i = 0; i < arr.Length; i++)
00007FFB5E860550  inc         edx  
00007FFB5E860552  cmp         r8d,edx  
00007FFB5E860555  jg          00007FFB5E86053D  
00007FFB5E860557  ret  


Обратный For:

            long sum = 0;
00007FFB5E850570  sub         rsp,28h  
00007FFB5E850574  xor         eax,eax  
            for (int i = arr.Length - 1; i >= 0; i--)
00007FFB5E850576  mov         edx,dword ptr [rcx+8]  
00007FFB5E850579  lea         r8d,[rdx-1]  
00007FFB5E85057D  test        r8d,r8d  
00007FFB5E850580  jl          00007FFB5E8505A2  
                sum += arr[i];
00007FFB5E850582  cmp         r8d,edx  
00007FFB5E850585  jae         00007FFB5E8505A7  
00007FFB5E850587  movsxd      r9,r8d  
00007FFB5E85058A  movzx       r9d,byte ptr [rcx+r9+10h]  
00007FFB5E850590  and         r9d,0FFFFFFFFh  
00007FFB5E850597  add         rax,r9  
            for (int i = arr.Length - 1; i >= 0; i--)
00007FFB5E85059A  dec         r8d  
00007FFB5E85059D  test        r8d,r8d  
00007FFB5E8505A0  jge         00007FFB5E850582  
00007FFB5E8505A2  add         rsp,28h  
00007FFB5E8505A6  ret  
00007FFB5E8505A7  call        00007FFBBE301A08  
00007FFB5E8505AC  int         3  


Видно две вещи:


Выполняемый код для foreach и for - идентичен. Отличаются только регистры (edx и
ecx поменялись местами)
Выполняемый код для обратного for отличается только направлением изменения переменной
и ее проверкой - test вместо cmp. 


Когда-то давно, во времена динозавров test работал ощутимо быстрее, чем cmp - и обратные
for были в моде. Сейчас - нет никакой разницы, по крайней мере на десктопных процессорах. 

Обратный for может быть чуть медленее из-за особенностей префетча памяти - процессор
предполагет, память будет использована в прямом порядке, и обращение к предыдущей странице
становится для него неожиданностью. Но опять же, современным процессорам относительно
все равно. 



Что же происходит на x86?

На этой платформе выстреливает проблема с long. Он просто не влазит в регистры, и
JIT-у приходится крутиться, разбивая операции сложения на две. И, соответственно, используя
два регистра для хранения результата. И он при этом умудряется налажать в случае For.
Вот кусок суммирования:

foreach:

        foreach (byte b in arr)
011F04BA  movzx       eax,byte ptr [ecx+esi+8]  
            sum += b;
011F04BF  xor         edx,edx  
011F04C1  add         ebx,eax  
011F04C3  adc         edi,edx  
011F04C5  inc         esi  
        foreach (byte b in arr)
011F04C6  cmp         dword ptr [ecx+4],esi  
011F04C9  jg          011F04BA  
        return sum;


в for:

                sum += arr[i];
011F04FF  movzx       eax,byte ptr [ecx+esi+8]  
011F0504  xor         edx,edx  
011F0506  add         eax,ebx  
011F0508  adc         edx,edi  
011F050A  mov         ebx,eax  
011F050C  mov         edi,edx  
            for (int i = 0; i < arr.Length; i++)
011F050E  inc         esi  
011F050F  cmp         dword ptr [ebp-10h],esi  
011F0512  jg          011F04FF  


Отличается направление сложения. Для foreach пракически выполняется:

(edi ebx) += (edx eax)


Для for оптимизатор лажает и делает

(edx eax) += (edi ebx)
(edi ebx) =  (edx eax)


Вот это перекладывание и дает вашу разницу на x86.

Основной вывод из этого - используйте x64. Это добро. Под него есть новый хороший
JIT. А x86 - зло :)


Ответ 2

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

В большинстве случаев компилятор сам оптимизирует код так, что разница исчезнет.

Вывод: Не оптимизируйте то, что может оптимизировать компилятор. Используйте тот
вариант, который понятнее отражает логику процесса.

Кому интересно, не оптимизированный IL-код отдельных выражений можно посмотреть с
помощью LINQPad.

UPD:
Виртуальная машина 2008R2 на Hyper-V, .NET 4.5
Для x64:

foreach: 22107 msec
for forward: 22127 msec
for backward: 22086 msec


тут все как ожидалось: разница в пределах погрешности измерения. У вас скорее всего
что-то таки вклинилось в процесс, не смотря на приоритеты, и испортило статистику,
например антивирус или еще что-то уровня ядра. 

Для x86:

foreach: 22309 msec
for forward: 90839 msec
for backward: 74015 msec


А вот это действительно загадка... Похоже на баг компилятора, т.к. в IL-коде различия
между вариантами не существенны вроде бы...