logo标签列表

.NET函数调用的性能（C# F#）与C++的比较

c#.netc++f#stopwatch
9
自从F# 2.0成为VS2010的一部分后，我对F#产生了兴趣。我想知道使用它的意义是什么。我稍微读了一些资料，并制作了一个基准来测量函数调用。 我使用了Ackermann函数：) C#
sealed class Program
{
    public static int ackermann(int m, int n)
    {
        if (m == 0)
            return n + 1;
        if (m > 0 && n == 0)
        {
            return ackermann(m - 1, 1);
        }
        if (m > 0 && n > 0)
        {
            return ackermann(m - 1, ackermann(m, n - 1));
        }
        return 0;
    }

    static void Main(string[] args)
    {

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();
        Console.WriteLine("C# ackermann(3,10) = " + Program.ackermann(3, 10));
        stopWatch.Stop();

        Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");
        Console.ReadLine();
    }
}

C++

class Program{
public:
static inline int ackermann(int m, int n)
{
  if(m == 0)
       return n + 1;
  if (m > 0 && n == 0)
  {
      return ackermann(m - 1, 1);
  }
  if (m > 0 && n > 0)
  {
      return ackermann(m - 1, ackermann(m, n - 1));
  }
  return 0;
 }
};

int _tmain(int argc, _TCHAR* argv[])
{
 clock_t start, end;

  start = clock();
 std::cout << "CPP: ackermann(3,10) = " << Program::ackermann(3, 10) << std::endl;
 end = clock();
 std::cout << "Time required for execution: " << (end-start) << " ms." << "\n\n";
 int i;
 std::cin >> i;
 return 0;
}

F#

// Ackermann
let rec ackermann m n  =
  if m = 0 then n + 1
  elif m > 0 && n = 0 then ackermann (m - 1) 1
  elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
  else 0

open System.Diagnostics;
let stopWatch = Stopwatch.StartNew()
let x = ackermann 3 10 
stopWatch.Stop();

printfn "F# ackermann(3,10) = %d"  x
printfn "Time required for execution: %f"  stopWatch.Elapsed.TotalMilliseconds

Java

public class Main 
{
 public static int ackermann(int m, int n)
 {
 if (m==0) 
   return n + 1;
if (m>0 && n==0)
{
 return ackermann(m - 1,1);
}
if (m>0 && n>0)
{
  return ackermann(m - 1,ackermann(m,n - 1));
 }
 return 0;
}

  public static void main(String[] args)
  { 
   System.out.println(Main.ackermann(3,10));
  }
}

然后
C# = 510毫秒
c++ = 130毫秒
F# = 185毫秒
Java = Stackoverflow :)

除了一小部分代码，这是 F# 的威力吗？如果想使用 .Net 并获得更快的执行速度，我能优化其中任何代码吗（尤其是 F#）?

更新。我去掉了 Console.WriteLine 并在没有调试器的情况下运行了 C# 代码: C# = 400ms

9
在运行基准测试之前，请先执行一次您的方法。您所测量的时间包括 JIT 中间语言所需的时间。此外，请将像 Console.WriteLine() 这样的方法从基准测试中移出，因为它们非常慢。 - Mark H
1
在运行基准测试之前，请先执行您的方法。您的时间已经包括了 JIT 中间语言所花费的时间。我添加了 let dd = ackermann 3 10，额外增加了 7 毫秒。对于 C# 没有改变 :)此外，将像 Console.WriteLine() 这样的方法从基准测试中排除，因为它们非常慢是个好主意。但这并没有提高速度。 - Lukasz Madon
是的，F#和C#都是JIT编译的 - 运行方法两次并使用第二个基准测试。原因是JIT编译器会针对处理器的特定能力（CISC计算好处）优化机器代码。 - Aaronontheweb
为什么不在基准测试中包括第一次执行？我们真的可以忽略JIT吗？这不是作弊吗？ - Inverse
1
不完全是这样。您可以预编译应用程序，如果应用程序运行了一个小时 - 第一个方法调用根本就不相关。 - TomTom
1 - 必须放弃这些打印输出 - 这不是库编写者智商缺陷的测试(Console.WriteLine 在 PowerShell 中只打印常量非常痛苦 - 有人需要因此被起诉 :-)2 - 必须跳过前2-5次运行或包括编译C++所需的时间(第一次运行用于JIT，其余用于让GC平静下来 - 所以好吧，C++无论如何都赢了 :-)3 - Ackerman作为一个堆栈破坏测试而闻名，那么像矩阵求逆这样现实的东西怎么样呢 :-)4 - 请有人修复那个Java - 这太尴尬了 :-))) - ZXX
4个回答
14

我认为在这种情况下，C#和F#之间的区别要归功于尾调用优化。

尾调用是指在函数中进行递归调用时作为“最后一件事”完成的调用。在这种情况下，F#实际上不会生成调用指令，而是将代码编译成循环（因为调用是“最后一件事”，我们可以重用当前的堆栈帧并跳转到方法的开始位置）。

在你的ackermann实现中，有两个是尾调用，只有一个不是（其中一个将结果作为参数传递给另一个ackermann调用）。这意味着F#版本实际上执行“调用”指令的次数要比C#版本少得多。

总的来说，性能大致相同，与C#的性能相当。这里有很多与F# vs. C#性能相关的帖子：

2
我一直在用C#手写递归下降解析器，但经常因为缺少尾调用优化而后悔没有使用F#。 - ChaosPandion
7
你正在用C#编写解析器，而你唯一后悔没有使用F#的原因是它可能无法优化尾调用？真的吗？这是唯一的原因吗？ - Gabe
@lukas：VC++编译器（因此优化器）比C#编译器成熟得多。即使在CLR上运行的C++/CLI代码通常也比等效的C#代码表现更好。实际上，F#性能与本机C++非常接近的事实证明了CLR代码的潜在性能。 - Cogwheel
@Gabe - 嗯，我也很后悔。公平地说，我并没有说那是我唯一的遗憾。 - ChaosPandion
2
实际上，一些C++编译器进行了尾递归优化，其中包括Visual C++。 - wmeyer
显示剩余3条评论
6

这与函数调用有关，因为这是一种减少函数调用的常见方法。

通过记忆化（缓存），您可以使此类型的递归函数更快。在C＃中也可以这样做（示例）。我得到了18ms。

open System.Collections.Generic

let memoize2 f =
    let cache = Dictionary<_, _>()
    fun x y ->
        if cache.ContainsKey (x, y) then 
            cache.[(x, y)]
        else 
            let res = f x y
            cache.[(x, y)] <- res
            res

// Ackermann
let rec ackermann =
    memoize2 (fun m n ->
        if m = 0 then n + 1
        elif m > 0 && n = 0 then ackermann (m - 1) 1
        elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
        else 0
    )
4

虽然与问题没有直接关联，但足够有趣，值得一试：尝试这个版本

let rec ackermann2 m n  =
  match m,n with
  | 0,0 -> 0
  | 0,n -> n+1
  | m,0 -> ackermann2 (m-1) 1
  | m,n -> ackermann2 (m-1) (ackermann2 m (n-1))

在我的电脑上（使用VS2010和F#交互界面），当计算Ackermann 3 12时，它比您的版本快了近50%。

我无法完全解释为什么会有这样的性能差异。我猜测这可能与F#编译器将匹配表达式转换为switch语句而不是一系列if语句有关。将（m=0，n=0）测试放在第一位也可能有所帮助。

1
模式匹配编译器应该重新构造测试以最小化冗余，而原始代码对m>0测试进行了两次。 - J D
1

对于 F#，您可能想尝试使用 inline 关键字。

此外，正如之前的帖子所提到的，由于 Console.WriteLine 语句的不同，C# 和 F# 版本有所区别。

2
函数不能同时是内联和递归的。 - Lukasz Madon
3
如何将一个递归函数内联化？ - Gabe
解除递归绑定，使用“inline”进行展开。 - J D
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接