为什么函数式语言在基准测试中总是落后于 C？如果您有静态类型的函数式语言，在我看来，它可以编译为与 C 相同的代码，或者甚至更优化的代码，因为编译器可以使用更多语义。为什么看起来所有函数式语言都比 C 慢，为什么它们总是需要垃圾收集和过度使用堆？
有谁知道适用于嵌入式/实时应用程序的功能语言，其中内存分配保持在最低限度并且生成的机器代码精简且快速？
Steve
问问题
17324 次
10 回答
71
函数式语言天生就慢吗？
从某种意义上说，是的。他们需要的基础设施不可避免地增加了理论上可以使用手工汇编程序实现的开销。特别是，一流的词法闭包只适用于垃圾收集，因为它们允许值超出范围。
为什么函数式语言在基准测试中总是落后于 C？
首先，谨防选择偏差。C 作为基准套件中的最低公分母，限制了可以完成的工作。如果你有一个比较 C 和函数式语言的基准，那么它几乎可以肯定是一个非常简单的程序。可以说如此简单，以至于在今天几乎没有实际意义。仅使用 C 作为基准来解决更复杂的问题实际上是不可行的。
最明显的例子是并行性。今天，我们都有多核。甚至我的手机也是多核的。众所周知，多核并行在 C 语言中很困难，但在函数式语言中却很容易（我喜欢 F#）。其他示例包括任何受益于持久数据结构的东西，例如，撤消缓冲区对于纯函数式数据结构来说是微不足道的，但在 C 等命令式语言中可能是大量工作。
为什么看起来所有函数式语言都比 C 慢，为什么它们总是需要垃圾收集和过度使用堆？
函数式语言看起来会更慢，因为你只会看到比较容易用 C 编写好的代码的基准测试，而你永远不会看到比较函数式语言开始表现出色的更复杂任务的基准测试。
但是，您已经正确地确定了当今函数式语言的最大瓶颈可能是什么：它们的分配率过高。干得好！
函数式语言分配如此繁重的原因可以分为历史原因和固有原因。
从历史上看，Lisp 实现已经做了很多拳击50年了。这种特性传播到许多其他使用类似 Lisp 的中间表示的语言。多年来，语言实施者一直在使用拳击作为解决语言实施复杂性的快速解决方案。在面向对象的语言中，默认设置总是堆分配每个对象，即使它显然可以被堆栈分配。然后效率的负担被推到了垃圾收集器上，并且已经投入了大量精力来构建垃圾收集器，这些垃圾收集器可以达到接近堆栈分配的性能，通常是通过使用凹凸分配的 Nursery 生成。我认为应该投入更多的精力来研究功能语言设计，以最大限度地减少装箱和垃圾收集器设计，这些设计针对不同的需求进行了优化。
分代垃圾收集器非常适合堆分配很多的语言，因为它们几乎可以与堆栈分配一样快。但它们在其他地方增加了大量的间接费用。今天的程序越来越多地使用队列之类的数据结构（例如，用于并发编程），这些数据结构给分代垃圾收集器带来了病态的行为。如果队列中的项目超过第一代，那么它们都被标记，然后它们都被复制（“撤离”），然后对其旧位置的所有引用都得到更新，然后它们就有资格被收集。这比它需要的速度慢了大约 3 倍（例如，与 C 相比）。标记区域收集器，例如Beltway (2002) 和Immix（2008）有可能解决这个问题，因为托儿所被一个可以像托儿所一样被收集的区域所取代，或者，如果它包含大部分可到达的值，它可以被另一个区域取代，并一直老化直到它包含大部分无法访问的值。
尽管 C++ 已经存在，Java 的创建者还是犯了对泛型采用类型擦除的错误，导致不必要的装箱。例如，我对一个简单的哈希表进行了基准测试，它在 .NET 上的运行速度比 JVM 快 17 倍，部分原因是 .NET 没有犯这个错误（它使用了具体化的泛型），也因为 .NET 具有值类型。我实际上责怪 Lisp 让 Java 变慢了。
所有现代函数式语言实现都继续过度装箱。Clojure 和 Scala 等基于 JVM 的语言几乎没有选择余地，因为它们所针对的 VM 甚至无法表达值类型。OCaml 在其编译过程的早期就丢弃类型信息，并在运行时使用标记整数和装箱来处理多态性。因此，OCaml 经常将单个浮点数装箱并且总是将元组装箱。例如，OCaml 中的三个字节由一个指针（其中嵌入一个隐式 1 位标记，在运行时重复检查）表示，该指针指向一个具有 64 位标头和 192 位主体的堆分配块，其中包含三个标记的 63 位整数（其中 3 个标记再次在运行时重复检查！）。这显然是疯了。
在函数式语言的拆箱优化方面已经做了一些工作，但从未真正获得关注。例如，标准 ML 的 MLton 编译器是一个全程序优化编译器，它进行了复杂的拆箱优化。可悲的是，它早于它的时代，而且“长”的编译时间（在现代机器上可能不到 1 秒！）阻止了人们使用它。
打破这一趋势的唯一主要平台是 .NET，但令人惊讶的是，这似乎是个意外。尽管Dictionary对值类型的键和值进行了非常优化的实现（因为它们是未装箱的），但像 Eric Lippert 这样的微软员工继续声称值类型的重要之处在于它们的按值传递语义而不是源自其未装箱的内部表示的性能特征。Eric 似乎被证明是错误的：更多的 .NET 开发人员似乎更关心拆箱而不是按值传递。实际上，大多数结构是不可变的，因此是引用透明的，因此按值传递和按引用传递之间没有语义差异。性能是可见的，结构可以提供巨大的性能改进。结构的性能甚至节省了堆栈溢出，结构用于避免商业软件中的 GC 延迟，如 Rapid Addition！
函数式语言大量分配的另一个原因是固有的。像哈希表这样的命令式数据结构在内部使用巨大的整体数组。如果这些是持久的，那么每次进行更新时都需要复制巨大的内部数组。因此，像平衡二叉树这样的纯功能数据结构被分割成许多小的堆分配块，以便于从一个版本的集合到下一个版本的重用。
当像字典这样的集合只在初始化期间写入，然后从很多地方读取时，Clojure 使用了一个巧妙的技巧来缓解这个问题。在这种情况下，初始化可以使用变异来构建“幕后”结构。但是，这对增量更新没有帮助，并且生成的集合仍然比它们的命令式等价物读起来慢得多。从好的方面来说，纯函数式数据结构提供持久性，而命令式数据结构则没有。然而，很少有实际应用程序从实践中的持久性中受益，因此这通常不是有利的。因此，对不纯函数式语言的渴望，你可以毫不费力地使用命令式风格并从中获益。
有谁知道适用于嵌入式/实时应用程序的功能语言，其中内存分配保持在最低限度并且生成的机器代码精简且快速？
如果您还没有，请看一下 Erlang 和 OCaml。两者对于内存受限的系统都是合理的，但都不会生成特别好的机器代码。
于 2012-06-05T17:07:54.517 回答
17
没有什么是天生的。这是一个示例，其中解释的OCaml 比等效的 C 代码运行得更快，因为由于语言的差异，OCaml 优化器具有不同的可用信息。当然，笼统地声称 OCaml 绝对比 C 快是愚蠢的。关键是，这取决于你在做什么，以及你是如何做的。
于 2009-02-05T15:37:31.573 回答
13
函数式语言需要消除在语言抽象级别可见的可变状态。因此，需要复制将通过命令式语言就地突变的数据，而突变发生在副本上。举个简单的例子，请参阅 Haskell 与 C 中的快速排序。
此外，垃圾收集是必需的，因为free()它不是纯函数，因为它有副作用。因此，在语言抽象级别释放内存且不涉及副作用的唯一方法是垃圾收集。
当然，原则上，足够智能的编译器可以优化大部分复制。这已经在某种程度上完成了，但是让编译器足够聪明以理解你的代码在那个级别的语义是很困难的。
于 2009-02-05T15:21:25.787 回答
8
过程语言的控制流更好地匹配现代计算机的实际处理模式。
C 非常紧密地映射到其编译产生的汇编代码，因此有“跨平台汇编”的绰号。计算机制造商花了几十年的时间使汇编代码尽可能快地运行，因此 C 继承了所有这些原始速度。
相比之下，函数式语言的无副作用、固有的并行性根本不能很好地映射到单个处理器上。调用函数的任意顺序需要序列化到 CPU 瓶颈：如果没有非常聪明的编译，你将一直在进行上下文切换，任何预取都不会起作用，因为你一直在跳跃到处都是，...基本上，计算机制造商为漂亮的、可预测的过程语言所做的所有优化工作都毫无用处。
然而！随着转向许多功能较弱的内核（而不是一两个涡轮增压内核），函数式语言应该开始缩小差距，因为它们自然地水平扩展。
于 2009-02-05T15:27:23.123 回答
8
C 速度很快，因为它基本上是一组用于汇编程序的宏 :) 当您在 C 中编写程序时，没有“幕后”。当您决定是时候分配内存并以同样的方式释放时，您会分配内存。当您编写实时应用程序时，这是一个巨大的优势，其中可预测性很重要（实际上比其他任何事情都重要）。
Also, C compilers are generally extremly fast because language itself is simple. It even doesn't make any type checkings :) This also means that is easier to make hard to find errors. Ad advantage with the lack of type checking is that a function name can just be exported with its name for example and this makes C code easy to link with other language's code
于 2009-02-05T15:29:15.117 回答
7
简短的回答：因为 C 很快。就像，快得惊人的疯狂。一种语言根本不必“慢”就可以让 C 把它交给它。
C 语言之所以快，是因为它是由真正伟大的程序员创建的，而 gcc 已经在数十年的时间里进行了优化，并且比 99% 的语言都多出数十名优秀的程序员。
简而言之，除了需要非常特定的函数式编程结构的特殊任务之外，您不会击败 C。
于 2009-02-05T15:20:53.883 回答
5
好吧，Haskell 仅比 GCC 的 C++ 慢 1.8 倍，后者在典型的基准测试任务中比 GCC 的 C 实现要快。这使得 Haskell 非常快，甚至比 C#（即 Mono）还要快。
相对语言速度
- 1.0 C++ GNU g++
- 1.1 C GNU gcc
- 1.2 ATS
- 1.5 Java 6-服务器
- 1.5 清洁
- 1.6 帕斯卡 自由帕斯卡
- 1.6 Fortran 英特尔
- 1.8 Haskell GHC
- 2.0 C# 单声道
- 2.1 斯卡拉
- 2.2 艾达 2005 GNAT
- 2.4 Lisp SBCL
- 3.9 Lua LuaJIT
作为记录，我在 iPhone 上使用 Lua 进行游戏，因此如果您愿意，您可以轻松使用 Haskell 或 Lisp，因为它们更快。
于 2009-02-05T15:53:40.573 回答
4
就目前而言，函数式语言并没有大量用于行业项目，因此没有足够认真的工作投入到优化器中。此外，为命令式目标优化命令式代码可能更容易。
函数式语言有一项壮举可以让它们现在很快超越命令式语言：微不足道的并行化。
微不足道不是因为它很容易，而是它可以内置到语言环境中，而开发人员不需要考虑它。
对于许多项目来说，使用与线程无关的语言（如 C）中强大的多线程的成本是令人望而却步的。
于 2009-02-05T15:21:10.980 回答
3
我不同意tuinstoel。重要的问题是，当函数式语言用于本应使用的函数式语言时，它是否能提供更快的开发时间并产生更快的代码。请参阅Wikipedia 上的效率问题部分，了解我的意思。
于 2009-02-05T15:25:59.863 回答
1
更大的可执行文件大小的另一个原因可能是惰性评估和非严格性。编译器无法在编译时确定某些表达式何时被评估，因此一些运行时被填充到可执行文件中来处理这个（调用所谓的thunks的评估）。至于性能，懒惰既好也坏。一方面它允许额外的潜在优化，另一方面代码大小可以更大，程序员更有可能做出错误的决定，例如参见 Haskell 的foldl vs. foldr vs. foldl' vs. foldr'。
于 2009-02-05T15:31:37.340 回答