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

欢迎!请查阅关于页面,了解更多关于如何使用本系统的方式。

0
Clojure

clojure.core/some 是使用 first 和 recur 实现的。它也可以使用 reduce 和 reduced 来实现,从而在大型集合上获得显著的速度提升。
我使用 criterium 测试了 range、iterate、vector、sorted-set 和 lazy-seq,以下是我的结果:

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

每个集合的大小都是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](https://dev.clojure.org/display/community/Contributing)

0

评论由:petterik 发布

当然,Andy。我将在明天发起迁移,所以下周我会处理这个问题。

0
_由 petterik 发布的评论_

附加 CLJ-2308.patch - 2018年1月20日 5:51 PM

通过reduce和early termination with reduced实现了clojure.core/some和clojure.core/every?

要实现这一点,我必须
* 使用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`要求在`reduce`中实现`reduced`,以便能够终止减少过程。`clojure.core`中有两个`reduce`实现,即`reduce`和`reduce1`,其中`reduce`实现`reduced`,而`reduce1`不实现。通过将`some`、`reduce1`和/或`reduce`相结合,使`some`能够访问实现`reduced`的减少函数。

尝试通过`(declare reduce)`声明`reduce`,但不起作用( 将再次验证此方法)。

旧方法
由于`some`在位置上位于`reduce`之上,因此无法访问,因此重点是将`reduce1`修改为实现`reduced`。这需要移动deref、deref-future和其他几个,这将导致补丁相当大。

新的方法
通过以下方式之一最小化补丁大小:
1a. 将某些(和每个?)移动到 reduce 之下
1b. 将某些(和每个?)向下移动,将 reduce 向上移动。
1c. 将 reduce 移到某些(和每个?)之上。
2. 创建类似于 reducesomesome1,其中基于 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,`some` 在这些 LOC 中被使用 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` 比第一+下一个更快的是 coll-reduce 协议和 IReduceInit 接口。

*方法*

1. 新 `reduce2`
在这个背景下,我首先尝试将 `reduce1` 重新定义为 `reduce`,但这不起作用,因为 `reduce` 调用的协议扩展缓存代码调用了 `reduce1`。将 `reduce1` 重新定义为 `reduce` 将导致对 `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`。这种方法是最独立的,并且在各个方面都表现良好。

*讨论*

仅仅将 `reduced` 语义添加到 `reduce1` 是不够的,因为大部分性能优势来自 IReduceInit 和 CollReduce。

创建新的 `reduce2` 允许所有当前使用 `reduce1` 的函数可选地提高减少性能。来自 `reduce1` 到 `reduce2` 的未来每个更改都仅限于该功能。缺点是 clojure.core 中将存在另一个减少函数,并且不容易看出它的存在原因(文档/注释可能会有所帮助)。此外,新的减少函数增加了一个间接层,因为调用 `reduce2` 的函数必须获取 var 根。如果这条路可行,添加 `reduced` 检查到 `reduce1` 将很好,以保证 `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 | 将 `reduce2` 重新定义为 `reduce` |
| CLJ-2308-4-alter-var-root.patch | some-redefined | 将 `some` 重新定义为使用 `alter-var-root` 的 `reduce` |
| N/A | some-redefined+meta | 将 `some` 重新定义为使用 `alter-var-root` 的 `reduce` 并向 `some` 添加 ^:redef 元数据 |
| 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,这表明有时会进行一些 JIT 优化。我怀疑我的 REPL 中的 `:string` 测试也会发生类似的情况。
我注意到所有的性能测试都是在大型集合(至少1e4,测试1e3,然后1e7,测试1e6)上进行的。对于小型集合(例如,1e2测试1e1)的表现如何?
0
参考:https://clojure.atlassian.net/browse/CLJ-2308(由petterik报告)
...