2024 年 Clojure 调查问卷! 分享您的想法。

欢迎!如需了解有关如何工作的更多信息,请参阅 关于 页面。

0
ClojureScript

由 vector/chunked-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 乘以两倍,它们不是慢两倍,而是慢 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. 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 毫秒"
“耗时:291.680000 毫秒”
"新版本"
“耗时:20.760000 毫秒”
“耗时:19.690000 毫秒”
“耗时:18.960000 毫秒”
“耗时:101.385000 毫秒”
“耗时:101.290000 毫秒”

FIREFOX

"旧版"
“耗时:7.880000 毫秒”
“耗时:7.820000 毫秒”
“耗时:69.460000 毫秒”
“耗时:197.800000 毫秒”
“耗时:209.300000 毫秒”
"新版本"
“耗时:7.380000 毫秒”
“耗时:7.360000 毫秒”
“耗时:8.100000 毫秒”
“耗时:110.640000 毫秒”
“耗时:89.960000 毫秒”
"旧版"
“耗时:6.520000 毫秒”
“耗时:7.360000 毫秒”
“耗时:106.920000 毫秒”
“耗时:252.300000 毫秒”
“耗时:249.800000 毫秒”
"新版本"
“耗时:7.360000 毫秒”
“耗时:6.940000 毫秒”
“耗时:6.880000 毫秒”
“耗时:99.380000 毫秒”
“耗时:53.220000 毫秒”

`

0
by

评论来源:aralo

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

0
by

评论来源:aralo

为ChunkedCons的reduce创建了新的工单:CLJS-2468

0
by

评论来源:aralo

依赖于CLJS-2469才能通过测试。补丁已附件。

0
by

评论者:tmulvaney

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

因此,我认为解决方案就像将LazySeq.IReduce.-reduce的主体从:(seq-reduce f init coll)改为(reduce f init (seq coll))一样简单。关键在于调用seq会提取内部序列(如果有的话),然后reduce将调用最适合它的路径。

希望这有所帮助。

0
by

评论来源:aralo

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

0
by
_由 tmulvaney 发表的评论:

有一点值得关注,该补丁改善了一个特殊情况,ChunkedSeqs。hash-maps 序列,IndexedSeqs,Ranges 不被处理。分发到 {{reduce}} 可解决这个问题。你可能关于打爆堆栈有看法,但我还没有实验过。

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

评论来源:aralo

托马斯,很高兴交换想法。请随意将你的想法与我的补丁进行比较,并参考性能指标。调用内部 fn 的 reduce 问题是堆栈和还原非保持性。包装减少函数相当昂贵。我试过,这要慢得多。我记得我之所以这样做,是因为速度慢。但再次强调,需要非常小心,不要打爆堆栈。这将对用户造成巨大的问题。

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