基于某些条件的减少

Question

clojure.core/some 使用 first 和 recur next 实现。它也可以使用 reduce 来实现，从而在大型集合中获得显著的性能提升。
我使用 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 运行这些测试
java -Xmx3g "-Dclojure.compiler.direct-linking=true" -server

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

Answer 1

评论由：petterik

我在说明中的格式有误，找不到如何编辑它（可能是由于我没有权限）？移除虚线应该差不多就可以了。

Answer 2

评论由：jafingerhut

由于您是签署了 Clojure 贡献者协议的人员名单之一，我已经提升了您 JIRA 账户的权限。现在您应该能够编辑条目了。

如果您想对Clojure进行修改，我建议根据本页面“开发补丁”（Developing Patches）链接中的说明来创建补丁：https://dev.clojure.org/display/community/Contributing

Answer 3

评论由：petterik

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

Answer 4

_由 petterik_ 发表的评论

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

使用Reduce和早期停止（with 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 实现了 reduced，而 reduce1 没有实现。将some、reduce1 和/或 reduce 的组合置于 some 可以访问实现 reduced 的 reduce 函数的位置。

尝试通过 (declare reduce) 声明 reduce 并未成功，如我所知（将再次验证该方法）。

旧方法
由于在位置上some位于reduce之上，因此不可访问，因此关注将reduce1实现为reduced。这需要移动deref、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个LOC，`some`在这4,114个LOC中使用了5次。
将`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的实现进行了特殊处理。通过对IReduceInit和chunked-seq的优化`reduce1`，我们获得了部分reduce路径优化。

3. 当`reduce`可用时重新定义`some`
一旦定义了`reduce`，就使用`alter-var-root`重新定义`some`。这种方法最为独立，并且整体性能良好。

*讨论*

仅仅为`reduce1`添加`reduced`语义并不足够，因为大多数性能优势都来自IReduceInit和CollReduce。

创建新的 `reduce2` 允许所有当前使用 `reduce1` 的函数选择性地提高减少性能。从 `reduce1` 到 `reduce2` 的任何未来变更都将仅限于该函数本身。缺点是，clojure.core 中将存在另一个减少函数，且其存在的原因并不容易理解（文档/注释可能会帮到一些）。此外，新的减少函数增加了一层间接级别，因为调用 `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 | 将 `some` 重新定义为使用 `reduce` 和 `alter-var-root` |
| N/A | some-redefined+meta | 将 `some` 重新定义为使用 `reduce` 和 `alter-var-root` 并添加 `^: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，这表明有时有一些 JIT 优化正在进行。我怀疑我的 REPL 中的 :string 测试也可能出现类似的情况。

Comments

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

Answer 8

参考：[https://clojure.atlassian.net/browse/CLJ-2308](https://clojure.atlassian.net/browse/CLJ-2308) (由petterik报告)