Почему этот простой код 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 #. Результаты одинаковы
Решение
Это определенно происходит непосредственно как следствие использования выражения:
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).
Другие решения
Я не очень хорошо знаю 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 # создает свою последовательность, а не самим механизмом циклирования.
Как человек, который копался в компиляторе 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 Nfor 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— Оптимизация не будет применяться, потому что это требует int32for 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 # и пытаться его применять. Хорошо выполненная оптимизация почти всегда приветствуется.
Надеюсь, это было кому-то интересно
Я думаю, что происходит то, что дополнительный seq предотвращает некоторые оптимизации.
Если вы измените на
for i in 1..N
что я думаю, что в значительной степени эквивалентно (по крайней мере, C ++), это гораздо быстрее