2024 年 Clojure 状态调查!中分享您的想法。

欢迎!有关本网站的工作方式,请参阅关于页面以获取更多信息。

+9
Clojure

在最近进行性能工作时,我发现将 unroll 转换为单个 assoc 调用比使用多个键快得多(对于我的特定应用程序,大约快 10%)。Zachary Tellman 后来指出,clojure.core 实际上根本不 unroll assoc,即使对于相对较低数量的键也是如此。

我们已经 unroll 了其他关键的性能函数,这些函数通过 apply 调用 things,例如 update https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L5914,但(我认为在许多应用程序和库的关键路径上)assoc 似乎也会从中受益。

我尚未为此开发修补程序,但我进行了一些独立的基准测试工作

https://github.com/yeller/unrolling-assoc-benchmarks

基准测试结果

代码: https://github.com/yeller/unrolling-assoc-benchmarks/blob/master/src/bench_assoc_unrolling.clj

| |1 |2 |3 |4 |
| :-- | :-- | :-- | :-- | :-- |
| 空数组映射(未 unroll) | 23ns | 93ns | 156ns | 224ns |
| 空数组映射(unroll assoc) | N/A | 51ns | 80ns | 110ns |
| | | | | |
| 20 个元素的持久 hashmap(未 unroll) | 190ns | 313ns | 551ns | 651ns |
| 20 个元素的持久 hashmap(unroll assoc) | N/A | 250ns | 433ns | 524ns |
| | | | | |
| 记录(未 unroll) | 12ns | 72ns | 105ns | 182ns |
| 记录(unroll assoc) | N/A | 21ns | 28ns | 41ns |

每次测量都在单独的 JVM 中进行,以避免 JIT 路径依赖。

基准测试在一个通用服务器(8 个 cpu,32gb ram)上运行,安装有 Ubuntu 12.04 和 Java 8 的最新版本。附件包含 cpuinfounamejava -version 输出。

启用了相对标准的 JVM 生产标志,并注意禁用 leiningen 的启动时间优化(这会禁用许多 JIT 优化)。

可以克隆存储库并运行 script/bench 来运行基准测试。

关于此修补程序有一个待解决的问题:我们应该 unroll 多少次调用?update(在 1.7 测试版本中已 unroll)unroll 到 3 个参数。添加更多 unroll 并不难,但这会影响 assoc 的可读性。

修补程序:CLJ-1656-v5.patch

25 答案

0 投票

评论者:tcrayford

好吧,附上了 assoc.diff,将其展开到比当前代码多一个层级(因此在不进行递归的情况下支持两个键值对)。如果我们继续这样下去,代码将变得更加复杂,所以我不确定这是否是一个好的方法,但是性能的提升似乎非常诱人。

0 投票

评论者:michaelblume

由于展开有点复杂,为什么不让我们有一个宏来自动生成它呢?

0 投票

评论者:michaelblume

补丁v2包括关联表!

0 投票

评论者:tcrayford

我对 conj 与相似的展开进行了基准测试,跨越了从核心(列表、集合、向量,每个都为空以及包含 20 个元素的列表)的相对广泛的数据类型。

| | 1 | 2 | 3 | 4 |
| :-- | :-- | :-- | :-- | :-- | :-- |
| 未展开的空向量 | 19ns | 57ns | 114ns | 126ns |
| 未展开的空向量(展开 conj) | N/A | 44ns | 67ns | 91ns |
| | | | | |
| 20 个元素的向量(未展开) | 27.35ns | 69ns | 111ns | 107ns |
| 20 个元素的向量(展开 conj) | N/A | 54ns | 79ns | 104ns |
| | | | | |
| 空列表(未展开) | 7ns | 28ns | 53ns | 51ns |
| 空列表(展开 conj) | N/A | 15ns | 20ns | 26ns |
| | | | | |
| 20 个元素的列表(未展开) | 8.9ns | 26ns | 49ns | 49ns |
| 20 个元素的列表(展开) | N/A | 15ns | 19ns | 30ns |
| | | | | |
| 空集合(未展开) | 64ns | 170ns | 286ns | 290ns |
| 空集合(展开) | N/A | 154ns | 249ns | 350ns |
| | | | | |
| 20 个元素的集合(未展开) | 33ns | 81ns | 132ns | 130ns |
| 20 个元素的集合(展开) | N/A | 69ns | 108ns | 139ns |

基准测试是在与之前相同的机器上运行的。这里的好处不是很明显,除了列表,在这里创建seq和递归的开销似乎明显超过了实际进行conj操作的成本(这很有道理 - 对于任何元素列表的conj操作应该是一个非常便宜的运算)。原始基准输出在这里:https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

0 投票

评论者:tcrayford

Michael Blume:我喜欢这些补丁!与我的原始补丁相比,这些补丁读取起来更让我满意。你是否检查过这些宏生成的方法是否会突破Hotspot的代码内联限制?(限制为235个字节码)。这是我在这里使用宏的唯一顾虑 - 容易生成会被内联器击败的代码。

0 投票

评论者:michaelblume

谢谢!这对我是新的,所以我可能做错了什么,但我刚刚对这两个定义运行了nodisassemble,并且每行的“指令编号”分别达到了219(varargs的arity)以及251(assoc!),所以,假设我看到了正确的内容,也许那个需要一个arity来调整?如果我去掉最高arity,得到232,这是低于行数的。

我想我们可以同时将varargs的arity中的assoc!替换为assoc*,这样就可以去除很多代码 -- 在这种情况下,varargs为176,六对为149。

0 投票

评论者:michaelblume

哎呀,我忘了将coll包含在varargs的assoc!调用中。

这让我想起这个补丁需要测试。

0 投票

评论者:michaelblume

好吧,我在检查反汇编输出后对此进行了一些修改。我对assoc!*宏进行了更改,以确保它正确地发出类型提示 - 我真的很不确定为什么它之前没有正确发出类型提示,但现在它确实做到了。此外,我将varargs版本顶部前六个条目的调用从宏调用更改为函数调用,以便它能在251个可内联字节码内执行。(这再次假设我阅读了正确的输出)。

0 投票

评论者:tcrayford

迈克尔:想把这些补丁推送到Clojars或者类似的仓库吗?然后我可以使用补丁中确切的代码重新运行基准测试。

0 投票

评论者:michaelblume

嗯,不确定我是否知道如何做到这一点——不过这里有一个GitHub上的分支:[https://github.com/MichaelBlume/clojure/tree/unroll-assoc](https://github.com/MichaelBlume/clojure/tree/unroll-assoc)

0 投票

评论者:michaelblume

v5版本将辅助宏标记为私有。

0 投票

评论者:tcrayford

迈克尔:那个分支是直接基于clojure/clojure的master吗?我尝试过从这个分支运行基准测试,但在构建此代码时遇到了未定义变量的错误(在alpha5中没有出现这种情况)

(从clojars检索com/yellerapp/clojure-unrolled-assoc/1.7.0-unrollassoc-SNAPSHOT/clojure-unrolled-assoc-1.7.0-unrollassoc-20150213.092242-1.pom)
(从clojars检索com/yellerapp/clojure-unrolled-assoc/1.7.0-unrollassoc-SNAPSHOT/clojure-unrolled-assoc-1.7.0-unrollassoc-20150213.092242-1.jar)
(从central检索org/clojure/clojure/1.3.0/clojure-1.3.0.jar)
主线程中的异常 java.lang.RuntimeException: 无法在当前上下文中解析符号:bench,编译:(bench_assoc_unrolling.clj:5)

at clojure.lang.Compiler.analyze(Compiler.java:6235)
at clojure.lang.Compiler.analyze(Compiler.java:6177)
at clojure.lang.Compiler$InvokeExpr.parse(Compiler.java:3452)
at clojure.lang.Compiler.analyzeSeq(Compiler.java:6411)
at clojure.lang.Compiler.analyze(Compiler.java:6216)
at clojure.lang.Compiler.analyze(Compiler.java:6177)
at clojure.lang.Compiler$BodyExpr$Parser.parse(Compiler.java:5572)
at clojure.lang.Compiler$FnMethod.parse(Compiler.java:5008)
0 投票

评论者:michaelblume

好吧,你是如何构建的?为什么clojure组这么奇怪?

0 投票

评论者:michaelblume

现有的assoc版本在运行时会检查是否传递了偶数字数的可变参数,但assoc!不检查。我们是否想要保留这种行为,还是在两者中都进行检查?

0 投票

评论者:michaelblume

此外,我对内联在此处的相关性很好奇——在存在getRootBinding步骤的情况下,HotSpot的内联确实与Var调用一起工作吗?

...