为什么Clojure的core.reducers比懒惰的集合函数更快

Question

在Reducers的许多资源中(如Rich Hickey的规范博客文章),它声称减速器比常规集合函数((map ... (filter ...))等)更快,因为开销更少.

什么是避免的额外开销？IIUC即使是懒惰的集合函数也只能将原始序列移动一次.计算中间结果的细节有何不同？

在实施Clojure中有助于理解差异的相关位置的指针也将是最有帮助的

Answer 1

我认为一个关键的见解来自原始博客文章的以下段落：

(require '[clojure.core.reducers :as r])
(reduce + (r/filter even? (r/map inc [1 1 1 2])))
;=> 6

这应该看起来很熟悉 - 它是相同的命名函数，以相同的顺序应用，具有相同的参数，产生与 Clojure 的基于 seq 的 fns 相同的结果。不同之处在于，reduce 急切，而这些 reducer fns 不在 seq 游戏中，没有每步分配开销，因此速度更快。懒惰在你需要时很好，但当你不需要时，你就不必为此付出代价。

惰性序列的实现伴随着（线性）分配成本：每次实现惰性序列中的另一个元素时，序列的其余部分存储在新的 thunk 中，并且这种“thunk”的表示是一个新的clojure.lang.LazySeq对象。

我相信这些LazySeq对象是引用中提到的分配开销。使用reducer 没有惰性seq 元素的逐渐实现，因此根本没有LazySeqthunk 的实例化。

Answer 2

"请注意,没有产生中间集合."

这是改进,因为例如对垃圾收集器的压力较小.

当你组合这样的操作时map,filter那些函数会迭代一个集合并返回一个新的集合,然后传递给下一个函数.减速器不是这种情况.

所以它们可以用作那些函数(也就是说,它们以相同的方式组成)并且可以应用于相同的集合.但随着性能的提升.

下面是一个粗略的,完全不科学的地图/地图/过滤操作草图,有或没有减速器:

没有减速器

初始集合=> map =>中介集合=> map =>中介集合=> filter =>最终集合

没有reducer(即clojure.core map/filter函数),懒惰地生成中间集合.也就是说,仅在下一个处理步骤需要时产生新元素,一次一个元素或一个块.

注意:块是一个包含32个元素的块(尽管这应该被视为实现细节).出于效率原因,这是为了避免从一个计算"跳跃"到另一个计算.

例如,请参见map函数返回值:它返回a lazy-seq(换能器除外).

减速机

初始集合=> map/map/filter reducer =>最终集合

如果你需要快速处理整个系列,那么懒惰就会影响性能.删除惰性seq的中间层可提供性能提升.Reducers执行此操作并热切地处理集合,因此更快.您还可以保持相同的功能以简化切换.

另请阅读下面的评论,特别是来自@MichałMarczyk的评论