use*_*963 25 c# c++ performance f#
我写了一个简单的测试,它创建一个变量,用零初始化它并增加100000000次.
C++在0.36秒内完成.原始C#版本在0.33s新的0.8s 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#.结果是一样的
The*_*ght 34
这非常肯定是由于使用表达式而直接发生的:
for i in seq{1..N} do
在我的机器上,这给出了结果:
亿
00:00:09.1500924
如果我将循环更改为:
for i in 1..N do
结果发生了巨大变化:
亿
00:00:00.1001864
为什么？
这两种方法产生的IL是完全不同的.第二种情况,使用1..N语法简单地以与C#for(int i=1; i<N+1; ++i)循环相同的方式进行编译.
第一种情况完全不同,这个版本产生一个完整的序列,然后由foreach循环枚举.
使用IEnumerables不同的C#和F#版本使用不同的范围函数来生成它们.
C#版本用于System.Linq.Enumerable.RangeIterator生成值范围,而F#版本使用Microsoft.FSharp.Core.Operators.OperatorIntrinsics.RangeInt32.我认为可以安全地假设在这种特殊情况下我们在C#和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
我们可以看到,单步执行枚举器会导致调用所提供的add函数,而不是直接添加更直接的函数.
注意:所有时间都在发布模式下运行(尾调用:开,优化:开).
Luc*_*ski 14
我不太了解F#所以我想看看它产生的代码.这是结果.它只是证实了TheInnerLight的答案.
首先,C++应该能够优化你的for循环,你将获得零(或接近零)的时间..NET编译器和JIT目前不执行此优化,所以让我们比较它们.
这是C#循环的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
这是F#循环的IL:
// [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#的作用:
MoveNext部分(仅一次)Current可枚举的属性,并将其丢弃0MoveNexttrue,或退出循环falseF#循环执行以下操作:
MoveNextfalseCurrent可枚举的属性,并将其值存储在本地0nop (原文如此)所以我们在这里有两点不同:
Current当F#将其存储在本地时,C#会丢弃该属性的值nop由于某种原因,F#在循环中有一个(不做任何)指令超出了我(是的,这是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#nopIL操作码被JIT优化了.nop在x64代码中有一个,但它在循环之后,并且它肯定在这里用于对齐.
然后,我们可以看到两种情况下的代码非常相似,尽管它的结构有点不同.它调用相同的函数,并没有做任何奇怪的事情.
所以,你看到的性能差异肯定是由F#构造它的序列的方式解释的,而不是它的循环机制本身.
Jus*_*mer 10
作为一个围绕这些部分在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 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 - 优化不适用,因为它需要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#代码并尝试应用它.做得好的优化几乎总是受欢迎的.
希望这对某人有趣
我认为正在发生的事情是额外seq的阻止了一些优化.
如果你改为
for i in 1..N
我认为它几乎相当(至少对于c ++)它要快得多