编译-功能语言天生就慢吗?

为什么功能语言在基准测试中总是落后于C? 如果您使用的是静态类型的功能语言,在我看来,它可以编译为与C相同的代码,甚至可以编译为更优化的代码,因为编译器可以使用更多的语义。 为什么似乎所有功能语言都比C慢,为什么它们总是需要垃圾回收和过多使用堆?

是否有人知道适合嵌入式/实时应用程序的功能语言,在这种语言中,内存分配保持在最低水平,并且生成的机器代码精简而快速?

asked 2020-08-08T18:07:04Z
10个解决方案
62 votes

函数语言天生就慢吗?

从某种意义上说是的。 他们需要的基础设施不可避免地会增加理论上手工组装所需的开销。 特别地,一类词汇闭包仅适用于垃圾回收,因为它们允许值在范围内进行。

为什么功能语言在基准测试中总是落后于C?

首先,提防选择偏见。 C作为基准套件中的最低公分母,限制了可以完成的工作。 如果您有将C与功能语言进行比较的基准,那么几乎可以肯定这是一个非常简单的程序。 可以说如此简单,以至于今天它几乎没有实际意义。 仅使用C来解决更复杂的问题在实践中是不可行的。

最明显的例子就是并行性。 今天,我们都有多核。 甚至我的手机都是多核的。 在C语言中,多核并行性非常困难,但在函数式语言中(我喜欢F#)则容易。 其他示例包括从持久性数据结构中受益的任何内容,例如 undo缓冲区对于纯功能数据结构来说是微不足道的,但是在诸如C这样的命令性语言中可能需要做大量工作。

为什么似乎所有功能语言都比C慢,为什么它们总是需要垃圾回收和过多使用堆?

函数式语言的运行速度似乎会变慢,因为您只会看到基准测试比较易于用C语言编写的代码,而您将永远不会看到基准测试比较功能强大的代码,而这些任务在函数式语言开始表现出色之后就开始了。

但是,您已经正确地确定了当今功能语言中最大的瓶颈可能是:过度的分配率。 干得好!

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

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

分代垃圾收集器对于堆分配很多的语言非常有用,因为它们几乎可以像堆栈分配一样快。 但是它们增加了其他地方的大量开销。 当今的程序越来越多地使用诸如队列之类的数据结构(例如用于并发编程),这些结构为代际垃圾收集器提供了病理行为。 如果队列中的项目在第一代中已经过期,则它们都将被标记,然后都将被复制(“撤离”),然后所有对其旧位置的引用都会更新,然后才有资格进行收集。 这比所需的速度慢大约3倍(例如,与C相比)。 诸如Beltway(2002)和Immix(2008)之类的马克地区收藏家具有解决这一问题的潜力,因为苗圃被一个可以被当作苗圃收集的区域所代替,或者如果它包含大部分可达到的价值,它可以 被另一个区域替换并老化,直到它包含大部分无法访问的值。

尽管C ++早已存在,但Java的创建者犯了一个错误,即对泛型采用类型擦除,从而导致不必要的装箱。 例如,我对一个简单的哈希表进行了基准测试,该哈希表在.NET上比JVM快17倍,部分原因是.NET不会犯此错误(它使用统一的泛型),也因为.NET具有值类型。 我实际上归咎于Lisp使Java变慢。

所有现代功能语言的实现都继续过度包装。 Clojure和Scala等基于JVM的语言几乎没有选择余地,因为它们所针对的VM甚至无法表达值类型。 OCaml在其编译过程的早期就释放类型信息,并在运行时求助于带标记的整数和装箱来处理多态性。 因此,OCaml经常会装箱单个浮点数,并总是装箱元组。 例如,OCaml中的三字节字节由指向具有64位标头和192位正文(包含 三个标记的63位整数(在运行时再次检查3个标记!)。 这显然是疯了。

在功能语言中对取消装箱优化进行了一些工作,但从未真正引起人们的注意。 例如,用于标准ML的MLton编译器是一个进行了复杂的拆箱优化的全程序优化编译器。 令人遗憾的是,这是在它的时代之前,“漫长的”编译时间(在现代机器上可能不到1秒!)阻止了人们使用它。

打破这一趋势的唯一主要平台是.NET,但令人惊讶的是,这似乎是偶然的。 尽管有一个Dictionary实现非常针对值类型的键和值进行了优化(因为它们是未装箱的),但像Eric Lippert这样的Microsoft员工仍然声称值类型的重要之处在于它们的按值传递语义而不是性能 源于其未装箱的内部表示形式的特征。 埃里克(Eric)似乎已经被证明是错误的:更多的.NET开发人员似乎更关心拆箱而不是按值传递。 实际上,大多数结构都是不可变的,因此是参照透明的,因此按值传递和按引用传递之间没有语义差异。 性能是可见的,并且结构可以提供大量的性能改进。 结构的性能甚至保存了堆栈溢出,并且这些结构用于避免诸如Rapid Addition的商业软件中的GC延迟!

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

当字典之类的集合仅在初始化期间写入然后从大量读取时,Clojure使用巧妙的技巧来缓解此问题。 在这种情况下,初始化可以使用变异来构建“幕后”结构。 但是,这对增量更新无济于事,并且所生成的集合仍比其命令等效项慢得多。 从好的方面来说,纯功能数据结构提供了持久性,而命令性数据结构则没有。 但是,很少有实际应用会从实践中受益,因此这通常是不利的。 因此,人们希望使用不纯净的功能语言,在这种语言中,您可以毫不费力地降至祈使风格并从中受益。

是否有人知道适合嵌入式/实时应用程序的功能语言,在这种语言中,内存分配保持在最低水平,并且生成的机器代码精简而快速?

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

Jon Harrop answered 2020-08-08T18:08:41Z
18 votes

天生就没有东西。 这是一个示例,其中解释的OCaml比等效的C代码运行得更快,因为OCaml优化器由于语言的不同而具有不同的可用信息。 当然,笼统地说OCaml绝对比C快是愚蠢的。关键是,这取决于您在做什么以及如何做。

也就是说,OCaml是一种(主要是)功能语言的示例,与纯净度相比,它实际上是为性能而设计的。

Craig Stuntz answered 2020-08-08T18:09:06Z
11 votes

功能语言要求消除在语言抽象级别可见的可变状态。 因此,需要使用命令式语言进行原位变异的数据需要复制,而变异发生在副本上。 对于一个简单的示例,请参见Haskell vs. C中的快速排序。

此外,由于free()不是纯函数,因为它具有副作用,因此需要进行垃圾回收。 因此,在语言抽象级别释放不涉及副作用的唯一内存的方法是使用垃圾回收。

当然,原则上,足够聪明的编译器可以优化大部分复制。 已经在某种程度上做到了这一点,但是要使编译器足够智能以在该级别理解您代码的语义是很困难的。

dsimcha answered 2020-08-08T18:09:36Z
9 votes

C的速度很快,因为它基本上是汇编程序的一组宏:)用C编写程序时,没有“幕后花絮”。当您决定要这样做并以相同的方式释放时,就分配内存。 当您编写实时应用程序时,这是一个巨大的优势,其中可预测性很重要(实际上比其他任何事情都重要)。

而且,由于语言本身很简单,因此C编译器通常速度极快。 它甚至不进行任何类型检查:)这也意味着更容易发现错误。缺乏类型检查的广告优势在于,例如,函数名称只能使用其名称导出,这使得C代码易于与其他语言的代码链接

Emiliano answered 2020-08-08T18:10:02Z
8 votes

简短的答案:因为C很快。 就像在疯狂地快疯了一样。 语言完全不必为了使其C被后方掌握而“变慢”。

C如此之快的原因是它是由非常出色的编码人员创建的,并且gcc在经过几十年的发展过程中得到了优化,并且数十种出色的编码人员对它们进行了优化,而目前尚不到99%的语言。

简而言之,除了需要非常特定的功能编程构造的特殊任务之外,您不会击败C。

Jens Roland answered 2020-08-08T18:10:31Z
6 votes

程序语言的控制流更好地匹配了现代计算机的实际处理模式。

C非常紧密地映射到其编译产生的汇编代码,因此被称为“跨平台汇编”。 计算机制造商花了几十年的时间使汇编代码尽可能快地运行,因此C继承了所有这些原始速度。

相比之下,功能语言的无副作用,固有的并行性根本不会映射到单个处理器上。 需要将调用函数的任意顺序序列化为CPU瓶颈:如果没有非常聪明的编译,您将一直在上下文切换中使用,因为您不断地跳转,所以任何预取都不会起作用 基本上,...计算机制造商针对好的,可预测的过程语言所做的所有优化工作几乎没有用。

然而! 随着向功能更弱的内核(而不是一两个涡轮增压内核)的发展,功能语言应该开始缩小差距,因为它们自然会水平扩展。

James Brady answered 2020-08-08T18:11:06Z
5 votes

就目前而言,功能语言在工业项目中并未得到广泛使用,因此优化器中没有足够认真的工作。 同样,为命令目标优化命令代码可能更容易。

函数式语言有一项壮举,使它们现在真的很快就会超越命令式语言:琐碎的并行化。

轻而易举的意义并不是轻而易举,而是可以将其内置到语言环境中,而无需开发人员考虑。

对于许多项目而言,使用与线程无关的语言(如C)来实现健壮的多线程的成本是令人望而却步的。

peterchen answered 2020-08-08T18:11:40Z
4 votes

Haskell井仅比GCC的C ++慢1.8倍,后者比典型基准任务的GCC的C实现快。这使得Haskell非常快,甚至比C#(即Mono)还要快。

相对语言速度

  • 1.0 C ++ GNU g ++
  • 1.1 C GNU gcc
  • 1.2空中交通服务
  • 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 for Games,因此您可以根据需要轻松使用Haskell或Lisp,因为它们更快。

Robert Gould answered 2020-08-08T18:13:09Z
2 votes

我不同意tuinstoel。 一个重要的问题是,当功能语言习惯于使用什么功能语言时,它是否会提供更快的开发时间并导致更快的代码。 请参阅Wikipedia上的效率问题部分,以了解我的意思。

Szymon Rozga answered 2020-08-08T18:13:30Z
1 votes

更大的可执行文件大小的另一个原因可能是懒惰的评估和不严格。 当某些表达式被求值时,编译器无法在编译时弄清楚,因此某些运行时会塞入可执行文件中以进行处理(以调用所谓的thunk求值)。 至于性能,懒惰既有好有坏。 一方面,它允许进行其他潜在的优化,另一方面,代码大小可能更大,并且程序员更有可能做出错误的决定,例如 请参阅Haskell的fold vs.foldr vs.foldl'vs.foldr'。

Eduard - Gabriel Munteanu answered 2020-08-08T18:13:50Z
translate from https://stackoverflow.com:/questions/516301/are-functional-languages-inherently-slow