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路径,而会坚持首次/后续。

注意:在Clojure中,他们正确地缩放(前3个约为45ms,最后2个约为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的reduce新增工单:CLJS-2468

0

评论由:aralo发表

通过依赖CLJS-2469通过测试。补丁已附加。

0

评论者:tmulvaney

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

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

希望这有所帮助。

0

评论由:aralo发表

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

0
_评论由:tmulvaney_发表

有一点值得考虑,这个补丁改进了特定的情况,ChunkedSeqs。hash-maps的序列、IndexedSeqs、Ranges没有被处理。通过分发,使用 reduce 可以解决这个问题。你可能对溢栈有疑虑,我没有实验过。

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

评论由:aralo发表

托马斯,很高兴交换想法。请随意将你的想法与我的补丁进行性能比较。在对内部fn调用reduce时的问题在于栈和reduce的非持久性。将减少函数包装的成本也很高。我试过,慢得多。如果我没有记错,这就是我那么做的原因。但再次强调,必须非常小心,以免溢栈。那会对用户造成巨大的问题。

0
...