Код не связанный с циклом замедляет его

Question

Я столкнулся с необычной ситуацией. Строка кода, добавленная перед циклом и никак с ним не связанная, замедляет выполнение цикла. Вот как это выглядит в "уменьшенном виде".

У меня есть метод с примитивным циклом:

int[] array = new int[ElemCnt];

public int Sum()
{
    int sum = 0;

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

    return sum;
}

Этот метод модифицируется затем следующим образом:

long state = 1;

public int Sum2()
{
    int sum = 0;

    if (Interlocked.Read(ref state) == 0)
        return sum;

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

    return sum;
}

т.е. просто добавляется проверка перед циклом.

Логично предположить, что время выполнения этой проверки можно оценить некой константой. Время выполнения второго метода (при худшем исходе) тогда можно оценить как T2 ≈ T + C, где T - время выполнения первого метода, а C - время выполнения проверки (CPU считаем не загружен). С ростом длины массива следует ожидать, очевидно, что время выполнения двух методов будет всё менее различимым (T2 ≈ T).

Такого, однако, не происходит:

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19044.1766 (21H2)
Intel Core i5-4690 CPU 3.50GHz (Haswell), 1 CPU, 4 logical and 4 physical cores
.NET SDK=6.0.301
  [Host]     : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
  DefaultJob : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT

Method	ElemCnt	Mean	Error	StdDev	Ratio	RatioSD
Sum	1000	590.1 ns	6.22 ns	5.81 ns	1.00	0.00
Sum2	1000	1,896.4 ns	9.88 ns	9.24 ns	3.21	0.03

Sum	10000	5,729.5 ns	27.40 ns	24.29 ns	1.00	0.00
Sum2	10000	18,929.2 ns	208.10 ns	194.66 ns	3.30	0.03

Sum	100000	57,273.8 ns	258.89 ns	242.17 ns	1.00	0.00
Sum2	100000	187,707.1 ns	2,121.93 ns	1,984.85 ns	3.28	0.03

Sum	1000000	590,207.1 ns	9,395.29 ns	8,328.68 ns	1.00	0.00
Sum2	1000000	1,943,186.9 ns	34,793.55 ns	32,545.90 ns	3.29	0.06

т.е. в действительности получается T2 ≈ K * T!

Это наводит на мысль о том, что во втором случае цикл выполняется медленнее. Будто бы добавленная проверка каким-то образом замедляет цикл. В чём здесь дело?

Код бенчмарка:

public class LoopBench
{
    int[] array = null;
    long state = 1;

    [Params(1000, 10000, 100000, 1000000)]
    public int ElemCnt { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        array = new int[ElemCnt];
    }

    [Benchmark(Baseline = true)]
    public int Sum()
    {
        int sum = 0;

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

        return sum;
    }

    [Benchmark]
    public int Sum2()
    {
        int sum = 0;

        if (Interlocked.Read(ref this.state) == 0)
            return sum;

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

        return sum;
    }
}

Answer 1

В чём здесь дело?

Если сравнивать IL-код двух методов, то ничего криминального не просматривается.

Вот так выглядит IL второго метода:

.maxstack  3
.locals init (int32 V_0, int32 V_1)
IL_0000:  ldc.i4.0
IL_0001:  stloc.0
IL_0002:  ldarg.0
IL_0003:  ldflda     int64 LoopBench::state
IL_0008:  call       int64 Interlocked::Read(int64&)
IL_000d:  brtrue.s   IL_0011
IL_000f:  ldloc.0
IL_0010:  ret
IL_0011:  ldc.i4.0
IL_0012:  stloc.1
IL_0013:  br.s       IL_0024
IL_0015:  ldloc.0
IL_0016:  ldarg.0
IL_0017:  ldfld      int32[] LoopBench::'array'
IL_001c:  ldloc.1
IL_001d:  ldelem.i4
IL_001e:  add
IL_001f:  stloc.0
IL_0020:  ldloc.1
IL_0021:  ldc.i4.1
IL_0022:  add
IL_0023:  stloc.1
IL_0024:  ldloc.1
IL_0025:  ldarg.0
IL_0026:  ldfld      int32[] LoopBench::'array'
IL_002b:  ldlen
IL_002c:  conv.i4
IL_002d:  blt.s      IL_0015
IL_002f:  ldloc.0
IL_0030:  ret

Для первого метода IL-код я не привожу, т.к. он практически идентичен и выглядит так, как если бы из кода второго метода выкинули инструкции с IL_0002 по IL_0010 (собственно проверка и возврат). Что касается цикла, и в особенности тела цикла (с IL_0015 по IL_002d) - различия отсутствуют.

А вот JIT генерирует немного разный код. И в теле цикла как раз таки есть отличия.

Код первого метода, если выкинуть всё второстепенное, выглядит так:

; LoopBench.Sum()
       sub       rsp,28
       xor       eax,eax                        // sum = 0
       xor       edx,edx                        // i = 0
       ...
M00_L00:
       ...
       movsxd    r9,edx                 
       add       eax,[r8+r9*4+10]               // sum += array[i]
       inc       edx                            // i++
       cmp       [rcx+8],edx
       jg        short M00_L00                  // array.Length > i
M00_L01:
       add       rsp,28
       ret

А код второго метода (также без второстепенных деталей) - так:

; LoopBench.Sum2()
       sub       rsp,28
       xor       eax,eax                        // sum = 0
       mov       [rsp+24],eax                   // [stack] <- sum
       ...
M00_L00:
       xor       eax,eax                        // i = 0
       ...
M00_L01:
       ...
       movsxd    r8,eax
       mov       r9d,[rsp+24]                   // sum <- [stack]
       add       r9d,[rcx+r8*4+10]              // sum += array[i]
       inc       eax                            // i++
       cmp       [rdx+8],eax
       jg        short M00_L03                  // array.Length > i
M00_L02:
       mov       eax,r9d                        // return sum
       add       rsp,28
       ret
M00_L03:
       mov       [rsp+24],r9d                   // [stack] <- sum
       jmp       short M00_L01

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

Работа со стеком не сказывалась бы заметно, если бы в цикле было много работы. Но здесь её очень мало. Поэтому такая код-генерация выглядит скорее нетипично, т.к. циклам с небольшим телом (их детекции и оптимизации) компилятор уделяет особое внимание.

Будто бы добавленная проверка каким-то образом замедляет цикл

Нет, сама проверка не замедляет выполнение цикла. Но её присутствие заставляет JIT генерировать для цикла менее производительный код.

Такое поведение RyuJIT компилятора - регрессия от предыдущих версий:

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19044.1766 (21H2)
Intel Core i5-4690 CPU 3.50GHz (Haswell), 1 CPU, 4 logical and 4 physical cores
.NET SDK=6.0.301
  [Host]             : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
  .NET 6.0           : .NET 6.0.6 (6.0.622.26707), X64 RyuJIT
  .NET 5.0           : .NET 5.0.17 (5.0.1722.21314), X64 RyuJIT
  .NET Core 3.1      : .NET Core 3.1.26 (CoreCLR 4.700.22.26002, CoreFX 4.700.22.26801), X64 RyuJIT
  .NET Core 2.2      : .NET Core 2.2.8 (CoreCLR 4.6.28207.03, CoreFX 4.6.28208.02), X64 RyuJIT
  .NET Framework 4.8 : .NET Framework 4.8 (4.8.4515.0), X64 RyuJIT

Method	Runtime	Mean	Error	StdDev	Ratio	RatioSD
Sum	.NET 6.0	587,219.9 ns	11,480.13 ns	10,738.52 ns	1.00	0.00
Sum2	.NET 6.0	1,943,794.5 ns	15,662.22 ns	13,078.66 ns	3.33	0.04

Sum	.NET 5.0	584,441.7 ns	9,659.41 ns	9,035.41 ns	1.00	0.00
Sum2	.NET 5.0	1,955,357.4 ns	18,500.14 ns	16,399.89 ns	3.35	0.06

Sum	.NET Core 3.1	597,269.8 ns	8,984.42 ns	8,404.03 ns	1.00	0.00
Sum2	.NET Core 3.1	1,987,871.5 ns	35,514.92 ns	33,220.67 ns	3.33	0.09

Sum	.NET Core 2.2	585,353.0 ns	7,527.64 ns	7,041.36 ns	1.00	0.00
Sum2	.NET Core 2.2	576,804.1 ns	2,975.21 ns	2,637.45 ns	0.99	0.01

Sum	.NET Framework 4.8	580,485.7 ns	5,634.76 ns	5,270.76 ns	1.00	0.00
Sum2	.NET Framework 4.8	591,283.8 ns	8,772.34 ns	8,205.65 ns	1.02	0.02

В .NET Framework 4.8 и .NET Core 2.2 всё было ещё не так плохо :)

О проблеме я сообщил "куда следует". Возможно она будет исправлена в будущих версиях .NET.

БЛОГ НА HUSL

Код не связанный с циклом замедляет его

Ответы (1 шт):