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

无副作用函数编程的承诺之一是可以对这些代码进行广泛优化 . 引用Wikipedia

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

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

Edit: 我试图给出一个特定的场景,但显然它并没有尝试以不同的方式解释它 .

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

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

  • (功能)实现接近原始想法并且易于理解,

  • 它被语言的编译器广泛优化,并且

  • 很难(或不可能)用命令式语言编写类似的高效代码,而无需手动优化,降低其简洁性和可读性 .

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

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

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


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

回答(4)

2 years ago

在某些情况下,相同的算法将在纯上下文中更好地优化 . 具体来说,stream fusion允许一种算法,该算法由一系列可能形式各异的循环组成: Map ,滤波器,折叠,展开,组成一个循环 .

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

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

2 years ago

Geoff大陆最近发表的一篇论文,Simon Peyton Jones,Simon Marlow,Roman Leshchinskiy(提交给ICFP 2013)描述了这样一个例子 . 摘要(粗体中有趣的部分):

流融合[6]是一种强大的技术,可将高级序列处理功能自动转换为高效实现 . 它已经在Haskell库中用于操作字节数组,Unicode文本和未装箱的向量 . 但是,某些操作(如vector append)在标准流融合框架中仍然表现不佳 . 其他人,比如使用现代x86芯片上提供的SSE和AVX指令的SIMD计算,似乎根本不适合框架 . 在本文中,我们介绍了广义流融合,它解决了这些问题 . 关键的见解是将多个流表示捆绑在一起,每个流表示针对特定类的流消费者进行调整 . 我们还描述了适合于使用SSE指令进行有效计算的流表示 . 我们的想法是在GHC编译器和矢量库的修改版本中实现的 . 基准测试表明,使用我们的编译器和库编写的高级Haskell代码可以生成比编译器和手动向量化C更快的代码 .

2 years ago

这只是一个注释,而不是答案: gcc 具有 pure 属性,表明它可以考虑纯度;显而易见的原因在手册_751461中有所说明 .

我认为'static single assignment'强加了一种纯度 - 见http://lambda-the-ultimate.org/node/2860或者维基百科文章 .

2 years ago

通过假设各种构建步骤是引用透明的,make和各种构建系统对大型项目执行得更好;因此,他们只需要重新运行已经改变输入的步骤 .

对于中小型更改,这比从头开始构建要快得多 .