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

欢迎!请参阅关于页以获取更多关于如何工作的信息。

0
ClojureScript

由向量/分块序列构建的懒序列有时会进行较慢的第一个/下一个 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: "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"
#4: "Elapsed time: 101.385000 msecs"
#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-reduce。有时,如ChunkedSeq的情况,内部序列实际上知道如何最好地对自己进行reduce。

所以我认为解决方案就像改变LazySeq.IReduce.-reduce的主体一样简单,从:{{(seq-reduce f init coll)}}更改为{{(reduce f init (seq coll)}}。这里的重点是在调用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
...