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

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

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

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

Код F #

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

Код C ++

#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;
}

Код C #

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();
}
}
}

редактировать

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

редактировать

Заменены DateTime с StopWatch для F # / C #. Результаты одинаковы

25

Решение

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

for i in seq{1..N} do

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

100000000

00: 00: 09,1500924

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

for i in 1..N do

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

100000000

00: 00: 00,1001864

Зачем?

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

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

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

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

Свик правильно указать в своем комментарии, что + оператор на самом деле передается в качестве аргумента 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 функция, а не более прямое, прямое добавление.

Замечания: Все тайминги работают в режиме Release (Tail Calls: On, Optimization: On).

32

Другие решения

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

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

Вот IL цикла C #:

// [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

Таким образом, хотя циклы немного отличаются, они в основном делают одно и то же.

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

  • [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 (Так в оригинале)
  • [5] Ветвь к [0]

Таким образом, у нас есть два отличия здесь:

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

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

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

C #, 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

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

Ох, и это F # nop Код операции IL оптимизирован с помощью JIT. Eсть nop в коде x64, но это после цикл, и это, безусловно, здесь для целей выравнивания.

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

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

14

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

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

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

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

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

Когда F # тип проверки обнаруживает 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, Казалось бы, более естественным местом было бы сделать это в оптимизатор. Я подозреваю, что это по унаследованным причинам, когда 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

Таким образом, перебор массивов будет быстрым (как в C #), но как быть со строками (которые быстры в C #) или другими структурами данных?

Оказывается, что оптимизатор имеет больше случаев, когда он обнаруживает итерации по строкам, спискам 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 # и пытаться его применять. Хорошо выполненная оптимизация почти всегда приветствуется.

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

10

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

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

for i in 1..N

что я думаю, что в значительной степени эквивалентно (по крайней мере, C ++), это гораздо быстрее

6
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector