为什么Haskell (GHC)这么快?

我同意Dietrich Epp的观点:它是几件事情的组合，使GHC快速。

首先，Haskell的级别很高。这使得编译器可以在不破坏代码的情况下执行积极优化。

想想SQL。现在，当我编写SELECT语句时，它可能会看起来像一个命令式循环，但事实并非如此。它可能看起来像遍历表中的所有行，试图找到与指定条件匹配的行，但实际上“编译器”(DB引擎)可能正在做索引查找。它们有着完全不同的性能特征。但是由于SQL是如此高级，“编译器”可以替代完全不同的算法，透明地应用多个处理器或I/O通道或整个服务器等等。

我觉得哈斯克尔也一样。你可能认为你刚刚要求Haskell将输入列表映射到第二个列表，将第二个列表过滤为第三个列表，然后计算产生了多少项。但是你没有看到GHC在幕后应用流融合重写规则，将整个事情转换成一个紧凑的机器代码循环，在一次数据传递中完成整个工作，没有分配—用手写这些东西会很乏味，容易出错，而且不可维护。这只是因为代码中缺乏低层细节才真正可能实现。

另一种看待它的方式可能是为什么不应该 Haskell是快?它做了什么会让它变慢?

它不是像Perl或JavaScript那样的解释性语言。它甚至不是像Java或c#那样的虚拟机系统。它一直编译到本地机器代码，所以没有开销。

与面向对象语言[Java, c#， JavaScript…]不同，Haskell具有完全类型擦除[像C, c++， Pascal…]。所有类型检查只在编译时发生。因此，也没有运行时类型检查来降低您的速度。(就此而言，没有空指针检查。例如，在Java中，JVM必须检查空指针，如果遵从一个空指针，则抛出异常。Haskell不需要为支票而烦恼。)

您说“在运行时动态地创建函数”听起来很慢，但如果您非常仔细地观察，实际上并没有这样做。它可能看起来像你做，但你没有。如果你说(+5)，好吧，这是硬编码到你的源代码。它不能在运行时更改。所以它不是一个真正的动态函数。即使是curry函数实际上也只是将参数保存到数据块中。所有可执行代码实际上都存在于编译时;没有运行时解释。(不像其他一些有“eval函数”的语言。)

想想帕斯卡。它很老了，没有人再使用它了，但是没有人会抱怨Pascal是慢。它有很多令人不喜欢的地方，但慢并不是其中之一。Haskell除了垃圾收集而不是手动内存管理之外，并没有做太多与Pascal不同的事情。不可变的数据允许对GC引擎进行一些优化(惰性计算会使其变得有些复杂)。

我认为事情是Haskell 看起来先进、复杂和高级，每个人都认为“哦哇，这真的很强大，它一定慢得惊人!”，但它不是。或者至少，它不是你所期望的方式。是的，它有一个惊人的类型系统。但你知道吗?这一切都发生在编译时。到运行时，它就消失了。是的，它允许你用一行代码构建复杂的adt。但你知道吗?ADT只是一个普通的__abc1中的C union。仅此而已。

真正的杀手是懒惰的评估。当你正确地处理代码的严格/懒惰时，你可以写出非常快的代码，但仍然优雅而美丽。但是如果你把这个东西弄错了，你的程序就会慢了几千倍，而且发生这种情况的原因真的不明显。

例如，我写了一个简单的小程序来计算每个字节在文件中出现的次数。对于一个25KB的输入文件，程序运行20分钟并占用RAM的6字节 !这是荒谬的! !但后来我意识到问题所在，添加了一个刘海模式，运行时下降到0.02秒。

这是Haskell走得出乎意料慢的地方。这当然需要一段时间来适应。但是随着时间的推移，编写非常快速的代码变得更加容易。

是什么让哈斯克尔这么快?纯洁。静态类型。懒惰。但最重要的是，要足够高级，编译器可以在不破坏代码预期的情况下从根本上改变实现。

但我想这只是我的个人观点……

很长一段时间以来，人们都认为函数语言不可能快——尤其是懒惰的函数语言。但这是因为它们的早期实现本质上是解释的，而不是真正的编译。

基于图约简的第二波设计出现了，为更高效的编译提供了可能。西蒙·佩顿·琼斯(Simon Peyton Jones)在他的两本书函数式编程语言的实现和实现函数式语言:教程中描述了这项研究(前者由Wadler和Hancock撰写，后者由David Lester撰写)。(Lennart Augustsson还告诉我，前一本书的一个关键动机是描述他的LML编译器完成编译的方式，该编译器没有得到广泛的评论)。

在这些著作中描述的图约简方法背后的关键概念是，我们不认为程序是一个指令序列，而是一个依赖图，它是评估，通过一系列局部约简。第二个关键的见解是，这样一个图的求值不需要解释，而图本身可以是由代码构建。特别地，我们可以将一个图的节点表示为“一个值或一个操作码和要操作的值”，而不是一个函数，当调用它时，返回所需的值。第一次调用它时，它会询问子节点的值，然后对它们进行操作，然后它会用一个只说“返回结果”的新指令重写自己。

这将在后面的论文中描述，该论文为GHC今天仍然如何工作(尽管对许多不同的调整进行了模)奠定了基础:在普通硬件上实现惰性函数语言:无骨无标签的G-Machine。GHC的当前执行模型在GHC维基中有更详细的文档。

因此，我们的见解是，“数据”和“代码”之间的严格区别，我们认为这是机器工作的“基础”，但不是它们必须这样工作，而是由我们的编译器强加的。因此，我们可以抛弃它，让代码(编译器)生成自我修改的代码(可执行文件)，这一切都可以很好地工作。

因此，虽然机器架构在某种意义上是必要的，但语言可能会以非常令人惊讶的方式映射到它们，这些方式看起来不像传统的c风格的流控制，如果我们足够低级，这也可能是有效的。

除此之外，pure还提供了许多其他优化，因为它允许更大范围的“安全”转换。何时以及如何应用这些转换，使事情变得更好而不是更糟，这当然是一个经验问题，在这个和许多其他小的选择上，多年的工作已经投入到理论工作和实际基准测试中。这当然也有作用。一篇论文提供了一个很好的例子，这类研究是“制作一个快速咖喱:Push/Enter vs. Eval/Apply for Higher-Order Languages。”

最后，应该注意的是，由于间接，该模型仍然引入了开销。这可以避免在我们知道严格地做事情是“安全的”的情况下，从而省略图的间接。推断严格/要求的机制在GHC维基中再次详细记录。

这里有很多值得评论的地方。我会尽量多回答的。

如果使用得当，它可以接近低级语言。

根据我的经验，在很多情况下，它的性能通常可以达到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-machine (STG)。你可以读一篇关于它的论文(它相当复杂)。GHC也做了很多其他的事情，比如严格性分析和乐观的评估。

我之所以说C和其他命令式语言有点类似于图灵机(但没有到Haskell类似于Lambda Calculus的程度)，是因为在命令式语言中，您有有限数量的状态(也就是行号)，以及一个磁带(ram)，这样状态和当前磁带就决定了对磁带做什么。

那么让人困惑的是可变性会导致代码变慢吗?Haskell的惰性实际上意味着可变性并不像你想象的那么重要，加上它是高级的，所以编译器可以应用许多优化。因此，就地修改记录几乎不会比在C等语言中慢。