基于某些条件的Reduce

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.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选项的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](https://dev.clojure.org/display/community/Contributing)

Answer 3

评论由：petterik

当然，Andy。我计划明天开始进行操作，所以我会下周完成。

Answer 4

评论：petterik_

附件：CLJ-2308.patch - 2018/1/20 5:51 PM

实现clojure.core/some和clojure.core/every?，使用reduce和early termination with reduced。

为了使这一功能正常运行，我必须
* 使用reduce1而不是reduce
* 将deref和reduced放置在reduce1之上
* 在reduce1中处理reduced值

我已经在集合大小为1e4和pred #(< % 1e3)的情况下对手动reduced based 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_

这是我的进度报告。我已经概述了我的思考过程。

请告诉我你是否更感兴趣于仅提供指标，我可以减少一些对话内容。

*简化版*

三个补丁
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 进行优化，我们得到了一些，但不是所有的减少路径优化。

3.当 `reduce` 可用的时候重新定义 `some`
在定义 `reduce` 后，使用 `alter-var-root` 重新定义 `some`。这种方法最为隔离，并且表现良好。

*讨论*

仅仅为 `reduce1` 添加 `reduced` 语义是不够的，因为大部分的性能提升都来自 IReduceInit 和 CollReduce。

创建新的 `reduce2` 允许为所有当前使用 `reduce1` 的函数选择接受减少性能提升。对 `reduce1` 的每个未来更改都只会影响到该特定的函数。缺点是，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 | 使用 `alter-var-root` 重新定义 `some` |
| N/A | some-redefined+meta | 使用 `alter-var-root` 重新定义 `some` 并添加 ^:redef 元数据 |
| N/A | REPL | 定义基于 `some` 的 reduce 的 REPL，运行 Clojure 1.10.0 |

测试
||测试 ID|| 表达式||
|:range | (some #(< 1e3 %) (range (long 1e4))) |
|:iterate | (some #(< 1e3 %) (iterate inc 0)) |
|:string | (some #(= % \x) "1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111x") |

平均时间
||测试 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报告）