FSharp的算法运行速度比Python慢

小编典典

FSharp的算法运行速度比Python慢

algorithm

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

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

（以防您注意到上面的“单声道”：我也在Windows下，使用Visual Studio进行了测试-速度相同）。

至少可以说，我很困惑。Python比F＃运行代码更快？使用.NET运行时的已编译二进制文件比Python的解释代码慢！

我知道VM的启动成本（在这种情况下为单例），以及JIT如何改善Python等语言的性能，但是…我仍然希望能加快速度，而不是减慢速度！

也许我做错了什么？

我在这里上传了代码：

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

请注意，F＃代码或多或少是Python代码的直接逐行转换。

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

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

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

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

阅读 313

2020-07-28

共1个答案

小编典典

通过电子邮件与我联系的Jon Harrop博士解释了发生的情况：

问题仅在于该程序已针对Python优化。当然，当程序员比另一种语言更熟悉一种语言时，这很常见。您只需要学习一组不同的规则，这些规则就应如何优化F＃程序。…突然出现了一些事情，例如使用“
1..n do中的for for”循环而不是“ for i” = 1到n
do“循环（通常更快，但在这里不重要），在列表上重复执行List.mapi以模仿数组索引（不必要地分配了中间列表），并且您使用F＃TryGetValue
for Dictionary来分配不必要地（接受引用的.NET TryGetValue通常更快，但在这里并没有那么快）

…但是真正的杀手级问题竟然是您使用哈希表来实现密集的2D矩阵。在Python中使用哈希表是理想的选择，因为它的哈希表实现已经过非常出色的优化（事实证明，您的Python代码的运行速度与F＃编译为本机代码一样快！），但是数组是表示密集代码的更好方法。矩阵，尤其是当您希望默认值为零时。

有趣的是，当我第一次编码算法，我 DID 使用一个表-我改变了实施的字典为了清楚起见，（避免数组边界检查使代码更简单-和更容易推理）。

乔恩（Jon）将我的代码（back :-)转换为其数组版本，并以100倍的速度运行。

故事的道德启示：

F＃字典需要工作…使用元组作为键时，已编译的F＃比解释的Python哈希表要慢！
显而易见，但无害于重复：简洁的代码有时意味着……慢得多的代码。

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

编辑
：用Array代替Dictionary使得F＃最终以预期的已编译语言运行的速度运行，这一事实并没有消除对Dictionary速度的修复的需要（我希望MS的F＃人员正在阅读此书）。其他算法取决于字典/哈希，因此无法轻松切换为使用数组。使程序每当使用字典时都会遭受“解释器速度”的困扰，这可以说是一个错误。如果像某些人在评论中说的那样，问题不出在F＃上，而是.NET字典，那么我认为这是.NET中的错误！

EDIT2 ：最清晰的解决方案是更改此方法，该解决方案不需要算法切换到数组（某些算法根本不适合该算法）：

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

到这个：

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

这一更改使F＃代码的运行速度提高了2.7倍，从而最终击败了Python（提高了1.6倍）。奇怪的是， 默认情况下
，元组使用结构化比较，因此，原则上，字典对键进行的比较是相同的（有或没有结构化）。Harrop博士认为，速度差异可能归因于虚拟调度： “
AFAIK，.NET在优化虚拟调度方面做得很少，而在现代硬件上虚拟调度的成本非常高，因为它是跳过程序的“计算目标”与不可预测的位置相对应，因此破坏了分支预测逻辑，几乎可以肯定会导致整个CPU管道被刷新并重新加载
。”

简而言之，正如Don
Syme所建议的那样（请看底部的3个答案），“当将引用类型的键与.NET集合结合使用时，应明确使用结构化哈希”。（Harrop博士在下面的评论中还说，使用.NET集合时，应
始终使用结构比较）。

亲爱的MS中的F＃小组，如果有一种自动解决此问题的方法，请这样做。

2020-07-28