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

  • Werner Schuster
  • 杨晨

2009 年 12 月 27 日

话题:JavaRuby编程语言函数式编程架构性能调优语言 & 开发

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

JavaRuby编程语言函数式编程架构性能调优语言 & 开发