基于某些条件进行减少

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 毫秒 | 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 方法使用了从集合中取出的 1m 个元素（using (some #(< 1e6 %) coll)）。

这些测试是在以下 java opts 下的 uberjar 上进行的：
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进行修改，我建议您按照页面上的“开发补丁”链接中的说明创建一个补丁：[链接](https://dev.clojure.org/display/community/Contributing)

Answer 3

评论者：petterik

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

Answer 4

_由petterik_发表的评论

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

实现了使用reduce和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?进行更改。

Answer 5

alexmiller发表的评论

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

Answer 6

评论者：petterik

摘要
我认为应该调查是否有一个具有相同效果的更小的补丁。我会看看我能做什么！

目标
在问题已分类后，尽量减小补丁的大小。

问题
some需要实现reduced以在reduce中停止降低过程。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行代码，而`some`在这4,114行代码内被使用了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`。这种方法最为隔离，并且在各方面表现良好。

讨论

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

创建新的 `reduce2` 允许所有目前使用 `reduce1` 的函数选择性地提高 `reduce` 性能。从 `reduce1` 到 `reduce2` 的每次函数更改都只会影响到那个函数。缺点是 clojure.core 中将存在另一个减少函数，并且难以理解其存在的原因（文档/注释可能会有所帮助）。此外，新的减少函数增加了一层间接调用，因为调用 `reduce2` 的函数必须获取 var root。如果这是前进的方向，那么在 `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` 重新定义为使用 `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 测试中也类似发生。

Comments

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

Answer 8

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