PyR*_*lez 223 performance haskell lambda-calculus ghc higher-order-functions
Haskell(使用GHC编译器)比你期望的要快很多.如果使用得当,它可以与低级语言保持密切联系.(Haskellers最喜欢的事情是尝试在C的5%范围内(或者甚至击败它,但这意味着你使用的是低效的C程序,因为GHC将Haskell编译为C).)我的问题是,为什么？
Haskell是声明性的,基于lambda演算.机器架构显然势在必行,粗略地基于图灵机.实际上,Haskell甚至没有具体的评估顺序.此外,您不必处理机器数据类型,而是始终生成代数数据类型.
最奇怪的是更高阶函数.你会认为动态创建函数并抛出它们会使程序变慢.但是使用更高阶函数实际上使Haskell更快.实际上,似乎要优化Haskell代码,你需要使它更优雅和抽象,而不是更像机器.如果Haskell的更高级功能没有改进,它们似乎甚至都不会影响它的性能.
很抱歉,如果这听起来不错,但这是我的问题:为什么Haskell(使用GHC编译)如此之快,考虑到它的抽象性质和与物理机器的差异？
注意:我说C和其他命令式语言有点类似于图灵机的原因(但不是Haskell类似于Lambda微积分)是因为在命令式语言中,你有一个有限数量的状态(也就是行号) ,以及磁带(ram),以便状态和当前磁带确定对磁带做什么.有关从图灵机到计算机的过渡,请参阅维基百科条目,图灵机等效项.
Mat*_*hid 239
我认为这个是基于意见的.但我会尽力回答.
我同意Dietrich Epp的看法:这是GHC快速发展的几个因素的组合.
首先,Haskell是非常高级的.这使编译器能够在不破坏代码的情况下执行积极的优化.
想想SQL.现在,当我写一个SELECT语句时,它可能看起来像一个命令式循环,但事实并非如此.它可能看起来像遍历该表中的所有行,试图找到与指定条件匹配的那一行,但实际上 "编译器"(数据库引擎)可能正在进行索引查找 - 它具有完全不同的性能特征.但由于SQL是如此高级,"编译器"可以替代完全不同的算法,透明地应用多个处理器或I/O通道或整个服务器等等.
我认为Haskell是一样的.您可能认为您刚刚要求Haskell将输入列表映射到第二个列表,将第二个列表过滤到第三个列表,然后计算产生的项目数.但你没有看到GHC在幕后应用流融合重写规则,将整个事物转换为一个紧密的机器代码循环,在没有分配的情况下一次性完成整个工作 - 这种事情会手工编写是单调乏味,容易出错且无法维护的.这是唯一真正可能的,因为代码中缺少低级细节.
另一种看待它的方法可能是......为什么Haskell 不应该快？它应该做什么应该让它变慢？
它不是像Perl或JavaScript这样的解释语言.它甚至不是像Java或C#这样的虚拟机系统.它一直编译到本机机器代码,所以没有开销.
与OO语言[Java,C#,JavaScript ...]不同,Haskell具有完全类型擦除[如C,C++,Pascal ...].所有类型检查仅在编译时进行.因此,没有运行时类型检查可以减慢您的速度.(就此而言,没有空指针检查.例如,在Java中,JVM必须检查空指针,如果你尊重它,则抛出异常.Haskell不必费心去检查.)
你说"在运行时动态创建函数"听起来很慢,但如果仔细观察,你实际上并没有这样做.它看起来可能像你一样,但你没有.如果你说(+5),那么,它已被硬编码到您的源代码中.它不能在运行时更改.所以它不是一个真正的动态功能.即使是curried函数实际上只是将参数保存到数据块中.所有可执行代码实际上都在编译时存在; 没有运行时解释.(与其他一些具有"评估功能"的语言不同.)
想想Pascal.它已经老了,没有人真正使用它,但是没有人会抱怨Pascal很慢.有很多东西不喜欢它,但缓慢并不是真正的其中之一.除了垃圾收集而不是手动内存管理之外,Haskell并没有真正做到与Pascal不同的那么多.并且不可变数据允许对GC引擎进行多次优化[懒惰评估然后稍微复杂化].
我认为事情是Haskell 看起来先进,精致和高级,每个人都认为"哦,哇,这真的很强大,它一定非常慢! "但事实并非如此.或者至少,它不是你期望的方式.是的,它有一个惊人的类型系统.但你知道吗？这一切都发生在编译时.通过运行时,它已经消失了.是的,它允许您使用一行代码构造复杂的ADT.但你知道吗？一个ADT只是一个简单的普通的C union的struct秒.而已.
真正的杀手是懒惰的评价.当你正确地得到你的代码的严格/懒惰时,你可以写出仍然优雅和美丽的愚蠢的快速代码.但如果你把这些东西弄错了,你的程序会慢几千倍,而且为什么会发生这种情况真的不明显.
例如,我编写了一个简单的小程序来计算每个字节出现在文件中的次数.对于一个25KB的输入文件,该程序需要20分钟才能运行并吞下6GB的RAM!那太荒谬了!! 但后来我意识到问题是什么,增加了一个爆炸模式,运行时间下降到0.02秒.
这就是Haskell出乎意料地慢慢走的地方.确实需要一段时间才能适应它.但随着时间的推移,编写真正快速的代码会变得更容易.
是什么让Haskell如此之快？纯度.静态类型.懒惰.但最重要的是,要达到足够高的水平,编译器可以从根本上改变实现,而不会破坏代码的期望.
但我猜这只是我的意见......
scl*_*clv 70
很长一段时间以来,人们一直认为函数式语言不是很快 - 特别是懒惰的函数式语言.但这是因为他们的早期实现本质上是解释而不是真正编译.
第二波设计基于图形缩减而出现,并为更高效的编译开辟了可能性.Simon Peyton Jones在他的两本书"功能编程语言的实现和实现函数式语言:一个教程(前者有Wadler和Hancock的部分,后者用David Lester编写)"中写到了这项研究.(Lennart Augustsson还告诉我,前一本书的一个主要动机是描述他的LML编译器的方式,该编译器没有得到广泛的评论,完成了它的编译).
这些工作中描述的图缩减方法背后的关键概念是我们不将程序视为指令序列,而是通过一系列局部约简来评估依赖图.第二个关键的见解是,不需要解释对这种图的评估,而是图形本身可以由代码构建.特别是,我们可以将图形的节点表示为"无论是值还是'操作码'以及要操作的值",而是作为调用时返回所需值的函数.第一次调用它时,它会询问子节点的值,然后对它们进行操作,然后用一条新的指令覆盖它自己,该指令只是说"返回结果".
这在后面的文章中进行了描述,该文章介绍了GHC如何在今天仍然有效的基础(虽然模数很多种调整):"在库存硬件上实现懒惰功能语言:无脊椎无标签G-Machine"..GHC的当前执行模型在GHC Wiki中有更详细的记录.
因此,我们的洞察力是,严格区分"数据"和"代码",我们认为它们是机器如何工作的"基础",而不是它们必须如何工作,而是由我们的编译器强加的.所以我们可以抛弃它,并拥有生成自修改代码(可执行文件)的代码(编译器),它可以很好地工作.
因此,事实证明,虽然机器架构在某种意义上是必不可少的,但语言可能会以非常令人惊讶的方式映射到它们,这看起来不像传统的C风格的流量控制,如果我们认为低级别,这也可能是高效.
除此之外,还有许多其他优化由纯度打开,因为它允许更大范围的"安全"转换.何时以及如何应用这些转变使得它们使事情变得更好而不是更糟,当然是一个经验问题,在这个和许多其他小的选择上,多年的工作已经被纳入理论工作和实际基准.所以这当然也起了作用.提供此类研究的一个很好的例子的论文是" 快速咖喱:推/输与对比/适用于高阶语言".
最后,应该注意的是,由于间接性,该模型仍然引入了开销.在我们知道严格执行操作并因此忽略图表间接是"安全"的情况下,可以避免这种情况.在GHC Wiki上再次详细记录了推断严格性/需求的机制.
小智 17
嗯,这里有很多评论.我会尽可能多地回答.
如果使用得当,它可以与低级语言保持密切联系.
根据我的经验,在很多情况下,通常可以将Rust的性能提高2倍.但是也存在一些(广泛的)用例,与低级语言相比,性能较差.
甚至击败它,但这意味着你正在使用低效的C程序,因为GHC将Haskell编译为C)
这不完全正确.Haskell编译为C--(C的一个子集),然后通过本机代码生成器编译到汇编.本机代码生成器通常生成比C编译器更快的代码,因为它可以应用普通C编译器无法实现的一些优化.
机器架构显然势在必行,粗略地基于图灵机.
这不是考虑它的好方法,特别是因为现代处理器将无序地并且可能同时评估指令.
实际上,Haskell甚至没有具体的评估顺序.
其实,哈斯克尔没有隐含地定义的评估顺序.
此外,您不必处理机器数据类型,而是始终生成代数数据类型.
如果您拥有足够先进的编译器,它们在许多情况下都是对应的.
你会认为动态创建函数并抛出它们会使程序变慢.
Haskell是编译的,因此高阶函数实际上并不是动态创建的.
它似乎优化了Haskell代码,你需要使它更优雅和抽象,而不是更像机器.
通常,使代码更"机器化"是在Haskell中获得更好性能的非生产性方法.但是让它更抽象也不总是一个好主意.什么是好主意是使用经过大量优化的常见数据结构和函数(例如链表).
f x = [x]而f = pure在Haskell中完全一样的东西,例如.一个好的编译器在前一种情况下不会产生更好的性能.
为什么Haskell(使用GHC编译)如此之快,考虑到它的抽象性质和与物理机器的差异？
简短的回答是"因为它的设计就是为了做到这一点." GHC使用无脊椎无标记g-machine(STG).你可以在这里阅读一篇关于它的论文(它非常复杂).GHC还做了很多其他事情,例如严格性分析和乐观评估.
我说C和其他命令式语言有点类似于图灵机的原因(但不是Haskell类似于Lambda微积分)是因为在命令式语言中,你有一个有限数量的状态(也就是行号),使用磁带(ram),以便状态和当前磁带确定如何对磁带执行操作.
那么混淆是否会导致代码变慢？Haskell的懒惰实际上意味着可变性并不像你想象的那么重要,加上它的高级别,因此编译器可以应用许多优化.因此,就地修改记录很少会比C等语言慢.