加入Transients和Chunked Sequences的Clojure 1.1更加高效

作者 Werner Schuster 译者 杨晨 发布于 2009年12月27日

领域

架构 & 设计,

语言 & 开发

主题

动态语言 ,

架构 ,

Ruby ,

语言 ,

运行时 ,

Java ,

性能和可伸缩性 ,

编译器 ,

语言设计

标签

LISP ,

性能调优 ,

函数式编程 ,

Clojure ,

线程技术 ,

并发

Clojure 1.1 RC1已经发布——现在是介绍它的时候了，我们希望能够在最终版发布之前给出一些反馈。这些工作是在GitHub的Clojure 1.1分支上完成的，现在在Google Code上已经可以下载到Clojure 1.1 RC1的Binary Package了。

1.1的更新日志列出了和1.0的不同点，例如在1.1发布之前已经关闭的issue。同样也加入了一些新的特性来优化Clojure程序的性能。

Transients能够大幅改善构建持久数据结构的性能。持久数据结构是Clojure非常重要的元素，例如隐藏在Clojure的Vectors，Maps和Sets（参考Clojure创建者Rich Hickey关于持久数据结构的介绍）后面的细节和概念。简而言之，持久数据结构是非可变的；要删除或者修改数据的唯一办法就是复制一份此数据结构的副本。但是有一个小技巧：持久数据结构的内部结构以及它的性质（所有元素都是不可变的）允许共享所有的数据和大部分结构，因此创建一个拷贝只需要非常小的开销。

虽然复制副本的开销很小，但是也会有需要插入大量元素的情况出现。Transients也可以解决这种情况。简单来说，这种思想就是在大量修改之前将一个持久数据结构转换为一个transient；调用transient即可完成这个功能。同一数据结构的transient版提供了和持久版相同的存取函数，但是对于修改操作来说，这就需要使用后缀为“!”的不同函数了，例如conj!（而不是conj）。

理解持久数据结构和他们的transient版本的关系的一个好办法是看看java.lang.String和java.lang.StringBuilder之间的关系；一个是不可变的，当需要修改的时候它会创建一个新的副本，而另一个则允许直接在其上进行修改。

不过它们的相似性也就这些。但是，创建一个StringBuilder也就意味着拷贝String的内容，一个O（n）的操作。将持久数据结构转换为等价的transient版本的开销却非常小：只是一个O（1）的操作；它只是创建了一个transient的对象，这个对象包括了一个数据结构的根对象，然后还有一个表示其为transient的标记；不会有数据复制的行为。一旦数据结构的transient版本需要转换为持久版，同样也只需要O（1）的操作。

但是为什么有时候需要将持久版转回为transient版呢？难道不能无限制地使用transient吗？当然不能 - transient版本有一个非常重要的限制：它只能被一个线程使用。原因很简单：因为transient是可变的，在不同的线程中使用它将会非常危险的，所以需要同步。而持久数据结构使得在线程间共享数据结构变得非常简单；transient允许一个线程修改数据结构，然后通过将其转换为持久数据结构置为其他线程可访问。

Chunked Sequences是Clojure 1.1中的另外一个优化。快速预览可以看Rich Hickey关于chunked sequence演讲的幻灯片（PDF格式）。

chunked sequences背后的思想即是减少由于（lazy）sequences引入的开销。

Lazy sequences在Clojure中随处可见，它能够延迟某个任务直到必须要去做的时候。但是在某些情况下，有些任务根本不需要做，例如下列代码：

(take 10 (range 1 1000000000000) )

range创建了一个lazy sequence，这个lazy sequence会预生成好指定范围内的10个数。然后，take会请求10次sequence来获取生成的数。由于使用lazy方法，这只是请求了10个数而已，因为预处理，所以总共只需计算10个数。

实现使用了lazy-seq宏（在core.clj中），这样使得代码非常简洁。但是有一个问题：在lazy sequence中访问下一个元素可能会有一些数据管理上的开销。Chunked sequences即是为了减少这样的开销而生的，它将元素划分成多个块并且缓存值；块的大小是32，也就是说每一步的开销只是限定在32个元素之内。

另外一种优化chunked sequences的方法是对数据结构的内部组织结构的分析。例如，一个持久vector是以树的形式组织的，在这里面数据保存在32个元素数组中。为了访问一个元素，需要遍历这棵树来寻找到元素保存的数组。一个原生的sequence使用索引访问下一个元素，这样可能导致每次访问的时候都需要遍历树。chunked sequence的持久vector实现避免了这种情况：它找到sequence开始的存储有32个元素的数组，然后为每个元素快速建立一个简单索引；只有在32个元素都访问之后，才需要取下一个树节点并且开始遍历。

现在就只是看看chunked sequences的接受度如何了；它们显然有着很大的优点，但是Clojure 1.1更新日志指出：

chunked-seq的开销和其他sequence一样都是完全透明的。但是，注意有些sequence一次会处理超过32个元素。如果你依赖于完全惰性（full laziness），不希望学习如何生成任何零成本的结果，那么当然可能对你有影响。一个将开销限制在单个元素的chunked-seq的接口仍然在设计中，请将chunked sequence在实际应用中出现的问题或者行为差异反馈给我们。

当然Clojure 1.1还有更多特性仍待介绍，更多信息请参考Clojure 1.1更新日志。

如果需要更多关于Clojure的信息，请点击InfoQ的Clojure标签。强烈推荐Rich Hickey的演讲，例如持久性数据结构和已托管的引用。InfoQ同样也有在QCon London 2009上采访Rich Hickey的视频。

查看英文原文：Clojure 1.1 Adds Transients, Chunked Sequences for Efficiency

译者 杨晨 对数据库和搜索引擎有深入了解，尤其擅长经典计算机科学理论，对历史学兴趣浓厚。

• 更早的 >