c# - 为什么 LINQ (c#) 与 Seq (f#) 之间存在性能差异

Question

我制作了非常简单的 C# 和 F# 测试程序。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static int Remainder(int num)
        {
            return num % 2;
        }
        static int SumOfremainders(IEnumerable<int> list)
        {
            var sum = 0;
            foreach (var num in list)
            {
                sum += Remainder(num);
            }
            return sum;
        }

        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            var nums = Enumerable.Range(1, 10000000);
            sw.Start();
            var a = SumOfremainders(nums);
            sw.Stop();
            Console.WriteLine("Duration " + (sw.ElapsedMilliseconds));
            Console.WriteLine("Sum of remainders: {0}", a);
        }
    }
}


let remainder x = x % 2   

let sumORemainders n = 
   n
   |> Seq.map(fun n-> remainder n)
   |> Seq.sum

let seqb = Seq.init 10000000(fun n->n)
let timer =System.Diagnostics.Stopwatch()
timer.Start()
let a =(sumORemainders seqb )
timer.Stop()
printfn "Elapsed Time: "
System.Console.WriteLine timer.ElapsedMilliseconds
printfn "Sum of squares of 1-100: %d"  a


[<EntryPoint>]
let main argv = 

    0 // return an integer exit code

c# 71 毫秒f# 1797 毫秒

我用 F# 制作了第二个版本，它的工作方式与 c# 类似

let remainder x = x % 2   

let sumORemainders (input:seq<int>)  =
    let mutable sum = 0
    let en = input.GetEnumerator()
    while (en.MoveNext()) do 
        sum <- sum + remainder en.Current 
    sum


let seqb = Seq.init 10000000(fun n->n)
let timer =System.Diagnostics.Stopwatch()
timer.Start()
let a =(sumORemainders seqb )
timer.Stop()
printfn "Elapsed Time: "
System.Console.WriteLine timer.ElapsedMilliseconds
printfn "Sum of squares of 1-100: %d"  a


[<EntryPoint>]
let main argv = 

    0 // return an integer exit code

但结果并没有显着改变(1650ms)

我不明白这两种语言在速度上的巨大差异。

这两个程序的IL代码非常相似，都使用IEnumerable，而且F#用操作代替了函数调用。

我基于 f# IL 代码重写了 c# 代码。

static int SumOfremainders(IEnumerable<int> list)
        {
            var sum = 0;
            IEnumerator<int> e = list.GetEnumerator();
            while (e.MoveNext())
            {
                sum += e.Current % 2;
            }
            return sum;
        }

两个程序的IL代码是一样的，但是速度还是有很大的不同。感谢 Foggy Finder，我发现了 IL 差异

慢代码

[CompilationMapping(SourceConstructFlags.Module)]
public static class Program
{
    [Serializable]
    internal class seqb@18 : FSharpFunc<int, int>
    {
        internal seqb@18()
        {
        }

        public override int Invoke(int n)
        {
            return n;
        }
    }

    [CompilationMapping(SourceConstructFlags.Value)]
    public static IEnumerable<int> seqb
    {
        get
        {
            return $Program.seqb@18;
        }
    }

快速代码

[CompilationMapping(SourceConstructFlags.Module)]
public static class Program
{
    [CompilationMapping(SourceConstructFlags.Value)]
        public static int[] seqb
        {
            get
            {
                return $Program.seqb@20;
            }
        }

Answer 1

OP 看到性能差异的主要原因是因为 Seq.init在 F# 中很慢。原因是在每次迭代中 Seq.upto (Seq.init 使用)分配一个新的 Lazy<_>目的。你可以在 Seq 中看到这个source .如果你有像 fun n -> n % 2 这样的低开销函数新的成本Lazy<_>对象以及评估它(互斥锁和解锁)需要大量时间。

OP 看到性能差异的第二个原因是 Seq在 F# 中通常很慢。此 PR 中的 manofstick 正在对此进行补救

使用 PR 就位 F# Seq与现有的替代方案相比将表现得非常好(一些细节 here )

综上所述，我准备了一些不同方法的比较来进行用户发布的计算(除了明显的 total / 2 )。

open CsPerfs
open Nessos.Streams
open System.Diagnostics
open System.Linq
open System.Numerics


// now () returns current time in milliseconds since start
let now : unit -> int64 =
  let sw = Stopwatch ()
  sw.Start ()
  fun () -> sw.ElapsedMilliseconds

// time estimates the time 'action' repeated a number of times
let time repeat action =
  let inline cc i       = System.GC.CollectionCount i

  let v                 = action ()

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

  let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2
  let b                 = now ()

  for i in 1..repeat do
    action () |> ignore

  let e = now ()
  let ecc0, ecc1, ecc2  = cc 0, cc 1, cc 2

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

[<EntryPoint>]
let main argv = 
  let count = 10000000

  let outers = 
    [|
      1000
    |]

  for outer in outers do
    let inner = count / outer

    let fsImperativeTest () = 
      let mutable sum = 0
      for n = 0 to inner-1 do
        sum <- sum + n % 2
      sum

    let fsLinqTest () = 
      Enumerable.Range(0, inner).Select(fun n -> n % 2).Sum()
    let fsNessosTest () = 
      Stream.initInfinite id
      |> Stream.take inner
      |> Stream.map (fun n -> n % 2)
      |> Stream.sum
    let fsOpTest () = 
      let remainder x = x % 2   
      let sumORemainders (input:seq<int>)  =
          let mutable sum = 0
          use en = input.GetEnumerator()
          while (en.MoveNext()) do 
              sum <- sum + remainder en.Current 
          sum
      let seqb = Seq.init inner id
      sumORemainders seqb
    let fsSseTest () = 
      let inc         = Vector<int>.One
      let one         = Vector<int>.One
      let mutable sum = Vector<int>.Zero
      let mutable n   = Vector<int> [|0..3|]
      for n4 = 0 to inner/4-1 do
        n <- n + inc
        sum <- sum + (n &&& one)
      sum.[0] + sum.[1] + sum.[2] + sum.[3]
    let fsSeqTest () = 
      Seq.init inner id 
        |> Seq.map (fun n -> n % 2)
        |> Seq.sum
    let fsSeqVariantTest () = 
      seq { for n = 0 to inner-1 do yield n }
        |> Seq.map (fun n -> n % 2)
        |> Seq.sum

    let csImperativeTest = 
      let f = Perfs.CsImperativeTest inner
      fun () -> f.Invoke ()
    let csLinqTest = 
      let f = Perfs.CsLinqTest inner
      fun () -> f.Invoke ()
    let csOpTest =
      let f = Perfs.CsOpTest inner
      fun () -> f.Invoke ()

    let tests =
      [|
        "fsImperativeTest"  , fsImperativeTest
        "fsLinqTest"        , fsLinqTest
        "fsNessosTest"      , fsNessosTest
        "fsOpTest"          , fsOpTest
        "fsSeqTest"         , fsSeqTest
        "fsSeqVariantTest"  , fsSeqVariantTest
        "fsSseTest"         , fsSseTest
        "csImperativeTest"  , csImperativeTest
        "csLinqTest"        , csLinqTest
        "csOpTest"          , csOpTest
      |]

    printfn "Test run - total count: %d, outer: %d, inner: %d" count outer inner

    for name, test in tests do
      printfn "Running %s..." name
      let v, ms, cc0, cc1, cc2 = time outer test
      printfn "  it took %d ms - collection count is %d,%d,%d - result is %A" ms cc0 cc1 cc2 v 


  0

匹配的C#代码:

namespace CsPerfs
{
  using System;
  using System.Collections.Generic;
  using System.Linq;

    public static class Perfs
    {
      static int Remainder(int num)
      {
          return num % 2;
      }

      static int SumOfremainders(IEnumerable<int> list)
      {
          var sum = 0;
          foreach (var num in list)
          {
              sum += Remainder(num);
          }
          return sum;
      }

      public static Func<int> CsOpTest (int count)
      {
        return () => SumOfremainders (Enumerable.Range(1, count));
      }

      public static Func<int> CsImperativeTest (int count)
      {
        return () =>
          {
            var sum = 0;
            for (var n = 0; n < count; ++n)
            {
              sum += n % 2;
            }
            return sum;
          };
      }

      public static Func<int> CsLinqTest (int count)
      {
        return () => Enumerable.Range (0, count).Select (n => n % 2).Sum ();
      }
    }
}

在运行 .NET 4.6.1 64 位的我的机器 (Intel Core I5) 上看到的性能数据:

Test run - total count: 10000000, outer: 1000, inner: 10000
Running fsImperativeTest...
  it took 20 ms - collection count is 0,0,0 - result is 5000
Running fsLinqTest...
  it took 124 ms - collection count is 0,0,0 - result is 5000
Running fsNessosTest...
  it took 56 ms - collection count is 0,0,0 - result is 5000
Running fsOpTest...
  it took 1320 ms - collection count is 661,0,0 - result is 5000
Running fsSeqTest...
  it took 1477 ms - collection count is 661,0,0 - result is 5000
Running fsSeqVariantTest...
  it took 512 ms - collection count is 0,0,0 - result is 5000
Running fsSseTest...
  it took 2 ms - collection count is 0,0,0 - result is 5000
Running csImperativeTest...
  it took 19 ms - collection count is 0,0,0 - result is 5000
Running csLinqTest...
  it took 122 ms - collection count is 0,0,0 - result is 5000
Running csOpTest...
  it took 58 ms - collection count is 0,0,0 - result is 5000
Press any key to continue . . .

Seq做最坏的，也消耗内存。如果 F# 和 C# 代码都使用 LINQ，则没有预期的真正区别。 Nessos 是 F#(和 C#)的高性能数据管道，性能明显更好。

“硬编码”for 循环效果更好，最快的解决方案是通过 System.Numerics.Vectors 使用 SSE .遗憾System.Numerics.Vectors不支持 %这使得比较有点不公平。

所以区别与其说是语言问题，不如说是图书馆问题。