对于 lazy-seqs 的更快 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 倍！！

;; 使用 concat 两倍，但它们不是慢两倍，而是慢 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，因为我不完全确定实施情况。需要小心不要在这里耗尽堆栈...

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

Answer 1

评论由：aralo

高级编译的计时

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

FIREFOX

"旧版"
1: "已用时间：7.880000 msecs"
2: "已用时间：7.820000 msecs"
3: "已用时间：69.460000 msecs"
4: "已用时间：197.800000 msecs"
5: "已用时间：209.300000 msecs"
"新版"
1: "已用时间：7.380000 msecs"
2: "已用时间：7.360000 msecs"
3: "已用时间：8.100000 msecs"
4: "已用时间：110.640000 msecs"
5: "已用时间：89.960000 msecs"
"旧版"
1: "已用时间：6.520000 msecs"
2: "已用时间：7.360000 msecs"
3: "已用时间：106.920000 msecs"
4: "已用时间：252.300000 msecs"
5: "已用时间：249.800000 msecs"
"新版"
1: "已用时间：7.360000 msecs"
2: "已用时间：6.940000 msecs"
3: "已用时间：6.880000 msecs"
4: "已用时间：99.380000 msecs"
5: "已用时间：53.220000 msecs"

`

Answer 2

评论由：aralo

对实际（未分块）的 lazy-seqs 的影响很小（由于垃圾回收造成的大量变化，难以衡量）。

Answer 3

评论由：aralo

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

Answer 4

评论由：aralo

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

Answer 5

评论者：tmulvaney

ChunkedSeq 已经实现了高效的 reduce 策略。我相信问题在于 LazySeq，它只是一个可能包含不同类型序列的容器，它总是会调用内部的 seq-reduce。有时，例如在 ChunkedSeq 的情况下，内部序列确实知道如何最好地缩减自身。

因此，我认为解决方案就像更改 LazySeq.IReduce.-reduce 的主体一样简单：将从：{{(seq-reduce f init coll)}} 更改为 {{(reduce f init (seq coll)}}。这里的关键在于调用 seq 会 извлечь 内部序列（如果存在的话），然后 reduce 会调用最好的路径。

希望这有助于解决问题。

Answer 6

评论由：aralo

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

Answer 7

评论由: tmulvaney_ 制作

有一点值得考虑，补丁改进了一个特定的案例，ChunkedSeqs。对于 hash-maps, IndexedSeqs, Ranges 等的 seqs 并未处理。分发到 {{reduce}} 会解决这个问题。你可能对栈爆炸有所顾虑，但我尚未进行实验。

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

Answer 8

评论由：aralo

托马斯，很高兴与你交换想法。请在性能指标上比较你的想法和我的补丁。对内部函数调用 reduce 的问题是栈和不可保值的 reduce。另外，包装减少函数相当昂贵。我已经尝试过了，它要慢得多。我记得这就是为什么我那样做的原因。但再次强调，需要非常小心不要栈爆炸。这对用户来说将是巨大的问题。

Answer 9

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