Производительность структурных кортежей

Следующая программа F # определяет функцию, которая возвращает меньшую из двух пар int, представленных как структурные кортежи, и для запуска требуется 1.4s:

let [<EntryPoint>] main _ =
  let min a b : int = if a < b then a else b
  let min (struct(a1, b1)) (struct(a2, b2)) = struct(min a1 a2, min b1 b2)
  let mutable x = struct(0, 0)
  for i in 1..100000000 do
    x <- min x (struct(i, i))
  0

Если я декомпилирую CIL на С#, я получаю этот код:

    public static int MinInt(int a, int b)
    {
        if (a < b)
        {
            return a;
        }
        return b;
    }

    public static System.ValueTuple<int, int> MinPair(System.ValueTuple<int, int> _arg2, System.ValueTuple<int, int> _arg1)
    {
        int b = _arg2.Item2;
        int a = _arg2.Item1;
        int b2 = _arg1.Item2;
        int a2 = _arg1.Item1;
        return new System.ValueTuple<int, int>(MinInt(a, a2), MinInt(b, b2));
    }

    public static void Main(string[] args)
    {
        System.ValueTuple<int, int> x = new System.ValueTuple<int, int>(0, 0);
        for (int i = 1; i <= 100000000; i++)
        {
            x = MinPair(x, new System.ValueTuple<int, int>(i, i));
        }
    }

Перекомпиляция с компилятором С# занимает всего 0,3 с, что на 4 раза быстрее, чем исходный F #.

Я не понимаю, почему одна программа намного быстрее, чем другая. Я даже декомпилировал обе версии для CIL и не вижу никакой очевидной причины. Вызов функции С# Min из F # дает ту же (плохую) производительность. CIL внутренней петли вызывающего абонента буквально идентичны.

Может ли кто-нибудь объяснить эту существенную разницу в производительности?

Ответы

Ответ 1

Вы используете оба примера в одной и той же архитектуре. Я получаю ~ 1.4 сек на x64 для кода F # и С# и ~ 0,6 сек на x86 для F # и ~ 0.3 сек на x86 для С#.

Как вы говорите, при декомпиляции сборок код выглядит довольно похожим, но при анализе кода IL появляются некоторые диссимиляции:

F # - let min (struct(a1, b1)) (struct(a2, b2)) ...

.maxstack 5
.locals init (
  [0] int32 b1,
  [1] int32 a1,
  [2] int32 b2,
  [3] int32 a2
)

IL_0000: ldarga.s _arg2
IL_0002: ldfld !1 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item2
IL_0007: stloc.0
IL_0008: ldarga.s _arg2
IL_000a: ldfld !0 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item1
IL_000f: stloc.1
IL_0010: ldarga.s _arg1
IL_0012: ldfld !1 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item2
IL_0017: stloc.2
IL_0018: ldarga.s _arg1
IL_001a: ldfld !0 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item1
IL_001f: stloc.3
IL_0020: nop
IL_0021: ldloc.1
IL_0022: ldloc.3
IL_0023: call int32 Program::[email protected](int32, int32)
IL_0028: ldloc.0
IL_0029: ldloc.2
IL_002a: call int32 Program::[email protected](int32, int32)
IL_002f: newobj instance void valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::.ctor(!0, !1)
IL_0034: ret

С# - MinPair

.maxstack 3
.locals init (
  [0] int32 b,
  [1] int32 b2,
  [2] int32 a2
)

IL_0000: ldarg.0
IL_0001: ldfld !1 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item2
IL_0006: stloc.0
IL_0007: ldarg.0
IL_0008: ldfld !0 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item1
IL_000d: ldarg.1
IL_000e: ldfld !1 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item2
IL_0013: stloc.1
IL_0014: ldarg.1
IL_0015: ldfld !0 valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::Item1
IL_001a: stloc.2
IL_001b: ldloc.2
IL_001c: call int32 PerfItCs.Program::MinInt(int32, int32)
IL_0021: ldloc.0
IL_0022: ldloc.1
IL_0023: call int32 PerfItCs.Program::MinInt(int32, int32)
IL_0028: newobj instance void valuetype [System.ValueTuple]System.ValueTuple`2<int32, int32>::.ctor(!0, !1)
IL_002d: ret

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

Другие функции очень похожи.

Разборка x86 дает следующее:

F # - петля

; F#
; struct (i, i) 
01690a7e 8bce            mov     ecx,esi
01690a80 8bd6            mov     edx,esi
; Loads x (pair) onto stack
01690a82 8d45f0          lea     eax,[ebp-10h]
01690a85 83ec08          sub     esp,8
01690a88 f30f7e00        movq    xmm0,mmword ptr [eax]
01690a8c 660fd60424      movq    mmword ptr [esp],xmm0
; Push new tuple on stack
01690a91 52              push    edx
01690a92 51              push    ecx
; Loads pointer to x into ecx (result will be written here)
01690a93 8d4df0          lea     ecx,[ebp-10h]
; Call min
01690a96 ff15744dfe00    call    dword ptr ds:[0FE4D74h]
; Increase i
01690a9c 46              inc     esi
01690a9d 81fe01e1f505    cmp     esi,offset FSharp_Core_ni+0x6be101 (05f5e101)
; Reached the end?
01690aa3 7cd9            jl      01690a7e

С# - цикл

; C#
; Loads x (pair) into ecx, eax
02c2057b 8d55ec          lea     edx,[ebp-14h]
02c2057e 8b0a            mov     ecx,dword ptr [edx]
02c20580 8b4204          mov     eax,dword ptr [edx+4]
; new System.ValueTuple<int, int>(i, i) 
02c20583 8bfe            mov     edi,esi
02c20585 8bd6            mov     edx,esi
; Push x on stack
02c20587 50              push    eax
02c20588 51              push    ecx
; Push new tuple on stack
02c20589 52              push    edx
02c2058a 57              push    edi
; Loads pointer to x into ecx (result will be written here)
02c2058b 8d4dec          lea     ecx,[ebp-14h]
; Call MinPair
02c2058e ff15104d2401    call    dword ptr ds:[1244D10h]
; Increase i
02c20594 46              inc     esi
; Reached the end?
02c20595 81fe00e1f505    cmp     esi,5F5E100h
02c2059b 7ede            jle     02c2057b

Трудно понять, почему код F # должен здесь значительно хуже. Код выглядит примерно эквивалентным с исключением того, как x загружается в стек. До тех пор, пока кто-нибудь не объяснит, почему я собираюсь предположить, что его movq имеет более низкую задержку, чем push, и поскольку все инструкции манипулируют стеком, CPU не может изменить порядок инструкций, чтобы уменьшить задержку movq.

Почему дрожание выбрало movq для кода F #, а не для кода С#, который я сейчас не знаю.

Для x64 производительность, похоже, ухудшается из-за большего количества накладных расходов в прелюдиях метода и более сглаживания из-за сглаживания. Это главным образом спекуляция с моей стороны, но из кода сборки трудно понять, что, кроме остановки, может снизить производительность x64 в 4 раза.

Помечая min как встроенный, x64 и x86 работают в ~ 0,15 сек. Неудивительно, что это устраняет все накладные расходы из прелюдий метода и много чтения и записи в стек.

Маркировка методов F # для агрессивной вставки (с помощью [MethodImpl (MethodImplOptions.AggressiveInlining)]) не работает, поскольку компилятор F # удаляет все такие атрибуты, что означает, что дрожание никогда не видит его, но маркировка методов С# для агрессивной вставки делает код С# запущенным в ~ 0,15 сек.

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

Фракция x64, вероятно, могла бы улучшить работу по более точной настройке параметров в стеке. Я думаю, используя push, поскольку джиттер x86 предпочтительнее над mov, поскольку семантика push более ограничена, но это только предположение с моей стороны.

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

Честно говоря, я не уверен, что это помогает OP, но, надеюсь, это было несколько интересно.

PS. Я запускаю код на .NET 4.6.2 на i5 3570K