函数式编程语言天生就慢吗？

摘要：近期，函数式编程得到了越来越多的关注，Lisp不仅重获青春还涌现出了一批新函数式编程语言。因此开发者们对函数式编程语言的运行快慢各抒己见，展开激烈讨论。本文将和大家一起讨论，函数式编程语言真的就慢吗？

由于函数式语言需要基础架构支持，这样不可避免地增加了学习汇编理论知识的成本。一流的词法闭包只有在配合垃圾回收时才能良好地工作，因为它允许值越界。

函数式语言：过度分配

请注意自己的选择。C在基准套件中扮演最小公分母，限制是可以实现的。如果在比较C语言与函数式编程语言上有一个基准，那么它肯定是一个非常简单的程序。按理说这么简单，它是没有什么实际意义的。仅仅把C作为基准的话，那么在解决更复杂的问题上，它是没有什么实际可行的解决方案。

这方面最明显的例子就是并行性。如今，多核已成为一种主流，甚至连我的手机也是多核的。在C语言中，要想实现多核并行是相当困难的，但是在函数式编程语言中会却容易实现（我比较喜欢F#）。其它例子还包括持久化数据结构，例如撤消缓冲区与纯函数数据结构是微不足道的，但在命令式语言上，这却是个非常大的工作量。

函数式语言看起来比C语言要慢，因为你仅看到基准代码在C语言里很容易去编写并且你永远不会明白基准比任务更耐人寻味，从函数式语言到Excel。然而，目前你已经能正确的识别出函数式语言的最大瓶颈是什么：过度的分配率。为什么函数式语言分配会如此严重的原因就是它被拆分成历史和内在的。

从历史上看，Lisp实现已经做了50年的装箱工作。这个特点也渗透到许多其它编程语言中，类似Lisp的中间件表示。这些年来，语言实现不断地采取装箱这种方式快速实现并发。在面向对象语言中，默认堆分配每个对象，即使明显可以采用堆栈分配。提高效率的负担是推到垃圾收集器并且在建设垃圾收集器性能上做一些努力，使它能够达到或者最大可能接近堆栈分配，通常是使用bump-allocating托管实现。我认为，应该投入更多的精力来研究函数语言设计，减少装箱和垃圾收集器设计，从而优化不同的需求。

分代式垃圾收集器

分代式垃圾收集器对语言来说，是很棒的，因为堆可以分配很多并且他们的速度也和堆栈分配差不多一样快，但是会增加其他地方的开销。如今的程序越来越多地使用像队列似地的数据结构（例如并发编程）并且让分代式垃圾收集产生一些病态行为。如果队列中的某项活得比第一代长，那么它们都会被做标记，然后所有引用的旧位置将会得到更新并且被收藏。这个大概要比它们需要的慢3倍（例如比C语言）。标记区域的收集器有可能解决这个问题，像Belway（2002）和Lmmix（2008），因为托管已经被替换成一个区域，可以被收集，就好像是一个托管所，如果它包含大部分可及值，可以被另一个区域替换并且留下时间，直到它包含一些遥不可及的值。

尽管已经存在的C++，还有Java的发明人采用泛型来消除这些错误，但这些都导致了不必要的装箱。例如，我构建一个简单的哈希表，在.NET上面的速度比JVM要快17倍。原因就是.NET并没有犯这个错误（它采用具体化泛型）并且.NET还有值类型。实际上，我认为是Lisp让Java变慢。

装箱、拆箱

所有现代式的函数式语言都是过分依赖装箱。基于JVM语言，像Clojure和Scala别无选择，因为VM甚至不能表达值类型。Ocaml（Objective Caml）在早期就揭示了类型信息，在它的编译过程和经常使用整数类型进行装箱标记并且在运行时去处理多态性。因此，Ocaml常常作为私有浮点数字被装入箱中并且一直是盒元组。在Ocaml中一个三重的字节就是一个由指针（有一个隐藏的标签嵌入在里面并且在运行时会被反复检查）和一个64位的堆上分配块头与192位的主体包含三个标记的63字节整数（3个标签，在运行时会被反复检查）。这显然是疯了。

在函数式语言上，有关拆箱优化工作已经完成但它并未真正获得牵引力。例如Mlton编译器对于ML标准来说，是一个全程序优化编译器并且很擅长拆箱优化工作。不幸的是，在运行时间之前和“长”编译时间（在现代机器上低于1秒）阻止人们使用它。

唯一的主要平台已经打破了这个趋势，但令人惊讶的是.NET却是个例外。尽管有一个Dictionary类可以高度优化键和值。微软的员工，比如Eric Lippert就继续强调值类型是根据值进行传递的，这一点很重要并且性能特点不是来源于它们内部拆箱特征。Eric的理解似乎已经被证明是错误的：越来越多的.NET程序员青睐拆箱而不是值传递。事实上，大多数结构是不可变的，因此，引用透明在值传递和引用传递之间并没有什么语义差别。性能是可见的并且结构可以提供大量的性能改进。性能结构甚至可以保存堆栈溢出并且结构常常用来避免GC延迟在商业软件上面，比如Rapid Addition's。

函数式与命令式

重分配的函数式语言的另一个原因是与生俱来的。命令式数据结构像哈希表结构使用内在巨大的整体数组。如果这些巨大的内部数组一直持续使用，将需要不断复制和更新。所以纯函数式数据结构比如平衡二叉树分裂成许多小堆，分裂成块为了便于从一个版本集合到另一个版本。

Clojure采用了一个非常巧妙的花招来解决这个问题，当集合例如dictionaries在初始化时被写，然后进行读取。在这个例子中，初始化可以使用突变来建立“幕后”结构。然而，这并不会有助于增量更新并且由此产生的集合在读取数据方面仍然比较命令式等价物慢。当然纯函数式语言在数据持久化方面明显要比命令式强。然后，很少的实际应用程序受益于持久化实践，所以这并不算是什么优势。因此，把非纯函数式语言降到命令式风格，这样就可以毫不费力的从总受益。