编译器优化的函数式代码比命令式代码表现更好的示例

Question

其中一种无副作用的引用透明函数式编程的承诺是这种代码可以被广泛优化。引用维基百科的话：

“在许多情况下，数据的不可变性可以通过允许编译器做出在命令式语言中不安全的假设，从而提高内联扩展的机会，从而提高执行效率。”

我想看到的是函数式语言编译器通过生成更好的优化代码而优于命令式编译器的示例。

编辑：我试图给出一个具体的场景，但显然这不是一个好主意。因此，我将尝试以不同的方式解释它。

程序员将思想（算法）转化为机器可以理解的语言。同时，翻译的最重要方面之一也是人类可以理解生成的代码。不幸的是，在许多情况下存在权衡：简洁易读的代码会受到慢速性能的影响，并且需要手动优化。这很容易出错，耗时，使代码难以阅读（甚至完全无法阅读）。

函数式语言的基础，如不变性和引用透明度，使编译器能够执行广泛的优化，可以取代代码的手动优化，并使程序员从中获得自由。我正在寻找思路（算法）及其实现的例子，以满足以下条件：

1. （函数式）实现与原始思路接近且易于理解，
2. 它被语言的编译器广泛优化了，
3. 在命令式语言中，如果没有减少简洁性和可读性的手动优化，很难（或不可能）编写出类似有效的代码。

如果答案的限制不必要，请原谅我的含糊不清。如果有人知道如何更好地表达这个思路，我很乐意接受建议。

我对此的兴趣不仅仅是理论上的。我想使用这些例子（除其他外）来激发学生对函数式编程的兴趣。

起初，我对评论中提出的一些例子不满意。但经过再次考虑，我收回了我的反对意见，那些是好的例子。请随意扩展它们到完整的答案，以便人们可以评论和投票支持它们。

---

这类示例最有可能是并行化的代码，可以利用多个CPU核心。通常在函数式语言中，这可以很容易地完成，而不会牺牲代码的简单性（比如在Haskell中添加par或pseq即可）。我也对其他非并行化的示例感兴趣。

- Petr

---

您可能对Neil Mitchell关于超级编译的论文感兴趣，论文链接为http://community.haskell.org/~ndm/supero/。 - Thomas M. DuBuisson

参考.trans.和懒惰优化（从O（n log n）到O（n））函数min = head.sort - josejuan

一般而言，如果算法完全相同，那么你正在比较运行时间和代码生成器；在这种情况下，有时语言的语义会改进一些东西。更有趣的是，当语言允许使用不同的算法时... - Don Stewart

一个很好的问题，却被人们投票关闭了。这个世界到底怎么了？！ - Nikita Volkov

@NikitaVolkov，就像Don建议的那样，您不会比较相同的算法。例如，快速排序是一种用于“原地”排序的命令式算法。您可以在Haskell中实现它，但您将不会学到任何关于引用透明性和效率的知识。或者，您可以实现通常的类似于函数式风格的快速排序并进行比较，但那么您将学不到任何东西，因为从语义上讲，这些算法确实完全不同。 - jberryman

Answer 1

在某些情况下，同样的算法在纯函数编程环境中会有更好的优化效果。特别是，stream fusion 允许由一系列循环组成的算法（这些循环可能形式各异：如 map、filter、fold、unfold）组合成单个循环。

在传统的命令式编程环境中，采用可变数据的循环进行等效的优化需要实现完全效果分析，而这是没有人去做的。

因此，对于那些被实现为顺序 ana- 和 catamorphisms 管道的算法类别，你可以保证获得无法在命令式环境中实现的优化结果。

- Don Stewart

---

记忆化呢？我相信在纯代码中有很多机会可以利用它。 - Nikita Volkov

记忆化很容易添加，困难的部分在于决定它何时真正有帮助，而不仅仅浪费大量内存。 - C. A. McCann

@C.A.McCann 你必须承认，“很多”是一个相当可疑的度量标准，特别是在如今可用内存的数量方面。无论如何，这是否意味着在GHC中没有基于记忆化的优化或计划实现任何优化？只是好奇。 - Nikita Volkov

@NikitaVolkov，自动记忆化优化很难做到正确，因为你不知道在哪里使用它们是有帮助的。但是当需要时，Haskell程序员很容易就会使用记忆化库，然后在他们的代码中输入memo。对我来说，这更像是“用户指导的优化”，而不是编码（显然，您必须了解问题和Haskell的评估模型才能知道在哪里放置它）。 - luqui

这有点引出了一个问题，即这两个是否是“相同的算法”。这些表达式看起来表面上很相似，但它们对数据的处理肯定不一样。 - tmyklebu

你可以使用模板元编程在C++中做类似的事情（参见Eigen，Blitz ++，std::valarray等），但这并不美观。 - Alexandre C.

Answer 2

最近一篇由Geoff Mainland, Simon Peyton Jones, Simon Marlow, Roman Leshchinskiy提交给ICFP 2013的论文Haskell beats C using generalised stream fusion描述了这样一个例子。摘要（有趣部分为粗体）：

流融合是一种强大的技术，可以自动将高级序列处理函数转换为高效实现。它已经被用于Haskell库中，用于操作字节数组、Unicode文本和未装箱向量。然而，一些操作，如向量附加，在标准流融合框架内仍然表现不佳。其他操作，如使用现代x86芯片上可用的SSE和AVX指令进行SIMD计算，似乎根本不适合该框架。

在本文中，我们介绍了广义流融合，解决了这些问题。关键的洞察力是将多个流表示捆绑在一起，每个表示都针对特定类别的流消费者进行调整。我们还描述了一种适用于使用SSE指令进行高效计算的流表示。我们的想法在修改过的GHC编译器和vector库的版本中得到实现。基准测试显示，使用我们的编译器和库编写的高级Haskell代码可以产生比编译器和手动向量化的C代码更快的代码。

- Petr

Answer 3

这只是一条注释，而不是答案：gcc有一个pure属性，表明它可以考虑到函数的纯净性；显而易见的原因在手册中已经提到了这里。

我认为'Static Single Assignment'强制实施了一种纯净的形式 - 请参阅http://lambda-the-ultimate.org/node/2860或维基百科文章中的链接。

- Michael

Answer 4

通过假设各种构建步骤是引用透明的，使得make和其他构建系统在大型项目中表现更好；因此，它们只需要重新运行那些输入发生变化的步骤。

对于小到中等规模的更改，这比从头开始构建要快得多。

- MSN

---

虽然这是一个很好的例子，但我认为它并没有回答我的问题——编译器优化的函数式代码比命令式代码表现更好的示例。 - Petr