基于某些内容的减少

Question

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

| | clojure.core/some | reduce some | :speed-up |
| :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

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和早期终止的clojure.core/some和clojure.core/every?

为了使它工作，我不得不
* 使用reduce1而不是reduce
* 将deref和reduced移动到reduce1之上
* 照顾好reduce1中的reduced值

我已经为clojure.core/every?的基于reduced的版本进行了基准测试，使用了大小为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的减少函数。

尝试通过`(declare reduce)`声明reduce并没有起作用，我想我知道（我将再次验证这种方法）。

旧方法
由于some在上面的reduce位置上，因此无法访问，所以重点关注将reduce1实现为reduced。这需要移动deref、deref-future和其他一些内容，结果产生了一个相当大的补丁。

新的方法
通过以下方法来减小补丁大小：
1a.将some（和every?）移动到reduce下面。
1b.将some（和every?）向下移动，而将reduce向上移动。
1c.将reduce移动到some（和every?）的上面。
2. 创建some和some1，就像对reduce所做的那样，其中基于reduce的some将位于reduce之下。
3. ?

我不是很喜欢第2种方法，因为会创建更多如reduce1一样的函数 duplication。我希望我们可以通过1x获得一个小补丁。

Answer 7

_由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 行代码，`some`在这些行代码中使用了5次。
2. 将`reduce`移动到`some`（和every?）上方或更接近的位置要求移动一些`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`的函数启用选择性的还原性能增强。`reduce1`到`reduce2`的每次未来更改都只影响该函数。缺点是，在`clojure.core`中将存在另一个还原函数，而且不清楚它存在的原因（文档/注释可能会有帮助）。此外，新的还原函数增加了一层间接性，因为调用`reduce2`的函数必须获取var根。如果这是前进的方向，那么在`reduce1`中添加`reduced`检查将会很棒，这样`reduce2`的行为就总是保持一致的。

在`reduce1`中实现`IReduceInit`有一个很大的接触面，因为它不仅影响`some`，还影响了大量的Clojure核心。对于某些数据结构来说，这将是一种性能胜利，但对于某些数据结构来说，这种变更将可能导致性能损失（例如`java.lang.String`）。如果这是一个有意义的方向，可以枚举较慢的路径并将它们特殊对待到`reduce1`中。

在定义`reduce`之后重新定义`some`。所有方法的足迹中最小。它将仅影响用户代码以及`reduce`之后的`sone`使用（目前是`sone-fn`）。可以考虑向`sone`函数添加`^:redef`，这将允许所有`sone`的使用受益于性能增强，即使在直接链接下。

**基准数据**

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

版本说明

||补丁||:version||描述||
| 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`，并添加到`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结果，其中我可以得到3 µs的`:range`和`:iterate`，这表明在某些情况下存在一些JIT优化。我怀疑REPL中的`:string`测试也存在类似的情况。

Comments

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

Answer 8

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