2024 Clojure状态调查! 分享您的想法。

欢迎!请查看关于 页面以了解更多有关其工作方式的信息。

0
ClojureScript

由向量/chunked-seqs构建的lazy-seqs有时会在首次/下一次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的解释:问题是当你没有给出init时,{{seq-reduce}}将会正确地再次调用{{reduce}}并采取快速路径。然而,给出了init后,它将始终保持首次/下一次,而不会逸出到快速reduce。

注意:在Clojure中,它们按照正确的方式扩展(前三个约为45ms,最后两个约为110ms)。

原因是Clojure正确地逸出到快速路径

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

这是一个RFC,因为我对实现并不完全确定。需要小心以免在这里堆栈溢出...

问题
1. Should 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的reduce创建新的ticket:CLJS-2468

0

由aralo发表的评论:

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

0

评论由:tmulvaney添加

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

所以我认为解决方案就像改变LazySeq.IReduce.-reduce的主体从:{{(seq-reduce f init coll)}}到{{(reduce f init (seq coll)}}。关键是调用seq会提取出内部seq(如果有的话),然后reduce将调用最适合它的路径。

希望这能有所帮助。

0

由aralo发表的评论:

我认为这不是一个好主意。你很容易用这种方法把栈吹爆。尽管如此,我还没有尝试过。

0
评论者:tmulvaney_

有一点值得考虑,该补丁改进了特定情况,即块状序列(ChunkedSeqs)。序列列表,索引序列(IndexedSeqs),范围(Ranges)未处理。分派到{{reduce}}将解决这个问题。关于栈溢出的问题,你可能有些异议,但我还没有实验过。

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

由aralo发表的评论:

托马斯,很高兴能互相交流想法。请随意比较你的想法与我的补丁,并使用性能指标。在对内部的fn调用reduce时的问题是栈和不可保留的reduce。此外,包装reducing函数相当昂贵的。我试过了,速度慢得多。我记得我就是因为这个原因才那样做的。但再次强调,必须非常小心,不要使栈溢出。那会是用户的一个大问题。

0
...