请分享您的想法,参加2024 年Clojure 调查问卷!

欢迎!请参阅 关于 页面,了解更多关于如何使用本站的信息。

0票数
Clojure

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 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 调用时使用 (some #(< 1e6 %) coll),从集合中占用 1m 个元素。

我在以下 java opts 的 uberjar 上运行了这些测试
java -Xmx3g "-Dclojure.compiler.direct-linking=true" -server

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

8 个答案

0票数

评论者:petterik

我在描述中格式化出错,找不到如何编辑它(可能是因为我没有权限)。删除虚线可能足够好。

0票数

评论者:jafingerhut

由于你在 Clojure 贡献者协议签署者名单中,我已经提升了你的 JIRA 账户权限。你现在应该能够编辑条目了。

如果你有一些建议要修改 Clojure,我建议您使用本页“开发补丁”链接处的说明创建补丁:https://dev.clojure.org/display/community/Contributing

0票数

评论者:petterik

当然,Andy。我将在明天发起移动,所以我会下周完成。

0票数
评论者:petterik_

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

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

为了实现这一功能,我必须
* 使用 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? 进行了更改。
0票数

评论者:alexmiller

为什么在补丁中将 deref 和 deref-future 等移动了?或者说,更大一点的问题,是否存在相同效果的更小的补丁?

0票数

评论者:petterik

摘要
我认为值得调查是否存在具有相同效果的更小的补丁。我会尽力做到!

目标
由于问题已经分级,尝试最小化补丁大小。

问题
some 需要 reduce 实现以能够在 reduce 中停止减少过程。在 clojure.core 中有两个 reduce 实现,reducereduce1,其中 reduce 实现 reducedreduce1 不实现。将 somereduce1 和/或 reduce 的组合定位到 some 可以访问到实现 reduced 的 reduce 函数的位置。

尝试通过 (declare reduce) 声明 reduce,但没有起作用(将再次验证这种方法)。

老方法
由于 some 的位置在 reduce 之上,因此不能访问,我们专注于使 reduce1 实现 reduced。这需要移动 deref、deref-future 以及其他几个,导致补丁相当大。

新方法
通过以下任意一种方式缩小补丁大小:
1a. 将一些(以及every?)移到reduce下方。
1b. 将一些(以及every?)向下移动,并将reduce向上移动。
1c. 将reduce移动到一些(以及every?)上方。
2.创建与reduce相同的一些some1,基于reducesome将位于reduce下方。
3. ?

我不太喜欢#2,创建了更多像reduce1那样的函数。我希望我们能得到一个较小的#1x补丁。

0票数
评论者: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次。
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`后将`some`使用`alter-var-root`重新定义。这种方法是最隔离的,并且在所有方面表现良好。

*讨论*

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

创建新的 `reduce2` 允许对所有当前使用 `reduce1` 的函数选择性地提升 `reduce` 性能。每次从 `reduce1` 到 `reduce2` 的函数更改都将仅限于该函数。缺点是 clojure.core 中将存在另一个 `reduce` 函数,其存在的原因并不明显(文档/注释可能会有帮助)。此外,新的 `reduce` 函数增加了一层间接调用,因为调用 `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` 的 `reduce` 重新定义 `some` |
| N/A | some-redefined+meta | 使用 `reduce` 和 `alter-var-root` 重新定义 `some`,并为 `some` 添加 `^:redef` 元信息 |
| N/A | REPL | 在运行 Clojure 1.10.0 的 REPL 中定义基于 `reduce` 的 `some` |

测试
||测试 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 测试中也会有类似的情况.
by
我注意到所有的性能测试都是在大型集合上进行(至少 1e4,测试 1e3,然后 1e7,测试 1e6)。对于小型集合(例如,1e2 测试 1e1)表现如何呢?
0票数
参考: https://clojure.atlassian.net/browse/CLJ-2308(由 petterik 报告)
...