请在Clojure 2024状况调查中分享您的想法!

欢迎!请查看关于页面以了解更多关于该功能的信息。

0投票
ClojureScript

由向量/分块seq构建的惰性seq有时会进行缓慢的初始/后续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将其加倍,它们不是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,因为我不十分确定实施。需要小心不要遍地栈...

问题
1. ChunkedCons应该实现IReduce吗?我认为如此。

9个回答

0投票

评论者: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 毫秒"
第4条: "已过时间: 101.385000 毫秒"
第5条: "已过时间: 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 毫秒"

`

0投票
作者:

评论者:aralo

对真正(未分块)的 lazy-seqs 的影响可忽略不计(由于垃圾回收导致很大的差异,难以测量)。

0投票
作者:

评论者:aralo

为 ChunkedCons 减少打开了新工单:CLJS-2468

0投票
作者:

评论者:aralo

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

0投票
作者:

评论者:tmulvaney

ChunkedSeq 已实现了一个高效的减少策略。我相信问题在于 LazySeq,它只是一个可能包含不同类型序列的容器,它总是对这个内部序列调用 seq-reduce。例如,在 ChunkedSeq 的情况下,内部序列实际上知道如何最好地减少自己。

所以我认为解决方案就是将 LazySeq.IReduce.reduce 的主体从:{{(seq-reduce f init coll)}} 改为:{{(reduce f init (seq coll)}}。这里的关键是调用 seq 可以提取内部序列(如果有的话),然后reduce 将调用最好的路径。

希望这能有所帮助。

0投票
作者:

评论者:aralo

我认为这不是一个好主意。你很容易用这种方法搞砸堆栈。虽然,我还没有尝试过。

0投票
评论者:tmulvaney

有一件事值得关注,这个补丁改进了一个特殊情况,ChunkedSeqs。hash-maps的seqs、IndexedSeqs、Ranges未被处理。分派到{{reduce}}将解决这个问题。你可能对搞砸堆栈有不同看法,但我还没有试验过。

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

评论者:aralo

托马斯,很高兴与您互相交流想法。请随意比较您的主意和我这个补丁的性能指标。在内部函数上调用reduce的问题在于堆栈,以及非保持性reduce。而包装减少函数相当昂贵。我试过,这个方法要慢得多。我记得这就是为什么我那样做的原因。但再次强调,需要非常小心,不要搞砸堆栈。那对用户来说将是个大问题。

0投票
参考:[https://clojure.atlassian.net/browse/CLJS-2466](https://clojure.atlassian.net/browse/CLJS-2466)(由aralo报告)
...