compilation - 函数式语言天生就慢吗？

Question

关闭。这个问题是 opinion-based 。它目前不接受答案。












想改善这个问题吗？更新问题，以便可以通过 editing this post 用事实和引文来回答。

7年前关闭。



Improve this question




为什么函数式语言在基准测试中总是落后于 C？如果您有静态类型的函数式语言，在我看来，它可以编译为与 C 相同的代码，或者编译为更优化的代码，因为编译器可以使用更多语义。为什么看起来所有函数式语言都比 C 慢，为什么它们总是需要垃圾收集和过度使用堆？

有没有人知道一种适用于嵌入式/实时应用程序的函数式语言，其中内存分配保持在最低限度并且生成的机器代码精简而快速？

Answer 1

Are functional languages inherently slow?

从某种意义上说，是的。他们需要的基础设施不可避免地增加了理论上使用手工汇编程序可以实现的开销。特别是，一流的词法闭包只适用于垃圾收集，因为它们允许值超出范围。

Why are functional languages always tailing behind C in benchmarks?

首先，要注意选择偏差。 C 作为基准套件中的最低公分母，限制了可以完成的工作。如果你有一个比较 C 和函数式语言的基准，那么它几乎可以肯定是一个非常简单的程序。可以说如此简单，以至于今天几乎没有实际意义。仅将 C 用作基准来解决更复杂的问题实际上是不可行的。

最明显的例子是并行性。今天，我们都有多核。连我的手机都是多核的。众所周知，多核并行在 C 中非常困难，但在函数式语言中很容易(我喜欢 F#)。其他示例包括任何受益于持久数据结构的东西，例如撤消缓冲区对于纯函数式数据结构来说是微不足道的，但在 C 等命令式语言中可能需要大量工作。

Why does it seem like all functional languages are slower than C, and why do they always need garbage collection and excessive use of the heap?

函数式语言看起来会更慢，因为您只会看到比较容易用 C 编写好的代码的基准，而您永远不会看到比较函数式语言开始擅长的更繁重任务的基准。

但是，您已经正确地确定了当今函数式语言中可能存在的最大瓶颈:它们过高的分配率。干得好!

函数式语言分配如此之多的原因可以分为历史原因和内在原因。

从历史上看，50 年来，Lisp 实现已经做了很多拳击。这种特性传播到许多其他使用类似 Lisp 的中间表示的语言。多年来，语言实现者不断采用装箱法来快速解决语言实现中的复杂问题。在面向对象的语言中，默认情况下总是堆分配每个对象，即使它显然可以堆栈分配。然后将效率的负担推到垃圾收集器上，并投入了大量精力来构建垃圾收集器，这些垃圾收集器可以获得接近堆栈分配的性能，通常是通过使用凹凸分配的托儿所生成。我认为应该投入更多的精力来研究功能语言设计，以最大限度地减少针对不同需求进行优化的装箱和垃圾收集器设计。

分代垃圾收集器非常适合堆分配很多的语言，因为它们几乎可以和堆栈分配一样快。但它们在其他地方增加了大量的管理费用。今天的程序越来越多地使用像队列这样的数据结构(例如，用于并发编程)，这些为分代垃圾收集器提供了病态的行为。如果队列中的项目比第一代的存在时间长，那么它们都会被标记，然后它们都会被复制(“疏散”)，然后对其旧位置的所有引用都会更新，然后它们就有资格被收集。这比它需要的慢了大约 3 倍(例如与 C 相比)。像 Beltway (2002) 和 Immix (2008) 这样的标记区域收集器有可能解决这个问题，因为托儿所被替换为一个区域，该区域可以像托儿所一样被收集，或者如果它包含大部分可到达的值，它可以被另一个区域替换并留待老化，直到它包含大部分无法访问的值。

尽管 C++ 已经存在，但 Java 的创建者犯了一个错误，为泛型采用了类型删除，导致了不必要的装箱。例如，I benchmarked a simple hash table running 17× faster on .NET than the JVM 部分是因为 .NET 没有犯这个错误(它使用具体化的泛型)，还因为 .NET 有值类型。我实际上责怪 Lisp 使 Java 变慢。

所有现代函数式语言实现都继续过度装箱。 Clojure 和 Scala 等基于 JVM 的语言几乎没有选择，因为它们所针对的 VM 甚至无法表达值类型。 OCaml 在其编译过程的早期丢弃类型信息，并在运行时诉诸标记整数和装箱来处理多态性。因此，OCaml 经常会装箱单个浮点数并始终装箱元组。例如，OCaml 中的三元组字节由指向堆分配块的指针(其中嵌入了一个隐含的 1 位标记，在运行时反复检查)表示，该块具有 64 位 header 和 192 位主体，其中包含三个标记的 63 位整数(其中 3 个标记再次在运行时反复检查!)。这显然是疯狂的。

已经在函数式语言的拆箱优化方面做了一些工作，但它从未真正受到关注。例如，标准 ML 的 MLton 编译器是一个完整的程序优化编译器，可以进行复杂的拆箱优化。可悲的是，它早于它的时代和“长”编译时间(在现代机器上可能不到 1 秒!)阻止人们使用它。

打破这一趋势的唯一主要平台是 .NET，但令人惊讶的是，它似乎是一个意外。尽管 Dictionary 实现非常针对值类型的键和值(因为它们是未装箱的)进行了大量优化，但像 Eric Lippert 这样的 Microsoft 员工继续使用 claim that the important thing about value types is their pass-by-value semantics 而不是源于其未装箱的内部表示的性能特征。 Eric 似乎被证明是错误的:更多的 .NET 开发人员似乎更关心拆箱而不是传值。事实上，大多数结构是不可变的，因此，引用透明，因此值传递和引用传递之间没有语义差异。性能是可见的，结构可以提供大量的性能改进。结构体的性能甚至保存了 Stack Overflow 和结构体用于避免商业软件中的 GC 延迟，例如 Rapid Addition's !

函数式语言大量分配的另一个原因是固有的。像哈希表这样的命令式数据结构在内部使用巨大的单体数组。如果这些是持久的，那么每次更新时都需要复制巨大的内部数组。因此，像平衡二叉树这样的纯函数数据结构被分成许多堆分配的小块，以便于从一个版本的集合到下一个版本的重用。

当像字典这样的集合只在初始化期间写入然后从大量读取时，Clojure 使用一个巧妙的技巧来缓解这个问题。在这种情况下，初始化可以使用变异来构建“幕后”结构。但是，这对增量更新没有帮助，并且结果集合的读取速度仍然比它们的命令式等效项慢得多。从好的方面来说，纯函数式数据结构提供持久性，而命令式数据结构则没有。然而，很少有实际应用受益于实践中的持久性，因此这通常是不利的。因此，人们渴望使用不纯的函数式语言，您可以毫不费力地使用命令式风格并从中获益。

Does anyone know of a functional language appropriate for embedded / real-time applications, where memory allocation is kept to a minimum and the produced machine code is lean and fast?

如果您还没有，请查看 Erlang 和 OCaml。两者对于内存受限的系统都是合理的，但都不会生成特别好的机器代码。