为惰性序列实现更快的reduce

Question

从向量/分块序列构建的惰性序列有时会进行慢速的首次/下一次reduce。

观察

`
(def xs (vec (range 3000000)))

(time (reduce max xs)) ;; #1: 130ms, (参考)
(time (reduce max (lazy-cat xs))) ;; #2: 130ms，同样快
(time (reduce max 0 (lazy-cat xs))) ;; #3: 500ms，慢4倍！！

;; 双倍concate后，不是慢2倍而是慢10倍
(time (reduce max (lazy-cat xs xs))) ;; #4: 1200ms
(time (reduce max 0 (lazy-cat xs xs))) ;; #5: 1200ms
`

对#3的解释：问题在于，当{{seq-reduce}}在没有{{init}}时被调用，它将正确地再次调用{{reduce}}并采取快速路径。但给定{{init}}，它将永远不会逃离到更快的reduce，而会坚持首次/下一次。

注意：在Clojure中，它们“适当”地缩放（前三个大约是45ms，后两个大约是110ms）。

原因是Clojure正确地逃离到快速路径

https://github.com/clojure/clojure/blob/2b242f943b9a74e753b7ee1b951a8699966ea560/src/clj/clojure/core/protocols.clj#L131-L143

这是一个RFC，因为我不是100%确信实现。需要小心不要在这里崩溃...

问题
1. 应该ChunkedCons实现IReduce？我认为是的。

Answer 1

留言者：aralo

高级编译的计时

`
CHROME
"旧版 "
#1: "Elapsed time: 21.870000 msecs"
#2: "Elapsed time: 25.485000 msecs"
#3: "Elapsed time: 134.900000 msecs"
#4: "Elapsed time: 317.155000 msecs"
#5: "Elapsed time: 313.225000 msecs"
"新版 "
#1: "Elapsed time: 23.290000 msecs"
#2: "Elapsed time: 19.445000 msecs"
#3: "Elapsed time: 20.075000 msecs"
#4: "Elapsed time: 102.895000 msecs"
#5: "Elapsed time: 100.430000 msecs"
"旧版 "
#1: "Elapsed time: 19.585000 msecs"
#2: "Elapsed time: 19.475000 msecs"
#3: "Elapsed time: 87.805000 msecs"
#4: "Elapsed time: 303.340000 msecs"
#5: "Elapsed time: 291.680000 msecs"
"新版 "
#1: "Elapsed time: 20.760000 msecs"
#2: "Elapsed time: 19.690000 msecs"
#3: "Elapsed time: 18.960000 msecs"
“已过时间：101.385000 毫秒”
“已过时间：101.290000 毫秒”

Firefox

"旧版 "
“#1：已过时间：7.880000 毫秒”
“#2：已过时间：7.820000 毫秒”
“#3：已过时间：69.460000 毫秒”
“#4：已过时间：197.800000 毫秒”
“#5：已过时间：209.300000 毫秒”
"新版 "
“#1：已过时间：7.380000 毫秒”
“#2：已过时间：7.360000 毫秒”
“#3：已过时间：8.100000 毫秒”
“#4：已过时间：110.640000 毫秒”
“#5：已过时间：89.960000 毫秒”
"旧版 "
“#1：已过时间：6.520000 毫秒”
“#2：已过时间：7.360000 毫秒”
“#3：已过时间：106.920000 毫秒”
“#4：已过时间：252.300000 毫秒”
“#5：已过时间：249.800000 毫秒”
"新版 "
“#1：已过时间：7.360000 毫秒”
“#2：已过时间：6.940000 毫秒”
“#3：已过时间：6.880000 毫秒”
“#4：已过时间：99.380000 毫秒”
“#5：已过时间：53.220000 毫秒”

`

Answer 2

留言者：aralo

这对真正（未分块）的lazy-seqs的影响可以忽略不计（由于垃圾回收引起的大量波动，难以衡量）。

Answer 3

留言者：aralo

为ChunkedCons的reduce创建新工单：CLJS-2468

Answer 4

留言者：aralo

依赖于CLJS-2469才能通过测试。补丁已附上。

Answer 5

评论者：tmulvaney

ChunkedSeq已经实现了一个高效的reduce策略。我认为问题在于LazySeq，它只是一个可能包含不同类型seq的容器，总是对该内部序列调用seq-reduce。有时，例如在ChunkedSeq的情况下，内部序列实际上知道如何最优为自己进行reduce。

所以我认为解决方案就是简单地改变LazySeq.IReduce.-reduce的主体，从：{{(seq-reduce f init coll)}}变为{{(reduce f init (seq coll)}}。关键在于调用seq时，如果存在，会提取内部seq，然后reducer会调用针对它的最佳路径。

希望这有帮助。

Answer 6

留言者：aralo

我认为这不是一个好主意。使用这种方法很容易堆栈溢出。尽管如此，我还没有试过。

Answer 7

_评论由：tmulvaney_发表

有一点值得考虑，该补丁改进了一个特定的案例，ChunkedSeqs。哈希映射的序列、索引序列、范围序列等没有被处理。将调度到 {{reduce}} 会解决这个问题。你可能会对压栈问题有看法，但我还没有进行实验。

例如，{{(reduce + (range 10000))}} 比 {{(reduce + (lazy-cat (range 10000)))}} 要快得多，但是使 LazySeq 的 reduce 调用作用于内部集合应该能解决这个问题。

Answer 8

留言者：aralo

托马斯，很高兴相互交流想法。请随意比较你的想法和我的补丁的性能指标。在内部 fn 上调用 reduce 的一个问题在于堆栈和使用非保留的 reduce。并且包装减少函数相当昂贵。我试过了，速度要慢得多。我想那样做的原因是它要慢得多。但再次强调，必须 非常 小心地不要压栈。这将用户的一个大问题。

Answer 9

参考：https://clojure.atlassian.net/browse/CLJS-2466 （由 aralo 报告）