编译器优化的功能代码比命令式代码执行得更好的示例

Question

无副作用,引用透明的函数编程的承诺之一是可以广泛优化这样的代码.引用维基百科:

在许多情况下,数据的不可变性可以通过允许编译器在命令式语言中做出不安全的假设来提高执行效率,从而增加强调文本在线扩展的机会.

我想看一些示例,其中函数式语言编译器通过生成更好的优化代码来优于命令式编译器.

编辑:我试图给出一个特定的场景,但显然这不是一个好主意.所以我会尝试以不同的方式解释它.

程序员将想法(算法)翻译成机器可以理解的语言.同时,翻译的一个最重要的方面是人类也可以理解产生的代码.不幸的是,在许多情况下需要权衡:简洁易读的代码会受到性能降低的影响,需要手动优化.这容易出错,耗时,并且使代码的可读性降低(完全不可读).

函数式语言的基础,例如不变性和引用透明性,允许编译器执行广泛的优化,这可以取代手动优化代码和免费程序员进行权衡.我正在寻找想法(算法)及其实现的示例,例如:

1. (功能)实现接近最初的想法,很容易理解,
2. 它由语言的编译器进行了广泛的优化,并且
3. 在命令式语言中编写类似的高效代码很难(或不可能),而无需手动优化,降低其简洁性和可读性.

如果它有点模糊,我道歉,但我希望这个想法很明确.我不想对答案给予不必要的限制.如果有人知道如何更好地表达它,我愿意接受建议.

我的兴趣不仅仅是理论上的.我想使用这些例子(以及其他内容)来激发学生对函数式编程感兴趣.

起初,我对评论中提出的一些例子并不满意.我想再次反对,这些都是很好的例子.请随意将它们扩展为完整的答案,以便人们可以评论并投票给他们.

---

(一类这样的例子很可能是并行化代码,它可以利用多个CPU内核.通常在函数式语言中,这可以轻松完成而不会牺牲代码的简单性(比如在Haskell中添加par或pseq在适当的位置).我是对这些例子感兴趣,但也对其他非平行的例子感兴趣.)

Answer 1

在某些情况下,相同的算法将在纯上下文中更好地优化.具体而言,流融合允许由一系列循环组成的算法,这些循环可以具有广泛变化的形式:地图,过滤器,折叠,展开,以组成单个循环.

传统的命令式设置中的等效优化,在循环中具有可变数据,必须实现完整的效果分析,没有人这样做.

因此,至少对于作为序列上的ana-和catamorphisms的管道实现的算法类,您可以保证在命令设置中不可能的优化结果.

Answer 2

最近的一篇论文Haskell使用 Geoff大陆的广义流融合击败C,Simon Peyton Jones,Simon Marlow,Roman Leshchinskiy(提交给ICFP 2013)描述了这样一个例子.摘要(粗体中有趣的部分):

流融合[6]是一种强大的技术,可将高级序列处理功能自动转换为高效实现.它已经在Haskell库中用于操作字节数组,Unicode文本和未装箱的向量.但是,某些操作(如vector append)在标准流融合框架中仍然表现不佳.其他人,比如使用现代x86芯片上提供的SSE和AVX指令的SIMD计算,似乎根本不适合框架.

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