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

欢迎!有关本站的工作方式,请参见 关于 页面以获取更多信息。

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}} 后,它将不会逃脱到快速路径,而是保持在首次/下一次。

注意:在 Clojure 中,它们“适当”地进行缩放(前 3 个约为 45ms,最后 2 个约为 110ms)。

原因是 Clojure 正确地逃离到快速路径

https://github.com/clojure/clojure/blob/2b242f943b9a74e753b7ee1b951a8699966ea560/src/clj/clojure/core/protocols.clj#L131-L143

这是一个 RFC,因为我不完全确定实施细节。需要小心不要炸毁堆栈...

问题
1. 分块 Cons 应该实现 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

"旧版"
“已过时间: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

评论者: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
by
_由 tmulvaney 发表的评论_

值得考虑的一点是,该补丁改进了特定的情况,但 ChunkedSeqs、序列化哈希表、IndexedSeqs、Ranges 仍未处理。调用 {{reduce}} 的分派可以解决这个问题。你提到关于堆栈溢出的顾虑是合理的,但我尚未进行实验。

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

评论者:aralo

Thomas,很高兴互相交流想法。请随意将您的想法与我的补丁和性能指标进行比较。在内部函数上调用 reduce 的问题在于堆栈空间和不能保持的 reduce。将减少函数包裹起来相当昂贵。我尝试过这种方法,但速度慢多了。据我所知,这就是为什么我采取了这种方法的。但再次强调,绝对不能让堆栈溢出。这对用户来说是个非常大的问题。

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