基于某些情况减少

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叫做(一些 #(< 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和提前终止采用reduced的方式实现了clojure.core/some和clojure.core/every?

为了实现这个函数我必须
* 使用reduce1而不是reduce
* 将deref和reduced放置于reduce1之上
注意reduce1中的reduced值

我已经对基于reduced的clojure.core/every?进行了基准测试，使用大小为1e4的集合和逻辑#(< % 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要求在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. 将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次。
将 `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`，但这是不行的，因为 protocols 扩展的缓存代码由 `reduce` 调用。将`reduce1`重定义为`reduce`会导致对`reduce`的调用无限循环。由于这个问题似乎相当棘手，我选择创建一个新的简化函数 `reduce2`，使用`alter-var-root`重定义它为`reduce`。

2. 在`reduce1`中实现IReduceInit优化
这个方法受到了clojure.core/set的启发，在那里我们对IReduceInit的实现进行了特殊处理。通过优化reduce1中的IReduceInit和chunked-seq，我们获得了一些，但不是所有的reduced路径优化。

3. 当`reduce`可用时重新定义`some`
定义`reduce`之后使用`alter-var-root`重新定义`some`。这种方法最为孤立，并且在各个方面都表现出良好的性能。

*讨论*

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

创建新的`reduce2`允许对当前使用`reduce1`的所有函数选择性地进行性能提升。从`reduce1`到`reduce2`的任何对未来函数的修改都将仅限于该特定函数。缺点是clojure.core中将存在另一个reducing函数，且不容易看出其存在的理由（文档/注释可能会有帮助）。此外，新reducing函数增加了一层间接性，因为调用`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}}进行了测试。

版本解释

||补丁||: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 | 使用`alter-var-root`将`some`重定义为使用`reduce` |
| N/A | some-redefined+meta | 使用`alter-var-root`将`some`重定义为使用`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中的:range测试也可能发生类似的情况。

Comments

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

Answer 8

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