BT

你的观点很重要! 快来参与InfoQ调研吧!

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

| 作者 Werner Schuster 关注 4 他的粉丝 ,译者 杨晨 关注 0 他的粉丝 发布于 2009年12月27日. 估计阅读时间: 7 分钟 | ArchSummit社交架构图谱:Facebook、Snapchat、Tumblr等背后的核心技术

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

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT