为什么 F# 比 C# 慢这么多？（质数基准）

Question

我认为 F# 应该比 C# 更快，我制作了一个可能很糟糕的基准测试工具，C# 得到了 16239 毫秒，而 F# 在 49583 毫秒时表现更差。有人能解释一下这是为什么吗？我正在考虑离开 F# 并回到 C#。是否可以使用更快的代码在 F# 中获得相同的结果？这是我使用的代码，我尽可能地使它相等。F#（49583 毫秒）open Systemopen System.Diagnosticslet stopwatch = new Stopwatch()stopwatch.Start()let mutable isPrime = truefor i in 2 .. 100000 do    for j in 2 .. i do        if i <> j && i % j = 0 then            isPrime <- false    if isPrime then        printfn "%i" i    isPrime <- truestopwatch.Stop()printfn "Elapsed time: %ims" stopwatch.ElapsedMillisecondsConsole.ReadKey() |> ignoreC#（16239 毫秒）using System;using System.Diagnostics;namespace ConsoleApp1{    class Program    {        static void Main(string[] args)        {            Stopwatch stopwatch = new Stopwatch();            stopwatch.Start();            bool isPrime = true;            for (int i = 2; i <= 100000; i++)            {                for (int j = 2; j <= i; j++)                {                    if (i != j && i % j == 0)                    {                        isPrime = false;                        break;                    }                }                if (isPrime)                {                    Console.WriteLine(i);                }                isPrime = true;            }            stopwatch.Stop();            Console.WriteLine("Elapsed time: " + stopwatch.ElapsedMilliseconds + "ms");            Console.ReadKey();        }    }}

Answer 1

F# 程序较慢，因为您的程序不等效。您的 C# 代码break在内for循环中有一条语句，但您的 F# 程序没有。因此，对于每个偶数，C# 代码将在检查可被 2 整除后停止，而 F# 程序将检查从 2 到i. 由于完成的工作有如此大的差异，F# 代码仅慢了三倍实际上令人惊讶！

现在，F# 故意没有break语句，因此您不能完全将 C# 代码直接转换为 F#。但是您可以使用包含短路逻辑的函数。例如：

{2 .. 100000}

|> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))

|> Seq.iter (printfn "%i")

这使用Seq.forall，它确实做了短路：它将根据条件检查序列中的每个输入，如果条件返回false，它将停止并且不再进行检查。（因为Seq模块中的函数是惰性的，并且不会做比获得输出绝对需要的更多的工作）。这就像break在你的 C# 代码中有一个。

我将逐步完成此操作，以便您了解它是如何工作的：

{2 .. 100000}

这将创建一个惰性整数序列，从 2 开始并上升到（并包括）100000。

|> Seq.filter (fun i -> (some expression involving i))

我将下一行分为两部分：外部Seq.filter部分和涉及i. 该Seq.filter部分获取序列并对其进行过滤：对于序列中的每个项目，调用它i并评估表达式。如果该表达式的计算结果为true，则保留该项目并将其传递到链中的下一步。如果表达式为false，则丢弃该项目。

现在，涉及的表达式i是：

{2 .. i-1} |> Seq.forall (fun j -> i % j <> 0)

这首先构造了一个从 2 开始一直到i负 1的惰性序列。（或者您可以将其视为从 2 开始并上升到i，但不包括i）。然后检查该序列的每个项目是否满足特定条件（即Seq.forall函数）。并且，作为 的实现细节Seq.forall，因为它是懒惰的并且不做绝对必要的工作，所以它在找到false结果的那一刻将停止并且不再通过输入序列。（因为一旦你找到一个反例，forall函数就不可能再返回真了，所以一旦知道结果，它就会停止。）被检入的表达式是Seq.forall什么？它是fun j -> i % j <> 0。所以j是内部循环变量，i是外部变量（在Seq.filter部分中分配的变量），逻辑与您的C#循环相同。

现在，请记住我们是在一个Seq.filter这里。因此，如果Seq.forall返回 true，Seq.filter则将保留 的值i。但是如果Seq.forall返回false，Seq.filter则将丢弃这个值i从传递到下一步。

最后，我们将这一行作为下一步（也是最后一步）：

|> Seq.iter (printfn "%i")

这与以下内容几乎完全相同：

for number in inputSoFar do

    printfn "%i" number

(printfn "%i")如果您不熟悉 F#，该调用可能看起来不寻常。这是currying，这是一个非常有用的概念，而且很重要的是要习惯它。所以花点时间思考一下：在 F# 中，以下两行代码是完全等价的：

(fun y -> someFunctionCall x y)

(someFunctionCall x)

所以fun item -> printfn "%i" item总是可以替换为printfn "%i. 并且Seq.iter相当于一个for循环：

inputSoFar |> Seq.iter (someFunctionCall x)

完全等同于：

for item in inputSoFar do

    someFunctionCall x item

所以你知道了：为什么你的 F# 程序更慢，以及如何编写一个 F# 程序，该程序将遵循与 C# 相同的逻辑，但在其中包含等效的break语句。

Answer 2

这些年来做了很多 C#，但 F# 并不多。以下将更等效于 C# 代码。

open System

open System.Diagnostics

let stopwatch = new Stopwatch()

stopwatch.Start()

let mutable loop = true

for i in 2 .. 100000 do

    let mutable j = 2

    while loop do

        if i <> j && i % j = 0 then

            loop <- false

        else

            j <- j + 1

            if j >= i then

                printfn "%i" i

                loop <- false

    loop <- true

stopwatch.Stop()

printfn "Elapsed time: %ims" stopwatch.ElapsedMilliseconds

它还得出了惊人的相似 IL。

Answer 3

正如其他人提到的，代码没有做同样的事情，您需要采用技术来确保在找到素数后停止内部循环。

此外，您正在将值打印为标准输出。当您进行 CPU 性能测试时，这通常是不希望的，因为大量时间可能是 I/O 歪曲测试结果。

无论如何，即使有一个公认的答案，我还是决定对此进行一些修补，以查看将不同的建议解决方案与我自己的一些解决方案进行比较。

性能运行x64在 .NET 4.7.1 模式下。

我比较了不同的建议 F# 解决方案以及我自己的一些变体：

Running 'Original(F#)' with 100000 (10512)...

  ... it took 14533 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Original(C#)' with 100000 (10512)...

  ... it took 1343 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Aaron' with 100000 (10512)...

  ... it took 5027 ms with (3, 1, 0) cc and produces 9592 GOOD primes

Running 'SteveJ' with 100000 (10512)...

  ... it took 1640 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Dumetrulo1' with 100000 (10512)...

  ... it took 1908 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Dumetrulo2' with 100000 (10512)...

  ... it took 970 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Simple' with 100000 (10512)...

  ... it took 621 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'PushStream' with 100000 (10512)...

  ... it took 1627 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Unstalling' with 100000 (10512)...

  ... it took 551 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'Vectors' with 100000 (10512)...

  ... it took 1076 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'VectorsUnstalling' with 100000 (10512)...

  ... it took 1072 ms with (0, 0, 0) cc and produces 9592 GOOD primes

Running 'BestAttempt' with 100000 (10512)...

  ... it took 4 ms with (0, 0, 0) cc and produces 9592 GOOD primes  

1. Original(F#) - OP 的原始 F# 代码改为不使用 stdout

2. Original(C#) - OP 的原始 C# 代码改为不使用 stdout

3. Aaron- 使用的惯用方法Seq。正如预期的那样Seq，性能通常不会很好地结合在一起。

4. SteveJ - @SteveJ 试图在 F# 中模仿 C# 代码

5. Dumetrulo1 - @dumetrulo 在尾递归中实现了算法

6. Dumetrulo2 - @dumetrulo 通过步进 +2 而不是 +1 来改进算法（不需要检查偶数）。

7. Simple- 我尝试使用Dumetrulo2与尾递归类似的方法。

8. PushStream- 我尝试使用简单的推流（Seq是拉流）

9. Unstalling - 如果使用的指令有延迟，我尝试尝试使 CPU 停止运行

10. Vectors- 我尝试使用System.Numerics.Vectors每个操作（又名 SIMD）进行多个除法。不幸的是，vector libary 不支持，mod所以我不得不模仿它。

11. VectorsUnstalling- 我试图Vectors通过尝试停止 CPU来改进。

12. BestAttempt- 喜欢Simple但只sqrt n在确定是否为素数时检查数字。

包起来

1. F# 循环没有也continue没有break. F# 中的尾递归是 IMO 实现需要break.

2. 在比较语言的性能时，应该比较最佳性能还是比较惯用解决方案的性能？我个人认为最好的性能是正确的方法，但我知道人们不同意我的意见（我写了一个mandelbrot 版本来对 F#的游戏进行基准测试，其性能与 C 相当，但它没有被接受，因为这种风格被视为非-F# 的惯用语）。

3. Seq不幸的是，在 F# 中会增加大量开销。即使开销不相关，我也很难让自己使用它。

4. 现代 CPU 指令具有不同的吞吐量和延迟数量。这意味着有时为了提高性能，需要在内循环中处理多个独立样本，以允许乱序执行单元重新排序程序以隐藏延迟。如果您的 CPU 具有超线程并且您在多个线程上运行算法，则超线程可以“自动”减轻延迟。

5. mod向量的缺乏阻止了使用 SIMD 来获得优于非 SIMD 解决方案的任何性能的尝试。

6. 如果我修改Unstalling尝试以与 C# 代码相同的次数循环，则最终结果1100 ms在 F# 中与1343 ms在 C# 中相比。因此，F# 可以与 C# 非常相似地运行。如果应用更多的技巧，它只需要，4 ms但对于 C# 也是一样的。无论如何，从几乎15 sec到4 ms.

希望它对某人很有趣

完整源代码：

module Common = 

  open System

  open System.Diagnostics

  let now =

    let sw = Stopwatch ()

    sw.Start ()

    fun () -> sw.ElapsedMilliseconds

  let time i a =

    let inline cc i       = GC.CollectionCount i

    let ii = i ()

    GC.Collect (2, GCCollectionMode.Forced, true)

    let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2

    let b                 = now ()

    let v = a ii

    let e = now ()

    let ecc0, ecc1, ecc2  = cc 0, cc 1, cc 2

    v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2

  let limit    = 100000

  // pi(x) ~= limit/(ln limit - 1)

  // Using pi(x) ~= limit/(ln limit - 2) to over-estimate

  let estimate = float limit / (log (float limit) - 1.0 - 1.0) |> round |> int

module Original =

  let primes limit =

    let ra = ResizeArray Common.estimate

    let mutable isPrime = true

    for i in 2 .. limit do

      for j in 2 .. i do

        if i <> j && i % j = 0 then

          isPrime <- false

      if isPrime then

          ra.Add i

      isPrime <- true

    ra.ToArray ()

module SolutionAaron =

  let primes limit =

    {2 .. limit}

    |> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))

    |> Seq.toArray

module SolutionSteveJ =

  let primes limit =

    let ra = ResizeArray Common.estimate

    let mutable loop = true

    for i in 2 .. limit do

        let mutable j = 2

        while loop do

            if i <> j && i % j = 0 then

                loop <- false

            else

                j <- j + 1

                if j >= i then

                    ra.Add i

                    loop <- false

        loop <- true

    ra.ToArray ()

module SolutionDumetrulo1 =

  let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =

    if i > limit then ra.ToArray ()

    elif j > i then

      ra.Add i

      isPrimeLoop ra (i + 1) 2 limit

    elif i <> j && i % j = 0 then

      isPrimeLoop ra (i + 1) 2 limit

    else

      isPrimeLoop ra i (j + 1) limit

  let primes limit =

    isPrimeLoop (ResizeArray Common.estimate) 2 2 limit

module SolutionDumetrulo2 =

  let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =

    let incr x = if x = 2 then 3 else x + 2

    if i > limit then ra.ToArray ()

    elif j > i then

      ra.Add i

      isPrimeLoop ra (incr i) 2 limit

    elif i <> j && i % j = 0 then

      isPrimeLoop ra (incr i) 2 limit

    else

      isPrimeLoop ra i (incr j) limit

  let primes limit =

    isPrimeLoop (ResizeArray Common.estimate) 2 2 limit

module SolutionSimple =

  let rec isPrime i j k =

    if i < k then

      (j % i) <> 0 && isPrime (i + 2) j k

    else

      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =

    if i < limit then 

      if isPrime 3 i i then

        ra.Add i

      isPrimeLoop ra (i + 2) limit

    else

      ra.ToArray ()

  let primes limit =

    let ra = ResizeArray Common.estimate

    ra.Add 2

    isPrimeLoop ra 3 limit

module SolutionPushStream =

  type Receiver<'T> = 'T -> bool

  type PushStream<'T> = Receiver<'T> -> bool

  module Details =

    module Loops =

      let rec range e r i =

        if i <= e then

          if r i then

            range e r (i + 1)

          else

            false

        else

          true

  open Details

  let range s e : PushStream<int> =

    fun r -> Loops.range e r s

  let filter p (t : PushStream<'T>) : PushStream<'T> =

    fun r -> t (fun v -> if p v then r v else true)

  let forall p (t : PushStream<'T>) : bool =

    t p

  let toArray (t : PushStream<'T>) : _ [] =

    let ra = ResizeArray 16

    t (fun v -> ra.Add v; true) |> ignore

    ra.ToArray ()

  let primes limit =

    range 2 limit

    |> filter (fun i -> range 2 (i - 1) |> forall (fun j -> i % j <> 0))

    |> toArray

module SolutionUnstalling =

  let rec isPrime i j k =

    if i + 6 < k then

      (j % i) <> 0 && (j % (i + 2)) <> 0 && (j % (i + 4)) <> 0 && (j % (i + 6)) <> 0  && isPrime (i + 8) j k

    else

      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =

    if i < limit then 

      if isPrime 3 i i then

        ra.Add i

      isPrimeLoop ra (i + 2) limit

    else

      ra.ToArray ()

  let primes limit =

    let ra = ResizeArray Common.estimate

    ra.Add 2

    ra.Add 3

    ra.Add 5

    ra.Add 7

    ra.Add 11

    ra.Add 13

    ra.Add 17

    ra.Add 19

    ra.Add 23

    isPrimeLoop ra 29 limit

module SolutionVectors =

  open System.Numerics

  assert (Vector<int>.Count = 4)

  type I4 = Vector<int>

  let inline (%%) (i : I4) (j : I4) : I4 =

    i - (j * (i / j))

  let init : int [] = Array.zeroCreate 4

  let i4 v0 v1 v2 v3 =

    init.[0] <- v0

    init.[1] <- v1

    init.[2] <- v2

    init.[3] <- v3

    I4 init

  let i4_ (v0 : int) =

    I4 v0

  let zero    = I4.Zero

  let one     = I4.One 

  let two     = one + one

  let eight   = two*two*two

  let step = i4 3 5 7 9

  let rec isPrime (i : I4) (j : I4) k l =

    if l + 6 < k then

      Vector.EqualsAny (j %% i, zero) |> not && isPrime (i + eight) j k (l + 8)

    else

      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =

    if i < limit then 

      if isPrime step (i4_ i) i 3 then

        ra.Add i

      isPrimeLoop ra (i + 2) limit

    else

      ra.ToArray ()

  let primes limit =

    let ra = ResizeArray Common.estimate

    ra.Add 2

    ra.Add 3

    ra.Add 5

    ra.Add 7

    ra.Add 11

    ra.Add 13

    ra.Add 17

    ra.Add 19

    ra.Add 23

    isPrimeLoop ra 29 limit

module SolutionVectorsUnstalling =

  open System.Numerics

  assert (Vector<int>.Count = 4)

  type I4 = Vector<int>

  let init : int [] = Array.zeroCreate 4

  let i4 v0 v1 v2 v3 =

    init.[0] <- v0

    init.[1] <- v1

    init.[2] <- v2

    init.[3] <- v3

    I4 init

  let i4_ (v0 : int) =

    I4 v0

  let zero    = I4.Zero

  let one     = I4.One 

  let two     = one + one

  let eight   = two*two*two

  let sixteen = two*eight

  let step = i4 3 5 7 9

  let rec isPrime (i : I4) (j : I4) k l =

    if l + 14 < k then

      // i - (j * (i / j))      

      let i0 = i

      let i8 = i + eight

      let d0 = j / i0

      let d8 = j / i8

      let n0 = i0 * d0

      let n8 = i8 * d8

      let r0 = j - n0

      let r8 = j - n8

      Vector.EqualsAny (r0, zero) |> not && Vector.EqualsAny (r8, zero) |> not && isPrime (i + sixteen) j k (l + 16)

    else

      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =

    if i < limit then 

      if isPrime step (i4_ i) i 3 then

        ra.Add i

      isPrimeLoop ra (i + 2) limit

    else

      ra.ToArray ()

  let primes limit =

    let ra = ResizeArray Common.estimate

    ra.Add 2

    ra.Add 3

    ra.Add 5

    ra.Add 7

    ra.Add 11

    ra.Add 13

    ra.Add 17

    ra.Add 19

    ra.Add 23

    isPrimeLoop ra 29 limit

module SolutionBestAttempt =

  let rec isPrime i j k =

    if i < k then

      (j % i) <> 0 && isPrime (i + 2) j k

    else

      true

  let inline isqrt i = (i |> float |> sqrt) + 1. |> int

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =

    if i < limit then 

      if isPrime 3 i (isqrt i) then

        ra.Add i

      isPrimeLoop ra (i + 2) limit

    else

      ra.ToArray ()

  let primes limit =

    let ra = ResizeArray Common.estimate

    ra.Add 2

    isPrimeLoop ra 3 limit

[<EntryPoint>]

let main argv =

  let testCases =

    [|

      "Original"    , Original.primes

      "Aaron"       , SolutionAaron.primes

      "SteveJ"      , SolutionSteveJ.primes

      "Dumetrulo1"  , SolutionDumetrulo1.primes

      "Dumetrulo2"  , SolutionDumetrulo2.primes

      "Simple"            , SolutionSimple.primes

      "PushStream"        , SolutionPushStream.primes

      "Unstalling"        , SolutionUnstalling.primes

      "Vectors"           , SolutionVectors.primes

      "VectorsUnstalling" , SolutionVectors.primes

      "BestAttempt"       , SolutionBestAttempt.primes

    |]

  do

    // Warm-up

    printfn "Warm up"

    for _, a in testCases do

      for i = 0 to 100 do

        a 100 |> ignore

  do

    let init ()   = Common.limit

    let expected  = SolutionSimple.primes Common.limit

    for testCase, a in testCases do

      printfn "Running '%s' with %d (%d)..." testCase Common.limit Common.estimate

      let actual, time, cc0, cc1, cc2 = Common.time init a

      let result = if expected = actual then "GOOD" else "BAD"

      printfn "  ... it took %d ms with (%d, %d, %d) cc and produces %d %s primes" time cc0 cc1 cc2 actual.Length result 

  0