Подтвердить что ты не робот

Почему этот простой код F # в 36 раз медленнее, чем версии С#/С++?

Я написал простой тест, который создает переменную, инициализирует ее нулем и увеличивает 100000000 раз.

С++ делает это за 0,36 с. Оригинальная версия С# в 0.33s Новая в 0.8s F # за 12 секунд.

Я не использую никаких функций, поэтому по умолчанию не проблема с дженериками

F # code

open System
open System.Diagnostics
// Learn more about F# at http://fsharp.org
// See the 'F# Tutorial' project for more help.
[<EntryPoint>]
let main argv = 
    let N = 100000000
    let mutable x = 0
    let watch = new Stopwatch();
    watch.Start();
    for i in seq{1..N} do
        x <- (x+1)
    printfn "%A" x
    printfn "%A" watch.Elapsed
    Console.ReadLine()
        |> ignore
    0 // return an integer exit code

Код С++

#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
#include<time.h>
using namespace std;
int main()
{
    const int N = 100000000;
    int x = 0;
    double start = clock();
    for(int i=0;i<N;++i)
    {
        x = x + 1;
    }
    printf("%d\n",x);
    printf("%.4lf\n",(clock() - start)/CLOCKS_PER_SEC);
    return 0;
}

Код С#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace SpeedTestCSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 100000000;
            int x = 0;
            Stopwatch watch = new Stopwatch();
            watch.Start();

            foreach(int i in Enumerable.Range(0,N))
            //Originally it was for(int i=0;i<N;++i)
            {
                x = x + 1;
            }
            Console.WriteLine(x);
            Console.WriteLine(watch.Elapsed);
            Console.ReadLine();
        }
    }
}

Edit

Замена for (int i = 0; i < N; ++i) на foreach(int i in Enumerable.Range(0,N)) заставляет программу С# работать примерно в 0.8 с, но она все еще намного быстрее, чем f #

Edit

Замените DateTime на StopWatch для F #/С#. Результаты те же

4b9b3361

Ответ 1

Это очень точно происходит непосредственно из-за использования выражения:

for i in seq{1..N} do

На моей машине это дает результат:

100000000

00: 00: 09,1500924

Если я сменил цикл на:

for i in 1..N do

Результат резко меняется:

100000000

00: 00: 00,1001864

Почему?

ИЛ, созданный этими двумя подходами, совершенно иная. Второй случай, используя синтаксис 1..N, просто компилируется так же, как цикл С# for(int i=1; i<N+1; ++i).

Первый случай совершенно другой, эта версия создает полную последовательность, которая затем перечитывается циклом foreach.

Варианты С# и F #, использующие IEnumerables, отличаются тем, что они используют разные функции диапазона для их генерации.

Версия С# использует System.Linq.Enumerable.RangeIterator для создания диапазона значений, в то время как версия F # использует Microsoft.FSharp.Core.Operators.OperatorIntrinsics.RangeInt32. Я считаю безопасным предположить, что разница производительности, которую мы наблюдаем между версиями С# и F # в данном конкретном случае, является результатом характеристик производительности этих двух функций.

svick правильно указать в своем комментарии, что оператор + фактически передается как аргумент функции integralRangeStep.

Для нетривиального случая, когда n <> m это приводит к компилятору F #, используя ProperIntegralRangeEnumerator с реализацией, найденной здесь: https://github.com/Microsoft/visualfsharp/blob/master/src/fsharp/FSharp.Core/prim-types.fs#L6463

let inline integralRangeStepEnumerator (zero,add,n,step,m,f) : IEnumerator<_> =
    // Generates sequence z_i where z_i = f (n + i.step) while n + i.step is in region (n,m)
    if n = m then
        new SingletonEnumerator<_> (f n) |> enumerator 
    else
        let up = (n < m)
        let canStart = not (if up then step < zero else step > zero) // check for interval increasing, step decreasing 
        // generate proper increasing sequence
        { new ProperIntegralRangeEnumerator<_,_>(n,m) with 
                member x.CanStart = canStart
                member x.Before a b = if up then (a < b) else (a > b)
                member x.Equal a b = (a = b)
                member x.Step a = add a step
                member x.Result a = f a } |> enumerator

Мы можем видеть, что переход через Enumerator приводит к вызовам предоставленной функции add, а не к более прямому, прямому добавлению.

Примечание: Все тайминги выполняются в режиме деблокирования (Tail Calls: On, Optimization: On).

Ответ 2

Я не очень хорошо знаю F #, поэтому я хотел заглянуть в код, который он производит. Вот результат. Он просто подтверждает ответ TheInnerLight.

Во-первых, С++ должен иметь возможность оптимизировать цикл for, вы получите нулевое (или почти нулевое) время. Компиляторы .NET и JIT в настоящее время не выполняют эту оптимизацию, поэтому сравните их.

Здесь IL цикла С#:

// [21 28 - 21 58]
IL_000e: ldc.i4.0     
IL_000f: ldc.i4       100000000
IL_0014: call         class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> [System.Core]System.Linq.Enumerable::Range(int32, int32)
IL_0019: callvirt     instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0/*int32*/> class [mscorlib]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator()
IL_001e: stloc.2      // V_2
.try
{

  IL_001f: br.s         IL_002c

// [21 16 - 21 24]
  IL_0021: ldloc.2      // V_2
  IL_0022: callvirt     instance !0/*int32*/ class [mscorlib]System.Collections.Generic.IEnumerator`1<int32>::get_Current()
  IL_0027: pop          

// [22 9 - 22 15]
  IL_0028: ldloc.0      // num1
  IL_0029: ldc.i4.1     
  IL_002a: add          
  IL_002b: stloc.0      // num1

  IL_002c: ldloc.2      // V_2
  IL_002d: callvirt     instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
  IL_0032: brtrue.s     IL_0021
  IL_0034: leave.s      IL_0040
} // end of .try
finally
{
  IL_0036: ldloc.2      // V_2
  IL_0037: brfalse.s    IL_003f
  IL_0039: ldloc.2      // V_2
  IL_003a: callvirt     instance void [mscorlib]System.IDisposable::Dispose()
  IL_003f: endfinally   
} // end of finally

И здесь IL цикла F #:

// [23 5 - 23 138]
IL_000f: ldc.i4.1     
IL_0010: ldc.i4.1     
IL_0011: ldc.i4       100000000
IL_0016: call         class [mscorlib]System.Collections.Generic.IEnumerable`1<int32> [FSharp.Core]Microsoft.FSharp.Core.Operators/OperatorIntrinsics::RangeInt32(int32, int32, int32)
IL_001b: call         class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0/*int32*/> [FSharp.Core]Microsoft.FSharp.Core.Operators::CreateSequence<int32>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0/*int32*/>)
IL_0020: stloc.2      // V_2
IL_0021: ldloc.2      // V_2
IL_0022: callvirt     instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0/*int32*/> class [mscorlib]System.Collections.Generic.IEnumerable`1<int32>::GetEnumerator()
IL_0027: stloc.3      // enumerator
.try
{

// [26 7 - 26 36]
  IL_0028: ldloc.3      // enumerator
  IL_0029: callvirt     instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
  IL_002e: brfalse.s    IL_003f

// [28 9 - 28 41]
  IL_0030: ldloc.3      // enumerator
  IL_0031: callvirt     instance !0/*int32*/ class [mscorlib]System.Collections.Generic.IEnumerator`1<int32>::get_Current()
  IL_0036: stloc.s      current

// [29 9 - 29 15]
  IL_0038: ldloc.0      // func
  IL_0039: ldc.i4.1     
  IL_003a: add          
  IL_003b: stloc.0      // func
  IL_003c: nop          

  IL_003d: br.s         IL_0028
  IL_003f: ldnull       
  IL_0040: stloc.s      V_4
  IL_0042: leave.s      IL_005d
} // end of .try
finally
{

// [34 7 - 34 57]
  IL_0044: ldloc.3      // enumerator
  IL_0045: isinst       [mscorlib]System.IDisposable
  IL_004a: stloc.s      disposable

// [35 7 - 35 30]
  IL_004c: ldloc.s      disposable
  IL_004e: brfalse.s    IL_005a

// [36 9 - 36 29]
  IL_0050: ldloc.s      disposable
  IL_0052: callvirt     instance void [mscorlib]System.IDisposable::Dispose()

  IL_0057: ldnull       
  IL_0058: pop          
  IL_0059: endfinally   
  IL_005a: ldnull       
  IL_005b: pop          
  IL_005c: endfinally   
} // end of finally
IL_005d: ldloc.s      V_4
IL_005f: pop          

Итак, хотя петли немного разные, они в основном делают то же самое.

Вот что делает С#:

  • [0] Отнести к части MoveNext (только один раз)
  • [1] Получите свойство Current перечислимого, и отбросьте его
  • [2] Добавить 1 в локальный 0
  • [3] Вызов MoveNext
  • [4] Вернитесь к [1] ​​на true или выйдите из цикла на false

Цикл F # выполняет следующие действия:

  • [0] Вызов MoveNext
  • [1] Оставьте цикл на false
  • [2] Получите свойство Current перечислимого, и сохраните его значение в локальном
  • [3] Добавить 1 в локальный 0
  • [4] Сделайте паузу с nop (sic)
  • [5] От ветвления до [0]

Итак, у нас есть два отличия:

  • С# отбрасывает значение свойства Current, а F # хранит его в локальном
  • F # имеет инструкцию nop (ничего не делать) в цикле по какой-то причине, что вне меня (и да, это режим Release).

Но только эти различия не объясняют огромного влияния производительности. Давайте посмотрим, что делает JIT с этим.

Примечание. rcx - это первый аргумент в используемом условном вызове x64, который соответствует неявному параметру this в вызовах метода экземпляра.

С#, x64:

            foreach (int i in Enumerable.Range(0, N))
00007FFCF2B94514  xor         ecx,ecx  
00007FFCF2B94516  mov         edx,5F5E100h  
00007FFCF2B9451B  call        00007FFD50EF08F0          // Call Enumerable.Range
00007FFCF2B94520  mov         rcx,rax  
00007FFCF2B94523  mov         r11,7FFCF2A80040h
00007FFCF2B9452D  cmp         dword ptr [rcx],ecx  
00007FFCF2B9452F  call        qword ptr [r11]           // Call GetEnumerator
00007FFCF2B94532  mov         qword ptr [rbp-20h],rax  
00007FFCF2B94536  mov         rcx,qword ptr [rbp-20h]   // Store the IEnumerator in rcx
00007FFCF2B9453A  mov         r11,7FFCF2A80048h        
00007FFCF2B94544  cmp         dword ptr [rcx],ecx  
00007FFCF2B94546  call        qword ptr [r11]           // Call MoveNext
00007FFCF2B94549  test        al,al  
00007FFCF2B9454B  je          00007FFCF2B9457F          // Skip the loop
00007FFCF2B9454D  mov         rcx,qword ptr [rbp-20h]   // Store the IEnumerator in rcx
00007FFCF2B94551  mov         r11,7FFCF2A80050h  
00007FFCF2B9455B  cmp         dword ptr [rcx],ecx  
00007FFCF2B9455D  call        qword ptr [r11]           // Call get_Current
            {
                x = x + 1;
00007FFCF2B94560  mov         ecx,dword ptr [rbp-0Ch]  
00007FFCF2B94563  inc         ecx                       
00007FFCF2B94565  mov         dword ptr [rbp-0Ch],ecx  
            foreach (int i in Enumerable.Range(0, N))
00007FFCF2B94568  mov         rcx,qword ptr [rbp-20h]   // Store the IEnumerator in rcx
00007FFCF2B9456C  mov         r11,7FFCF2A80048h  
00007FFCF2B94576  cmp         dword ptr [rcx],ecx  
00007FFCF2B94578  call        qword ptr [r11]           // Call MoveNext
00007FFCF2B9457B  test        al,al  
00007FFCF2B9457D  jne         00007FFCF2B9454D  
00007FFCF2B9457F  mov         rcx,qword ptr [rsp+20h]  
00007FFCF2B94584  call        00007FFCF2B945C6  
00007FFCF2B94589  nop  
            }

F #, x64:

    for i in seq{1..N} do
00007FFCF2B904F4  mov         ecx,1  
00007FFCF2B904F9  mov         edx,1  
00007FFCF2B904FE  mov         r8d,5F5E100h  
00007FFCF2B90504  call        00007FFD42AA2B80          // Create the sequence
00007FFCF2B90509  mov         rcx,rax  
00007FFCF2B9050C  mov         r11,7FFCF2A90020h  
00007FFCF2B90516  cmp         dword ptr [rcx],ecx  
00007FFCF2B90518  call        qword ptr [r11]           // Call GetEnumerator
00007FFCF2B9051B  mov         qword ptr [rbp-20h],rax  
00007FFCF2B9051F  mov         rcx,qword ptr [rbp-20h]   // Store the IEnumerator in rcx
00007FFCF2B90523  mov         r11,7FFCF2A90028h  
00007FFCF2B9052D  cmp         dword ptr [rcx],ecx  
00007FFCF2B9052F  call        qword ptr [r11]           // Call MoveNext  
00007FFCF2B90532  test        al,al  
00007FFCF2B90534  je          00007FFCF2B90553          // Exit the loop?
        x <- (x+1)
00007FFCF2B90536  mov         rcx,qword ptr [rbp-20h]  
00007FFCF2B9053A  mov         r11,7FFCF2A90030h  
00007FFCF2B90544  cmp         dword ptr [rcx],ecx  
00007FFCF2B90546  call        qword ptr [r11]           // Call get_Current
00007FFCF2B90549  mov         edx,dword ptr [rbp-0Ch]  
00007FFCF2B9054C  inc         edx  
00007FFCF2B9054E  mov         dword ptr [rbp-0Ch],edx  
00007FFCF2B90551  jmp         00007FFCF2B9051F          // Loop
00007FFCF2B90553  mov         rcx,qword ptr [rsp+20h]  
00007FFCF2B90558  call        00007FFCF2B9061C  
00007FFCF2B9055D  nop   

Во-первых, мы замечаем, что С# все еще вызывает Current, даже если он отбрасывает свой результат. Это виртуальный вызов, который не оптимизировался.

Oh и что код операции F # nop IL оптимизирован JIT. В коде x64 есть nop, но это после цикла, и это конечно здесь для целей выравнивания.

Затем мы можем видеть, что код очень схож в двух случаях, хотя он структурирован несколько иначе. Он вызывает те же функции и не делает ничего странного.

Итак, разница в производительности, которую вы видите, определенно объясняется тем, как F # строит свою последовательность, а не сам ее механизм цикла.

Ответ 3

Как человек, который выкопал в компиляторе F # вокруг этих частей, я подумал, что, возможно, могу поделиться некоторыми источниками света на том, что происходит внутри компилятора F #.

Как отмечалось, for i in seq{1..N} создает IEnumerable<> в диапазоне 1..N. Итерация над IEnumerable<> довольно медленная, частично из-за виртуальных вызовов на Current и MoveNext. В принципе, F # может обнаружить этот шаблон и оптимизировать его, но в настоящее время F # не делает.

Предполагается использовать шаблон for i in 1..N, который дает гораздо лучшую производительность, а также уменьшенное давление GC.

Вопрос читателю перед чтением о том, какую производительность мы можем ожидать от выражений:

  • for i in 1L..int64 N
  • for i in 1..2..N

Когда F # тип checker обнаруживает for-each expression, он преобразует его в более примитивное выражение, которое можно более легко преобразовать в код IL, Резервный случай состоит в том, чтобы преобразовать for-each expression в нечто подобное:

// body is the body of the for_each expression, enumerable is what we iterate over
let for_each (body : 'T -> unit) (enumerable : IEnumerable<'T>) : unit =
  let e = enumerable.GetEnumerator ()
  try
    while e.MoveNext () do
      body e.Current
  finally
    e.Dispose ()

Это происходит в функции TcForEachExpr. Любопытный читатель замечает эту строку в этой функции:

// optimize 'for i in n .. m do' 
| Expr.App(Expr.Val(vf,_,_),_,[tyarg],[startExpr;finishExpr],_) 
    when valRefEq cenv.g vf cenv.g.range_op_vref && typeEquiv cenv.g tyarg cenv.g.int_ty -> 
        (cenv.g.int32_ty, (fun _ x -> x), id, Choice1Of3 (startExpr,finishExpr))

Проверка типа фактически выполняет оптимизацию for-each expression формы for i in lowerint32..upperinter32. Казалось бы, более естественным местом было бы сделать это в optimizer. Я подозреваю, что это связано с устаревшими причинами, когда F # не был настолько зрелым, как все новые оптимизации должны были войти в оптимизатор. К сожалению, переместить эту оптимизацию в оптимизатор непросто, поскольку это изменило бы форму дерева выражений для <@ for i in 0..100 @>, скорее всего, нарушив множество кодов кода пользователя. По этой же причине в средство проверки типов не может быть добавлено больше оптимизаций. Это радость и задача поддержания обратной совместимости.

Код оптимизации также позволяет нам ответить на предыдущие вопросы:

  • for i in 1L..int64 N - Оптимизация не будет применяться, поскольку для нее требуется int32
  • for i in 1..2..N - Оптимизация не будет применяться, потому что нет случая для range_step_op_vref

Что делает резервный случай, это создать объект seq вокруг выражения диапазона и перебрать его с помощью .Current/.MoveNext. Он будет работать, но производительность будет плохой.

Также существует оптимизация для итерации по массивам:

// optimize 'for i in arr do' 
| _ when isArray1DTy cenv.g enumExprTy  -> 
    let arrVar,arrExpr = mkCompGenLocal m "arr" enumExprTy
    let idxVar,idxExpr = mkCompGenLocal m "idx" cenv.g.int32_ty
    let elemTy = destArrayTy cenv.g enumExprTy

Итак, повторение массивов будет быстрым (как и на С#), но как насчет строк (что быстро в С#) или других структур данных?

Оказывается, оптимизатор имеет больше случаев, когда он обнаруживает итерацию по строкам, спискам fsharp и циклам с шагом 1 и -1 и преобразует их в эффективный for loops (большинство из которых происходит в DetectAndOptimizeForExpression).

Код, демонстрирующий некоторые из оптимизаций или пропущенных возможностей для обсуждаемых оптимизаций

open System.Collections.Generic

let total = 10000000
let outer = 10
let inner = total / outer

let stopWatch = 
  let sw = System.Diagnostics.Stopwatch ()
  sw.Start ()
  sw

let timeIt (name : string) (a : unit -> 'T) : unit = // ' 
  let t = stopWatch.ElapsedMilliseconds
  let v = a ()
  for i = 1 to (outer - 1) do
    a () |> ignore
  let d = stopWatch.ElapsedMilliseconds - t
  printfn "%s, elapsed %d ms, result %A" name d v

let case1 () = 
  // Slow because it fallbacks into slow but safe code pattern
  let mutable x = 0
  for i in seq{1..inner} do
    x <- x+1
  x

let case2 () = 
  // Fast because the optimization in TypeChecker.fs matches
  let mutable x = 0
  for i in 1..inner do
    x <- x+1
  x

let case3 () = 
  // Slow because the optimization in TypeChecker.fs requires int32
  let mutable x = 0
  for i in 1L..int64 inner do
    x <- x+1
  x

let case4 () = 
  // Slow because the optimization in TypeChecker.fs doesn't recognize b..inc..e patterns
  let mutable x = 0
  for i in 1..2..inner do
    x <- x+1
  x

let case5 () = 
  // Fast because Optimizer.fs recognizes this pattern
  let mutable x = 0
  for i in 1..1..inner do
    x <- x+1
  x

let case6 () = 
  // Fast because Optimizer.fs recognizes this pattern
  let mutable x = 0
  for i in inner..(-1)..1 do
    x <- x+1
  x


[<EntryPoint>]
let main argv =
  timeIt "case1" case1
  timeIt "case2" case2
  timeIt "case3" case3
  timeIt "case4" case4
  timeIt "case5" case5
  timeIt "case6" case6

  0

Я хотел бы поощрить любого, кто считает, что у них есть полезное улучшение для оптимизатора F #, чтобы загрузить код F # и попытаться применить его. Хорошо сделанные оптимизации почти всегда приветствуются.

Надеюсь, это было интересно кому-то

Ответ 4

Я думаю, что происходит то, что дополнительный seq предотвращает некоторые оптимизации.

Если вы измените на

for i in 1..N 

который, как мне кажется, почти эквивалентен (по крайней мере, на С++), он намного быстрее