基于某些内容的减少

Question

clojure.core/some 实现使用 first 和 recur next。它可以用 reduce 和 reduced 实现，从而在大型集合上获得显著的加速。
我使用 criterium 对 range、iterate、vector、sorted-set 和 lazy-seq 进行基准测试，得到了以下结果

| | clojure.core/some | reduce some | :speed-up |
| :iterate | 14.502145 ms | 3.994055 ms | 3.63x |
| :range | 16.949429 ms | 14.903065 ms | 1.14x | <-- 此结果针对 clojure.lang.Range
| :vector | 23.706839 ms | 5.765865 ms | 4.11x |
| :lazy-seq | 28.723150 ms | 5.616475 ms | 5.11x |
| :set | 53.063608 ms | 17.419191 ms | 3.05x |

每个集合的大小为 1e7，some 使用 (some #(< 1e6 %) coll) 调用，从集合中占用 1m 个元素。

我使用以下 java opts 运行这些测试，创建了一个 uberjar
java -Xmx3g "-Dclojure.compiler.direct-linking=true" -server

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

Answer 1

由 petterik 发布的评论

我在描述中的格式出了问题，找不到如何编辑它（可能是由于我没有权限？）。删除虚线可能已经足够。

Answer 2

由 jafingerhut 发布的评论

由于您已签署 Clojure 贡献者协议，我已经提高了您的 JIRA 账户权限。您现在应该能够编辑票据。

如果您想对Clojure进行修改，我建议您根据本页“开发补丁”链接中的说明创建一个补丁：[开发补丁](https://dev.clojure.org/display/community/Contributing)

Answer 3

由 petterik 发布的评论

当然，Andy。我打算明天开始迁移，所以我下周会处理。

Answer 4

_由 petterik 发布的评论_

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

使用reduce和reduced实现了clojure.core/some和clojure.core/every?

为了使这成为可能，我不得不
* 使用reduce1代替reduce
* 将deref和reduced移到reduce1上方
在reduce1中处理reduced值

我针对大小为1e4的集合和pred #(< % 1e3)进行了reduced基于clojure.core/every?的基准测试
| |  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?

Answer 5

alexmiller 发布的评论：

为什么在补丁中将deref和deref-future等移除？或者，更大一点的问题，是否有一个具有相同效果的更小的补丁？

Answer 6

由 petterik 发布的评论

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

目标
由于已经对问题进行了故障排除，尝试最小化补丁大小。

问题
some需要在reduce中实现reduced才能中止减少过程。clojure.core中存在两个reduce实现reduce和reduce1，其中reduce实现在其中，而reduce1没有。根据some、reduce1和/或reduce的组合定位，使some可以访问实现reduced的reduce函数。

尝试使用`(declare reduce)`声明reduce，但没有效果（将再次验证该方法）。

旧方法
由于some在位置上位于reduce之上，因此无法访问，因此重点关注将reduce1实现为reduced。这需要移动一些变量引用、deref-future以及其他几个变量，从而导致相当大的补丁。

新方法
通过以下方式之一最小化补丁大小：
1a. 将some（和every?）移动到reduce之下。
1b. 将some（和every?）向下移动，将reduce向上移动。
1c. 将reduce移动到some（和every?）之上。
2. 创建与reduce相同的some和some1，其中基于reduce的some将位于reduce之下。
3. ?

我不太喜欢第2项，即为reduce1之类的函数创建更多重复功能。我希望能得到一个带#1x的小补丁。

Answer 7

_由 petterik 发布的评论_

这是我进度报告。我概述了我的思路。

请告诉我你是否更感兴趣于只看指标，我可以让它少说点。

*TL;DR*

三个补丁
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行代码，且在这些行中`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` 的函数选择提升减少性能。`reduce1` 到 `reduce2` 的任何未来更改都仅限于该函数。缺点是在 `clojure.core` 中将存在另一个减少函数，且不易看出其存在的原因（文档/评论可能会有所帮助）。此外，新减少函数添加了一层间接调用等级，因为调用 `reduce2` 的函数必须获取变量根。如果这是前进的方向，在 `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 | 将 reduce2 重新定义为 `reduce` |
| CLJ-2308-4-alter-var-root.patch | some-redefined | 将 `some` 重新定义为使用 `reduce` 和 `alter-var-root` |
| N/A | some-redefined+meta | 将 `some` 重新定义为使用 `reduce` 和 `alter-var-root`，并为 `some` 添加 ^:redef 元数据 |
| N/A | REPL | 在 Clojure 1.10.0 运行的 REPL 中定义基于 reduce 的 some |

测试
||测试 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 结果较低，我得到的范围和迭代结果分别为 3 µs，这表明有时存在一些 JIT 优化。我怀疑在我的 REPL 中的字符串测试中也存在类似的情况。

Comments

我注意到所有性能测试都是在大规模集合（至少1e4，测试1e3，然后1e7，测试1e6）上进行的。对于小集合（例如，1e2进行1e1测试）的表现如何呢？

Answer 8

参考资料： https://clojure.atlassian.net/browse/CLJ-2308（由petterik报告）