FSharp运行我的算法比Python慢

Question

几年前，我通过动态编程解决了一个问题：

https://www.thanassis.space/fillupDVD.html

解决方案是用Python编写的。

作为拓展视野的一部分，我最近开始学习OCaml/F。有什么比直接将我用Python编写的命令代码移植到F#来测试waters更好的方法呢？从这里开始，逐步走向函数式编程解决方案。

第一个结果，直接端口。。。令人不安：

在Python下：

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

根据FSharp：

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

（如果你注意到上面的“mono”：我也在Windows下进行了测试，使用Visual Studio-同样的速度）。

我是。。。至少可以说是困惑。Python运行代码的速度比F#快？使用.NET运行时编译的二进制文件比Python的解释代码运行得慢？！？！

我知道VMs（本例中是mono）的启动成本，以及jit如何改进Python之类的语言，但仍然。。。我期待的是加速，而不是减速！

我可能做错什么了吗？

我已经在这里上传了代码：

https://www.thanassis.space/fsharp.slower.than.python.tar.gz

注意，F#代码或多或少是Python代码的直接逐行翻译。

当然还有其他好处，例如F#提供的静态类型安全性——但是如果命令式算法的结果速度在F#下更差。。。至少可以说，我很失望。

编辑：根据评论中的要求直接访问：

Python代码：https://gist.github.com/950697

FSharp代码：https://gist.github.com/950699

Answer 1

我通过电子邮件联系了乔恩·哈罗普医生，他解释了发生的事情：

The problem is simply that the program has been optimized for Python. This is common when the programmer is more familiar with one language than the other, of course. You just have to learn a different set of rules that dictate how F# programs should be optimized... Several things jumped out at me such as the use of a "for i in 1..n do" loop rather than a "for i=1 to n do" loop (which is faster in general but not significant here), repeatedly doing List.mapi on a list to mimic an array index (which allocated intermediate lists unnecessarily) and your use of the F# TryGetValue for Dictionary which allocates unnecessarily (the .NET TryGetValue that accepts a ref is faster in general but not so much here)

... but the real killer problem turned out to be your use of a hash table to implement a dense 2D matrix. Using a hash table is ideal in Python because its hash table implementation has been extremely well optimized (as evidenced by the fact that your Python code is running as fast as F# compiled to native code!) but arrays are a much better way to represent dense matrices, particularly when you want a default value of zero.

有趣的是，当我第一次编码这个算法时，我确实使用了一个表——为了清晰起见，我将实现改为字典（避免数组边界检查使代码更简单，也更容易推理）。

Jon将我的代码（back:-）转换为它的array version，它以100倍的速度运行。

故事的寓意：

• 字典需要工作。。。当使用元组作为键时，编译的F#比解释的Python哈希表慢！
• 很明显，但重复并没有坏处：更干净的代码有时意味着。。。更慢的代码。

谢谢你，乔恩——非常感谢。

编辑：事实上，用数组替换字典使F最终以编译语言预期的运行速度运行，这并不意味着需要修正字典的速度（我希望来自MS的F#人正在阅读这个）。其他的算法依赖于字典/散列，并且不能很容易地切换到使用数组；使得程序在使用字典时遭受“解释器速度”的影响，可以说是一个bug。如果，正如一些人在评论中所说，问题不在于F，而在于.NET字典，那么我认为。。。是.NET中的一个bug！

EDIT2：最清晰的解决方案是，不需要算法切换到数组（有些算法根本不适合这样做）来更改：

let optimalResults = new Dictionary<_,_>()

进入这个：

let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)

这一变化使F#代码的运行速度提高了2.7倍，从而最终击败了Python（提高了1.6倍）。奇怪的是元组默认情况下使用结构比较，因此原则上，字典对键进行的比较是相同的（有或没有结构）。Harrop博士认为，速度差可能是由于虚拟调度造成的：“AFAIK，.NET对优化虚拟调度几乎没有作用，而且在现代硬件上，虚拟调度的成本极高，因为它是一个“计算的goto”，将程序计数器跳到一个不可预测的位置，因此，破坏分支预测逻辑，几乎肯定会导致整个CPU管道被刷新和重新加载“。

简单地说，正如Don Syme（look at the bottom 3 answers）所建议的，“在将引用类型的键与.NET集合结合使用时，要明确使用结构哈希”。（Harrop博士在下面的评论中还说，在使用.NET集合时，我们应该始终使用结构比较）。

亲爱的微软团队，如果有办法自动解决这个问题，请这样做。

Answer 2

正如Jon Harrop所指出的，简单地使用Dictionary(HashIdentity.Structural)构造字典可以显著提高性能（在我的计算机上是3倍）。这几乎可以肯定是为了获得比Python更好的性能而需要进行的微创更改，并使代码保持习惯性（而不是用结构等替换元组），并与Python实现并行。

Answer 3

编辑：我错了，这不是值类型对引用类型的问题。性能问题与散列函数有关，如其他注释中所述。我把答案留在这里是因为有一个有趣的讨论。我的代码部分修复了性能问题，但这不是一个干净和推荐的解决方案。

--

在我的计算机上，我用一个结构替换元组，使您的示例运行速度比运行速度快两倍。这意味着，等价的F#代码应该比Python代码运行得更快。我不同意那些说.NET哈希表速度慢的评论，我相信与Python或其他语言实现没有显著的区别。另外，我不同意“你不能期望1对1的转换代码更快”：对于大多数任务，F代码通常比Python快（静态类型对编译器非常有帮助）。在您的示例中，大部分时间都花在了哈希表查找上，因此可以公平地想象，两种语言都应该几乎一样快。

我认为性能问题与gabage集合有关（但我没有使用探查器进行检查）。这里使用元组比结构慢的原因已经在SO问题（Why is the new Tuple type in .Net 4.0 a reference type (class) and not a value type (struct)）和MSDN页面（Building tuples）中讨论过了：

If they are reference types, this means there can be lots of garbage generated if you are changing elements in a tuple in a tight loop. [...] F# tuples were reference types, but there was a feeling from the team that they could realize a performance improvement if two, and perhaps three, element tuples were value types instead. Some teams that had created internal tuples had used value instead of reference types, because their scenarios were very sensitive to creating lots of managed objects.

当然，正如Jon在另一条评论中所说，示例中明显的优化是用数组替换哈希表。数组显然要快得多（整数索引、无散列、无冲突处理、无重新分配、更紧凑），但这是针对您的问题的，它不能解释与Python的性能差异（据我所知，Python代码使用的是散列表，而不是数组）。

为了重现我50%的加速，这里是完整的代码：http://pastebin.com/nbYrEi5d

简而言之，我用这种类型替换了元组：

type Tup = {x: int; y: int}

而且，它看起来像一个细节，但是您应该将List.mapi (fun i x -> (i,x)) fileSizes移出封闭循环。我相信Pythonenumerate实际上并不分配列表（因此在F#中只分配一次列表，或者使用Seq模块，或者使用可变计数器是公平的）。