2024 Clojure状态调查中分享你的想法!

欢迎!有关如何使用本网站的信息,请参阅关于页面。

0
ClojureScript

从向量/切片-seq构建的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加倍,不是慢两倍,而是慢十倍
(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. Should ChunkedCons implement IReduce? I think so.

9个回答

0

评论由:aralo发表

高级编译时的计时

`
CHROME
“旧版”
#1: "消耗时间: 21.870000 ms"
#2: "消耗时间: 25.485000 ms"
#3: "消耗时间: 134.900000 ms"
#4: "消耗时间: 317.155000 ms"
#5: "消耗时间: 313.225000 ms"
“新版本”
#1: "消耗时间: 23.290000 ms"
#2: "消耗时间: 19.445000 ms"
#3: "消耗时间: 20.075000 ms"
#4: "消耗时间: 102.895000 ms"
#5: "消耗时间: 100.430000 ms"
“旧版”
#1: "消耗时间: 19.585000 ms"
#2: "消耗时间: 19.475000 ms"
#3: "消耗时间: 87.805000 ms"
#4: "消耗时间: 303.340000 ms"
#5: "消耗时间: 291.680000 ms"
“新版本”
#1: "消耗时间: 20.760000 ms"
#2: "消耗时间: 19.690000 ms"
#3: "消耗时间: 18.960000 ms"
第4条: "已过时间: 101.385000 毫秒"
第5条: "已过时间: 101.290000 毫秒"

火狐浏览器

“旧版”
第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。使用哈希映射的 seqs、IndexedSeqs、Ranges 被处理。将分派到 {{reduce}} 会解决这个问题。你可能会认为这会导致栈溢出,但是我还没有实验过。

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

评论由:aralo发表

托马斯,很高兴能够互相交流想法。请随意将您的想法与我的补丁进行性能对比。在内部函数上调用 reduce 的问题是栈和不可保留的 reduce。并且封装 reducing 函数是非常昂贵的。我试过这个方法,它慢得多。据我所知,这就是我那样做的原因。但再次强调,必须非常小心,以免栈溢出。那将给用户带来巨大问题。

0
参考链接:https://clojure.atlassian.net/browse/CLJS-2466(由 aralo 提出)
...