请在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. 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创建新工单: 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的seqs,IndexedSeqs,Ranges没有处理。通过转发给{{reduce}}可以解决这个问题。你说的关于耗尽栈空间的问题可能有道理,我还没有试验过。

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

由:aralo

托马斯,很高兴来回交流想法。你可以随时比较你的想法和我补丁的性能指标。在内部fn上调用reduce的问题在于栈,还有非保留的reduce。并且包装reducing函数相当昂贵。我试过,但是慢得多。我记得这就是为什么我这么做的原因。但再次强调,必须非常小心以免耗尽栈空间。这对用户来说将是巨大的问题。

0
...