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

欢迎!请参阅关于页面,了解更多关于这一工作的信息。

0
Clojure

clojure.core/some通过first和recur实现。它可以利用reduce来实现,从而在大型集合上获得显著的性能提升。
我使用criterium为range、iterate、vector、sorted-set和lazy-seq进行了基准测试,得到了以下结果

| | clojure.core/some | reduce some | :加速比 |
| :iterate | 14.502145 毫秒 | 3.994055 毫秒 | 3.63倍 |
| :range | 16.949429 毫秒 | 14.903065 毫秒 | 1.14倍 | <-- 这是对clojure.lang.Range的结果
| :vector | 23.706839 毫秒 | 5.765865 毫秒 | 4.11倍 |
| :lazy-seq | 28.723150 毫秒 | 5.616475 毫秒 | 5.11倍 |
| :set | 53.063608 毫秒 | 17.419191 毫秒 | 3.05倍 |

每个集合的大小为1e7,some使用的是(some #(< 1e6 %) coll),从集合中取出1m个元素。

我使用了以下java opts在uberjar上运行了这些测试
java -Xmx3g "-Dclojure.compiler.direct-linking=true" -server

我使用的some的reduce版本和基准测试代码可以在该gist中找到
https://gist.github.com/petterik/63fad1126842ba4550dcb338328e2975

8 个答案

0

评论由:petterik发表

我在描述中搞错了格式,找不到如何编辑它(可能是因为我没有权限?)。去除点线可能就足够好了。

0

评论由:jafingerhut发表

由于你在Clojure贡献协议签名者名单上,我已经将你的JIRA权限提升了。你现在应该能够编辑这个工单了。

如果你想要对Clojure进行修改,建议你创建一个补丁,使用本页“开发补丁”链接中的说明:https://dev.clojure.org/display/community/Contributing

0

评论由:petterik发表

当然,Andy。我计划明天启动迁移,下周再处理它。

0
_由petterik_做出的评论

附件 CLJ-2308.patch - 18/Jan/18 5:51 PM

实现了 clojure.core/some 和 clojure.core/every?,使用 reduce 和预先终止。

为了使其工作,我不得不
* 使用 reduce1 而不是 reduce
* 将 deref 和 reduced 移到 reduce1 之上
* 在 reduce1 中注意 reduced 值

我已经对比了基于 reduced 的 clojure.core/every? 和 1e4 大小的集合以及 pred #(< % 1e3)
| |  clojure.core/every? | reduce every? | :speed-up
|  :iterate | 16.897504 µs |  8.273847 µs | 2.04x
|:long-range | 15.197158 µs |  8.658177 µs | 1.76x
|   :vector | 27.534283 µs |  2.519784 µs | 10.93x
| :lazy-seq | 25.457922 µs |  6.393590 µs | 3.98x
|      :set | 56.421657 µs | 17.143458 µs | 3.29x

由于结果不错,并且 some 与 every? 非常相似,因此我继续为 every? 进行了更改。
0

评论由 alexmiller 完成

为什么 deref 和 deref-future 等 在补丁中被移动?或者,更大的问题是,是否有一个具有相同效果的更小的补丁?

0

评论由:petterik发表

摘要
我认为值得调查是否有具有相同效果的更小的补丁。我会看看能做些什么!

目标
由于问题已被分类,尽量减小补丁的大小。

问题
some 需要实现 reducedreduce 中,才能使减少过程终止。在 clojure.core 中有两个 reduce 实现,即 reducereduce1,其中 reduce 实现了 reduced,而 reduce1 没有实现。将 somereduce1 和/或 reduce 组合在一起,使得 some 可以访问实现 reduced 的 reduce 函数。

尝试通过 (declare reduce) 声明 reduce 并且它不起作用(将再次验证此方法)。

旧方法
由于在位置上 somereduce 之上且不可访问,因此重点关注让 reduce1 实现 reduced。这需要移动 deref、deref-future 以及其他一些东西,导致了相当大的补丁。

新的方法
通过以下方式之一最小化补丁大小
1a. 将一些(以及 every?)移至 reduce 以下
1b. 将一些(以及 every?)向下移动,并将 reduce 向上移动。
1c. 将 reduce 移至一些(以及 every?)之上。
2. 创建 somesome1,就像为 reduce 所做的那样,其中基于 reducesome 将在 reduce 之下。
3. ?

我不太喜欢第2种方法,它创建了像 reduce1 一样的函数的更多重复。我希望我们能用第1x来获得一个小补丁。

0
_由petterik_做出的评论

这是我的进度报告。我概述了我的思考过程。

请告诉我你是否更感兴趣于只看指标,这样我可以减少一些琐碎的内容。

(长话短说)

三个补丁
1. 添加了新的 `reduce2`,当可能时将其重新定义为 `reduce`。(CLJ-2308-2-reduce2.patch)
2. 在 `reduce1` 中实现了 reduced? 和 IReduceInit 检查。(CLJ-2308-3-IReduceInit.patch)
3. 一旦定义了 `reduce`,就使用 `alter-var-root` 重新定义 `some`。(CLJ-2308-4-alter-var-root.patch)

所有补丁都比原始补丁小很多。

(背景)

当我开始处理一个新的补丁时,我开始想起为什么我会采用原始的方法。

1. 在 clojure/core.clj 中,`some` 和 `reduce` 之间有 4,114 个 LOC 的距离,并且在这 4,114 个 LOC 中 `some` 被使用了 5 次。
2. 将 `reduce` 移至 `some` 之上或更近,需要移动一些 `load` 表达式,包括 {{(load "core/protocols")}}。

鉴于这两个障碍,我重新审视了原始补丁及 `deref` 和 `deref-future` 为什么必须移动的问题。我能够通过以下方式创建一个非常小巧的补丁:
1. 在 Reduced 对象上调用 {{.deref}} 方法而不是 `deref` 函数。
2. 使用 {{RT/isReduced}} 而不是 `reduced?` 函数。
3. 只将 `reduced` 函数移动到 `some` 之上。

当我准备新的补丁时,我首先运行了两个基准测试,发现基于 `reduce1` 的 `some` 在一种情况下较慢,并确认真是基于 `reduce` 的 `some` 要快得多。这个发现并不令人惊讶,因为 `reduce1` 使用 seq api 对具有 chunked-seq 优化的集合进行迭代。真正使 `reduce` 比first+next 快得多的是 coll-reduce 协议和 IReduceInit 接口。

(方法)

1. 新的 `reduce2`
鉴于这个背景,我首先尝试将 `reduce1` 重新定义为 `reduce`,但不起作用,因为 `reduce` 调用的生命周期缓存代码调用了 `reduce1`。将 `reduce1` 重新定义为 `reduce` 可能会导致 `reduce` 循环无限调用。由于这个问题似乎相当棘手,我选择了创建一个新的减少函数 `reduce2`,它使用 `alter-var-root` 重新定义为 `reduce`。

2. 在 `reduce1` 中实现 IReduceInit 优化
这个方法是在 clojure.core/set 的启发下产生的,其中我们特别处理了 IReduceInit 的实现。通过优化 `reduce1` 中的 IReduceInit 和 chunked-seq,我们获得了部分但不是全部的 reduce 路径优化。

3. 当 `reduce` 可用时重新定义 `some`
一旦定义了 `reduce`,就使用 `alter-var-root` 重新定义 `some`。这种方法最独立,而且表现良好。

(讨论)

仅仅向 `reduce1` 添加 `reduced` 语义是不够的,因为大多数的性能优势都来自 IReduceInit 和 CollReduce。

创建新的 `reduce2` 允许所有目前使用 `reduce1` 的函数选择提高Reduce性能。将来的任何从 `reduce1` 到 `reduce2` 的函数变更都将仅限于那个函数。缺点是 clojure.core 将会存在另一个Reduce函数,而且很难看出它的存在原因(文档或注释可能会有所帮助)。另外,新的Reduce函数增加了一层间接调用,因为调用 `reduce2` 的函数必须获取var根。如果这是前进的方向,那么在 `reduce1` 中添加 `reduced` 检查将会是个好主意,这样的话 `reduce2` 的行为总是保持一致。

在 `reduce1` 中实现 IReduceInit 具有广泛的接触面积,因为它不仅影响 `some`,还影响了Clojure核心的很多地方。对于某些数据结构来说,这可能会提高性能,但对于某些数据结构来说,这种变更可能会降低性能(例如 java.lang.String)。如果这是一个有趣的方向,可以选择枚举较慢的路径,并将它们特别处理到 `reduce1` 中。

在定义 `reduce` 之后重新定义 `some`。任何方法中最小的足迹。它将只会影响用户代码以及 `reduce` 后的 `some` 使用(当前是 `some-fn`)。可以考虑向 `some` 函数添加 ^:redef,这样即使直接连接也能使所有 `some` 的使用都从性能提升中受益。

**基准数据**

所有方法都使用 {{criterium.core/bench}} 进行了测试。

版本说明

||补丁||:版本||描述||
| N/A | 1.10.0 | 基线。没有更改的Clojure 1.10.0。 |
| N/A | reduce1-reduced | 实现 reduced 检查的 reduce1 |
| CLJ-2308-3-IReduceInit.patch | reduce1-reduced+IReduceInit | 实现 reduced 和 IReduceInit 检查的 reduce1 |
| CLJ-2308-2-reduce2.patch | reduce2 | 重定义为 `reduce` 的 reduce2 |
| CLJ-2308-4-alter-var-root.patch | some-redefined | 使用 `reduce` 和 `alter-var-root` 重新定义 `some` |
| N/A | some-redefined+meta | 使用 `reduce` 和 `alter-var-root` 重新定义 `some` 并添加 ^:redef 元数据到 `some` |
| N/A | REPL | 定义在运行 Clojure 1.10.0 的 REPL 中基于 `some` 的 reduce |

测试
||测试 ID|| 表达式||
|:range | (some #(< 1e3 %) (range (long 1e4))) |
|:iterate | (some #(< 1e3 %) (iterate inc 0)) |
|:string | (some #(= % \x) "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111x") |

平均时间
||测试 ID || 1.10.0 || reduce1-reduced || reduce1-reduced+IReduceInit || reduce2 || some-redefined || some-redefined+meta || REPL ||
| :range | 29.439476 µs | 7.281439 µs | 4.958930 µs | 4.935221 µs | 5.030624 µs | 5.052136 µs | 5.636544 µs |
| :iterate | 36.640107 µs | 56.214323 µs | 6.622923 µs | 6.835455 µs | 7.014428 µs | 7.242155 µs | 6.660484 µs |
| :string | 6.236579 µs | 7.853746 µs | 7.645742 µs | 4.186791 µs | 4.170554 µs | 4.180583 µs | 1.898992 µs |
| 总计 | 72.316162 | 71.349508 | 19.227595 | 15.957467 | 16.215606 | 16.474874 | 14.19602 |

所有结果都具有可复现性和一致性,除了 REPL 的结果,我在 :range 和 :iterate 达到了最低 3 µs,这表明有时JA
by
我注意到所有性能测试都是在大型集合(至少1e4,测试1e3,然后1e7,测试1e6)上完成的。对于小型集合(例如,1e2测试1e1),性能如何?
0
by
参考:[CLJ-2308](https://clojure.atlassian.net/browse/CLJ-2308)(由petterik报告)
...