请在2024年Clojure调查中分享您的想法!

欢迎!请参阅关于页面以获取更多关于如何使用本站的信息。

0
Clojure

clojure.core/some 通过first和recur next来实现。它也可以使用reduce来实现,从而在大型集合上获得显著的加速。
我使用criterium评估了range、iterate、vector、sorted-set和lazy-seq,得到了以下结果

| | clojure.core/some | reduce some | 速度提升 |
| :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个元素。

以下是我的uberjar中运行这些测试的java配置选项
java -Xmx3g "-Dclojure.compiler.direct-linking=true" -server

我使用的some的reduce版本和基准测试代码可以在这个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 - 2018/1/20 5:51 下午

使用reduce和early termination with 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?进行了更改。
0

由 alexmiller 发表评论

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

0

评论者:petterik

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

目标
问题得到评估后,尝试最小化补丁的大小。

问题
代码some需要在代码reduce中实现reduced以能够停止减少过程。clojure.core中有两个reduce的实现,即reducereduce1,其中reduce实现了reduced,而reduce1没有。定位一个代码somereduce1和/或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. 创建类似于对 reducesomesome1,其中基于 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,且在这 4,114 LOC 中 `some` 使用了 5 次。
2. 将 `reduce` 移到 `some` 上或更接近 `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 来迭代集合。真正使 `reduce` 比首次+下一个更快的是 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 和分块序列进行优化,以获得某些,但不是所有的 reduce 路径优化。

3. 当 `reduce` 可用时应重新定义 `some`
在定义 `reduce` 之后重定义 `some` 为 `alter-var-root`。这种方法是最隔离的,并且在整个范围上性能表现良好。

*讨论*

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

创建新的 `reduce2` 允许所有当前使用 `reduce1` 的函数选择性地提高 `reduce` 性能。从 `reduce1` 到 `reduce2` 的任何未来函数更改都只会影响该函数。缺点是 clojure.core中将存在另一个减少函数,并难以看出其存在的原因(文档/注释可以帮助)。此外,新的减少函数增加了一级间接层,因为调用 `reduce2` 的函数必须获取变量根。如果这是前进的方向,那么在 `reduce1` 中添加 `reduced` 检查将会很棒,这样 `reduce2` 的行为总是统一的。

在 `reduce1` 中实现 IReduceInit 具有广泛的接触面,因为它不仅影响 `some`,还影响大量的 Clojure 内核。对于某些数据结构来说,这将是一个性能上的胜利,但对于某些数据结构来说,这种改变可能会导致性能损失(例如 java.lang.String)。如果这是一个有趣的前进方向,人们可以枚举较慢的路径并特别地将它们放入 `reduce1`。

在定义 `reduce` 之后重定义 `some`。任何方法中最小的足迹。它只会影响定义 `reduce` 后以及 `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 | 使用 `reduce` 和 `alter-var-root` 重新定义 `some` |
| N/A | some-redefined+meta | 使用 `reduce` 和 `alter-var-root` 重新定义 `some` 并为 `some` 添加 `^:redef` 元数据 |
| N/A | REPL | 定义基于 Clojure 1.10.0 运行的 REPL 中的 reduce-based 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
by
参考:[https://clojure.atlassian.net/browse/CLJ-2308](https://clojure.atlassian.net/browse/CLJ-2308)(由petterik报告)
...