FSharp 运行我的算法比 Python 慢

Question

FSharp 运行我的算法比 Python 慢

pythonalgorithmperformancef#dynamic-programming

43

多年前，我通过动态规划解决了一个问题：

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

该解决方案是用Python编写的。

为了拓宽视野，最近我开始学习OCaml/F#。测试水温的最好方法莫过于将我以前用Python编写的命令式代码直接移植到F#中，并从此处开始，逐步朝着函数式编程解决方案迈进。

然而，这个第一次直接移植的结果有些令人不安：

在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的解释代码更慢？！

我知道虚拟机的启动成本（在这种情况下是mono）以及JIT如何改善像Python这样的语言的性能，但是...我预计会有加速而不是减速！

也许我做错了什么吗？

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

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

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

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

编辑：按要求直接访问：

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

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

- ttsiodras

7

请使用类似于 http://gist.github.com/ 的工具上传您的代码...这样做可以避免下载 tar.gz 文件才能查看您的代码，感觉很烦。 - razenha

7

这些都是神话，全部都是神话。并不是编译速度更快、解释速度更快、本地化速度更快或即时编译更快。唯一快的就是快。铭记于心。 - R. Martinho Fernandes

4

我没有Python来测试它，但是在我的Intel Core 2 Duo CPU（2.26 GHz）上，F#版本在大约1.5秒内完成（在Windows上使用fsi.exe和#time计时）。然而，我没有尝试理解你的代码-如果您发布一些要优化的简单F#代码（因为不是每个人都想分析您的两个示例），那么您更有可能得到有用的答案。 - Tomas Petricek

3

在我的电脑上，Python 运行需要 1.2 秒钟，而 F# 版本则需要 1.8 秒钟。这个基准测试可能显示的是，Python 有一个优秀的字典实现，也许对于键值为一对的情况进行了优化。 - wmeyer

1

@Martinho: “但是这段代码适合在F#中快速运行吗？” 是的。我的F#优化版比原来快100倍... - J D

显示剩余11条评论

4个回答

8

如Jon Harrop所指出的那样，仅使用Dictionary(HashIdentity.Structural)构建字典可以显著提高性能（在我的电脑上是3倍）。这几乎肯定是您需要进行的最小侵入性更改，以获得比Python更好的性能，并保持您的代码惯用（而不是将元组替换为结构等），与Python实现相平行。

- kvb

5

编辑：我错了，这不是值类型与引用类型的问题。性能问题与哈希函数有关，如其他评论中所解释的。我将我的答案保留在此处，因为有一个有趣的讨论。我的代码部分修复了性能问题，但这不是清洁且推荐的解决方案。

--

在我的计算机上，通过使用结构体代替元组，我使您的示例运行速度加快了两倍。这意味着，等效的F#代码应该比您的Python代码运行得更快。我不同意评论说.NET哈希表很慢，我认为与Python或其他语言实现没有显着差异。另外，我不同意“你不能一对一地翻译代码并期望它更快”的说法：对于大多数任务，F#代码通常比Python更快（静态类型对编译器非常有帮助）。在您的示例中，大部分时间都花费在做哈希表查找上，因此可以想象两种语言应该几乎一样快。

我认为性能问题与垃圾回收有关（但我还没有用分析器进行检查）。在SO问题（为什么.NET 4.0中的新元组类型是引用类型（类）而不是值类型（结构体））和MSDN页面（构建元组）中已经讨论了使用元组比结构体慢的原因：

如果它们是引用类型，这意味着如果您在紧密循环中更改元组中的元素，则可能会生成大量垃圾。[...] F#元组是引用类型，但该团队认为，如果两个或三个元素的元组代替引用类型，则可以实现性能提升。一些创建内部元组的团队已经使用值而不是引用类型，因为他们的情况非常敏感，需要创建大量托管对象。

当然，正如Jon在另一个评论中所说的那样，在您的示例中明显的优化是将哈希表替换为数组。数组显然更快（整数索引，无哈希处理，无冲突处理，无重新分配，更紧凑），但这对于您的问题非常特定，并且不能解释与Python的性能差异（据我所知，Python代码使用哈希表，而不是数组）。

要复制我的50%加速，请使用以下完整代码：http://pastebin.com/nbYrEi5d 简而言之，我用以下类型替换了元组：

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

此外，这似乎是一个细节，但你应该将 List.mapi (fun i x -> (i,x)) fileSizes 移出封闭循环。我相信 Python 的 enumerate 实际上没有分配列表（因此在 F# 中只需要分配一次列表，或使用 Seq 模块，或使用可变计数器即可）。

- Laurent

@ttsiodras: 我不这么认为。通过我的更改，代码比Python实现要快一些，这意味着在.NET中字典并不那么慢。当然，如果你知道索引，数组比哈希表快得多，但你正在改变算法。 - Laurent

@Jon：如果应该始终使用HashIdentity.Structural，那么为什么它不是Dictionary的默认值？我是F#的新手，所以有没有不使用Structural的原因？ - ttsiodras

1

@ttsiodras - 结构标识是一个 F# 的概念，其基础 .NET 框架完全不知道，因此 .NET 字典类型无法将其用作默认值。 - kvb

2

在当前版本的F#中，是否仍然存在获取引用相等性的危险？使用字典中的元组键似乎并非如此。在使用结构化F#类型的其他情况下是否可能发生？ - wmeyer

1

@wmeyer - 元组通过其组成值的相等性和哈希来定义它们的相等性和哈希。如果它们的值的相等性和哈希已经是结构化的，那么元组也将具有结构化的相等性和哈希（例如 int*int）。但是，如果它们的值不是结构化的，则元组的相等性和哈希也不会是结构化的（例如 int[]*int[]）。F# 的 = 运算符和 hash 函数即使在这些类型上也表现出结构性，HashIdentity.Structural 相等比较器也是如此。 - kvb

显示剩余8条评论

0

嗯..如果哈希表是主要的瓶颈，那么很可能是哈希函数本身的问题。虽然没有查看特定的哈希函数，但对于最常见的哈希函数之一，即

((a * x + b) % p) % q

模运算%非常缓慢，如果p和q采用2^k - 1的形式，则可以使用与、加和位移操作进行模运算。

Dietzfelbinger的通用哈希函数h_a：[2^w] -> [2^l]

lowerbound(((a * x) % 2^w)/2^(w-l))

其中a是w位的随机奇数种子。

它可以通过(a*x) >> (w-l)计算，比第一个哈希函数快得多。我不得不使用链表作为冲突处理来实现哈希表。它花费了10分钟来实现和测试，我们必须使用两个函数进行测试，并分析速度差异。第二个哈希函数速度提升了4-10倍，具体取决于表的大小。但要学习的事情是，如果程序的瓶颈是哈希表查找，则哈希函数也必须快速。

- kam

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ttsiodras · Accepted Answer

我通过电子邮件联系了Jon Harrop博士，他解释了正在发生的事情：

问题很简单，该程序已经针对Python进行了优化。当然，如果程序员更熟悉一种语言而不是另一种语言，这种情况很常见。您只需要学习一组不同的规则来指导如何优化F#程序... 有几件事情引起了我的注意，例如使用“for i in 1..n do”循环而不是“for i = 1 to n do”循环（通常更快但在这里不重要），重复在列表上执行List.mapi以模拟数组索引（这会不必要地分配中间列表）以及您使用F# TryGetValue for Dictionary进行字典查询，这会不必要地分配内存（.NET TryGetValue接受ref的方法通常更快，但在这里并没有太大作用）

...但真正致命的问题是您使用哈希表来实现密集的二维矩阵。在Python中使用哈希表是理想的，因为它的哈希表实现已经被极大地优化（正如您的Python代码运行得像编译成本机代码的F#一样快！），但是在表示密集矩阵时，数组是更好的方式，特别是当您需要默认值为零时。

有趣的是，当我第一次编写这个算法时，我确实使用了一个表格 - 由于清晰度的原因，我将实现更改为字典（避免了数组边界检查，使代码更简单 - 也更容易理解）。

Jon将我的代码转换回其array version，它运行速度快了100倍。

故事的寓意：

F#字典需要改进... 当使用元组作为键时，编译的F#比解释的Python的哈希表慢得多！
显而易见，但重复一遍没有坏处：清洁的代码有时意味着......更慢的代码。

谢谢，Jon--非常感谢。

编辑：用数组替换字典使F#最终以编译语言应有的速度运行，并不能否认需要修复字典速度的需求（我希望微软的F#人员能看到这一点）。其他算法依赖于字典/哈希，不能轻易地切换到使用数组；每当使用字典时使程序遭受“解释器速度”的影响，可以说是一个漏洞。如果像评论中一些人所说的那样，问题不在于F#而在于.NET字典，那么我会认为这...是.NET的一个漏洞！

编辑2：最清晰的解决方案，不需要算法转换为数组（有些算法根本不适合）是改变这个：

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

变成这个：

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

这个更改使得 F# 代码的运行速度快了 2.7 倍，最终超过了 Python（快了 1.6 倍）。奇怪的是，元组默认使用结构比较，因此原则上，在键上由字典执行的比较是相同的（有或没有使用 Structural）。Harrop 博士认为，速度差异可能归因于虚拟分派：“据我所知，.NET 并没有多少优化虚拟分派的工作，并且现代硬件上虚拟分派的成本非常高，因为它是一个“计算跳转”，会将程序计数器跳转到一个不可预测的位置，从而破坏分支预测逻辑，几乎肯定会导致整个 CPU 流水线被刷新和重新加载”。

简单来说，正如 Don Syme 所建议的（请查看下面三个答案），“在使用引用类型键与 .NET 集合同时使用时，明确使用结构哈希”。（Harrop 博士在下面的评论中还说，我们应该始终在使用 .NET 集合时使用结构比较）。

亲爱的 MS F# 团队，如果有自动修复的方法，请务必使用。