Haskell(使用 GHC
编译器)是一个 lot faster than you'd expect。正确使用,它可以接近低级语言。 (Haskellers 最喜欢做的一件事情是尝试在 C 的 5% 以内(甚至超过它,但这意味着您使用的是低效的 C 程序,因为 GHC 将 Haskell 编译为 C)。)我的问题是,为什么?
Haskell 是声明式的并且基于 lambda 演算。机器架构显然是必不可少的,大致基于图灵机。事实上,Haskell 甚至没有具体的评估顺序。此外,您总是创建代数数据类型,而不是处理机器数据类型。
最奇怪的是高阶函数。您会认为动态创建函数并将它们扔掉会使程序变慢。 But using higher order functions actually makes Haskell faster. 实际上,要优化 Haskell 代码,您似乎需要使其更优雅和抽象,而不是更像机器。 Haskell 更高级的特性似乎都影响它的性能,如果它们不改进它的话。
对不起,如果这听起来很无礼,但这是我的问题:考虑到 Haskell(用 GHC 编译)的抽象性质和与物理机器的区别,为什么这么快?
注意:我说 C 和其他命令式语言与图灵机有些相似(但不是 Haskell 与 Lambda 演算相似的程度)的原因是,在命令式语言中,您有有限数量的状态(也称为行号) ,以及磁带(ram),以便状态和当前磁带确定对磁带执行的操作。有关从图灵机到计算机的过渡,请参阅 Wikipedia 条目 Turing machine equivalents。
我同意 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)
,那么它已硬编码到您的源代码中。它不能在运行时更改。所以它不是一个真正的动态函数。甚至柯里化函数实际上只是将参数保存到数据块中。所有可执行代码实际上都存在于编译时;没有运行时解释。 (与其他一些具有“评估功能”的语言不同。)
想想帕斯卡。它很旧,没有人真正使用它,但没有人会抱怨 Pascal 很慢。有很多不喜欢它的地方,但缓慢并不是其中之一。 Haskell 并没有真正做与 Pascal 不同的事情,除了垃圾收集而不是手动内存管理。并且不可变数据允许对 GC 引擎进行多项优化(惰性求值因此变得有些复杂)。
我认为问题在于 Haskell 看起来高级、复杂和高级,每个人都认为“哇哦,这真的很强大,它一定非常慢!”但是不是。或者至少,它不是你所期望的那样。是的,它有一个惊人的类型系统。但你知道吗?这一切都发生在编译时。到运行时,它已经消失了。是的,它允许您使用一行代码构建复杂的 ADT。但你知道吗? ADT 只是 struct
的普通 C union
。而已。
真正的杀手是懒惰的评价。当你的代码的严格性/惰性正确时,你可以编写出仍然优雅和漂亮的愚蠢快速的代码。但是如果你把这些东西弄错了,你的程序就会慢几千倍,而且为什么会发生这种情况真的很不明显。
例如,我编写了一个简单的小程序来计算每个字节在文件中出现的次数。对于一个 25KB 的输入文件,该程序需要 20 分钟才能运行并吞下 6 GB 的 RAM!太荒谬了!!但后来我意识到问题出在哪里,添加了一个 bang-pattern,运行时间下降到 0.02 秒。
这就是 Haskell 出人意料地缓慢发展的地方。而且肯定需要一段时间才能习惯。但随着时间的推移,编写真正快速的代码会变得更容易。
是什么让 Haskell 如此之快?纯度。静态类型。懒惰。但最重要的是,足够高级,编译器可以从根本上改变实现而不会破坏代码的期望。
但我想这只是我的看法...
长期以来,人们认为函数式语言不能很快——尤其是惰性函数式语言。但这是因为它们的早期实现本质上是解释性的,而不是真正编译的。
基于图缩减的第二波设计出现了,为更高效的编译开辟了可能性。西蒙·佩顿·琼斯 (Simon Peyton Jones) 在他的两本书 The Implementation of Functional Programming Languages 和 Implementing functional languages: a tutorial 中描述了这项研究(前者由 Wadler 和 Hancock 撰写,后者由 David Lester 撰写)。 (Lennart Augustsson 还告诉我,前一本书的一个关键动机是描述他的 LML 编译器完成编译的方式,没有得到广泛的评论)。
这些作品中描述的图归约方法背后的关键概念是,我们不将程序视为指令序列,而是将依赖图视为通过一系列局部归约进行评估的依赖图。第二个关键见解是不需要解释对这种图的评估,而是可以用代码构建图本身。特别是,我们可以不将图的节点表示为“值或'操作码'和要操作的值”,而是表示为一个函数,在调用时返回所需的值。第一次调用它时,它会向子节点询问它们的值,然后对它们进行操作,然后用一条新指令覆盖自己,这条指令只是说“返回结果”。
这在稍后的一篇论文中进行了描述,该论文阐述了 GHC 如何在今天仍然工作的基础知识(尽管以许多不同的调整为模):"Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-Machine."。 GHC 的当前执行模型在 GHC Wiki 中有更详细的说明。
因此,洞察力是,我们认为机器如何工作的“基础”“数据”和“代码”的严格区别并不是它们必须如何工作,而是由我们的编译器强加的。所以我们可以把它扔掉,并拥有生成自修改代码(可执行文件)的代码(编译器),它可以很好地工作。
因此事实证明,虽然机器架构在某种意义上是必不可少的,但语言可能会以非常令人惊讶的方式映射到它们,这看起来不像传统的 C 风格的流控制,如果我们认为足够低级,这也可能是高效的。
除此之外,还有许多其他优化,特别是纯度开放,因为它允许更大范围的“安全”转换。何时以及如何应用这些转换以使事情变得更好而不是更糟当然是一个经验问题,并且在这个和许多其他小的选择上,多年来的工作已经投入到理论工作和实际基准测试中。所以这当然也起作用。提供此类研究的一个很好例子的论文是“Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-Order Languages."
最后,应该注意的是,该模型仍然由于间接而引入了开销。在我们知道严格执行某些事情是“安全的”并因此省略了图形间接的情况下,可以避免这种情况。 GHC Wiki 再次详细记录了推断严格性/需求的机制。
嗯,这里有很多要评论的。我会尽量回答。
正确使用,它可以接近低级语言。
以我的经验,在许多情况下,通常可以将 Rust 的性能提高到 2 倍以内。但也有一些(广泛的)用例与低级语言相比性能较差。
甚至击败它,但这意味着您使用的是效率低下的 C 程序,因为 GHC 将 Haskell 编译为 C)
这并不完全正确。 Haskell 编译为 C--(C 的一个子集),然后通过本机代码生成器编译为汇编。本机代码生成器通常生成比 C 编译器更快的代码,因为它可以应用一些普通 C 编译器无法做到的优化。
机器架构显然是必不可少的,大致基于图灵机。
这不是一个很好的思考方式,特别是因为现代处理器会乱序评估指令,并且可能同时进行。
事实上,Haskell 甚至没有具体的评估顺序。
实际上,Haskell 确实隐含地定义了评估顺序。
此外,您总是创建代数数据类型,而不是处理机器数据类型。
只要您有足够先进的编译器,它们在许多情况下都是对应的。
您会认为动态创建函数并将它们扔掉会使程序变慢。
Haskell 是编译好的,所以高阶函数实际上并不是动态创建的。
似乎优化了 Haskell 代码,你需要让它更优雅和抽象,而不是更像机器。
一般来说,让代码更像“机器”是在 Haskell 中获得更好性能的一种低效方法。但使其更抽象也并不总是一个好主意。使用经过大量优化的通用数据结构和函数(例如链表)是一个好主意。
例如,f x = [x]
和 f = pure
在 Haskell 中是完全相同的。在前一种情况下,一个好的编译器不会产生更好的性能。
为什么 Haskell(用 GHC 编译)这么快,考虑到它的抽象性质和与物理机器的区别?
简短的回答是“因为它旨在做到这一点。” GHC 使用无脊椎无标签 g 机器 (STG)。您可以阅读一篇关于它的论文here(它非常复杂)。 GHC 还做了很多其他事情,例如严格性分析和optimistic evaluation。
我说 C 和其他命令式语言与图灵机有些相似(但不是 Haskell 与 Lambda 演算相似的程度)的原因是,在命令式语言中,你有有限数量的状态(也就是行号),沿着使用磁带(ram),以便状态和当前磁带确定对磁带执行的操作。
那么混淆点是否会导致代码变慢? Haskell 的惰性实际上意味着可变性并不像您想象的那么重要,而且它是高级别的,因此编译器可以应用许多优化。因此,就地修改记录很少会比在诸如 C 之类的语言中慢。
不定期副业成功案例分享