对少量参数进行 unroll assoc 和 assoc!

Question

在最近做性能工作时，我发现对于单一 assoc 调用的展开要比使用多个键要快得多（我的特定应用程序中大约是10%）。然后 Zachary Tellman 指出，clojure.core 完全不对 assoc 进行展开，即使是相对少量的键数。

我们已经展开了一些其他通过 apply 调用的性能关键函数，例如 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 |
| :-- | :-- | :-- | :-- | :-- |
| 不展开的空数组映射 | 23ns | 93ns | 156ns | 224ns |
| 不展开的空数组映射（展开的 assoc） | N/A | 51ns | 80ns | 110ns |
| | | | | |
| 20个元素的持久哈希映射（不展开） | 190ns | 313ns | 551ns | 651ns |
| 20个元素的持久哈希映射（展开的 assoc） | N/A | 250ns | 433ns | 524ns |
| | | | | |
| 记录（不展开） | 12ns | 72ns | 105ns | 182ns |
| 记录（展开的 assoc） | N/A | 21ns | 28ns | 41ns |

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

基准测试在一台通用服务器（8 个 CPU，32GB RAM）上运行，使用 ubuntu 12.04 和 Java 8 的最新版本。附上 cpuinfo、uname 和 java -version 的输出。

启用了相对标准的 JVM 生产力标志，并尽心尽力地禁用了 leiningen 的启动时间优化（这会禁用许多 JIT 优化）。

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

对于这个补丁有一个悬而未决的问题：我们应该展开到多少参数？update（它在 1.7 预览版中展开）展开到 3 个参数。进一步展开并不困难，但这会影响 assoc 的可读性。

补丁： CLJ-1656-v5.patch

Answer 1

评论由：tcrayford 发布

好吧，附上了 assoc.diff，将其展开成比当前代码多一个级别的单一层（因此支持不递归的前两个键/值对）。如果我们继续这样下去，那么代码将变得非常复杂，所以我不确定这是否是一个好的方法，但是性能提升似乎非常有吸引力。

Answer 2

评论由：michaelblume 发布

由于展开的内容有点复杂，为什么不让我们用一个宏来自动写它呢？

Answer 3

评论由：michaelblume 发布

补丁 v2 已包含 assoc！

Answer 4

评论由：tcrayford 发布

我对 conj 进行了基准测试，其展开与类似的展开相似，跨越了从核心（列表、集合、向量，每个都是空的，然后 again with 20 elements）相对较广泛的 datatypes。

| | 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 |

基准测试在同一家机器上运行。除了列表之外，这里的好处不是很明显，因为创建 seqs 和递归的开销似乎明显地占主导地位，这影响了 conj 的实际开销（这很合理 - conj 任何元素列表的操作应该是一个非常便宜的操作）。原始基准测试输出在此：https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

Answer 5

评论由：tcrayford 发布

迈克尔·布卢姆：我喜欢这些补丁！它们读起来比我最初的补丁要顺眼得多。你检查过这些由宏生成的任何方法是否超出了Hotspot的热代码内联限制吗？（限制为235字节码）。这就是我在这里使用宏的唯一担忧——生成能够击败内联器的代码很容易。

Answer 6

评论由：michaelblume 发布

谢谢！这对我说是个新问题，所以我可能做了不对的事情，但我刚刚运行了nodisassemble来检查这两个定义，每一行旁边的“指令号码”都达到了219（varargs的可变数目关联）和251（assoc!），所以，假设我看着的是对的，可能需要去掉一个arity。如果我去掉最高的arity，varargs会得到232，这正好在行下面。

我想另一个选择是在备份的arity中使用assoc!代替assoc*，这将删除大量代码——在这种情况下，varargs是176，六个配对是149。

Answer 7

评论由：michaelblume 发布

哎呀，我在调用assoc!时忘了include coll。

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

Answer 8

评论由：michaelblume 发布

好的，这是在检查反汇编输出后做的几个修正。我修改了assoc!*宏，以确保它正确提示类型——我确实不确定为什么它以前不能正确提示类型，但现在可以了。此外，我将varargs版本顶部前六个条目的调用从宏调用改为函数调用，以便在251个内联字节码内。（这又假设我正确阅读了输出）。

Answer 9

评论由：tcrayford 发布

迈克尔：想将这组补丁推送到clojars或其他地方吗？这样我就可以使用补丁中的确切代码重新运行基准测试。

Answer 10

评论由：michaelblume 发布

嗯，我不确定我是否知道如何做这件事 —— 不过这里有一个github上的分支 https://github.com/MichaelBlume/clojure/tree/unroll-assoc

Answer 11

评论由：michaelblume 发布

v5版本将辅助宏设置为私有。

Answer 12

评论由：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)
在主线"main"中抛出异常 java.lang.RuntimeException: Unable to resolve symbol: bench in this context, 编译：(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)

Answer 13

评论由：michaelblume 发布

好吧，你是如何构建的？为什么clojure group这么奇特？

Answer 14

评论由：michaelblume 发布

现有的assoc版本在运行时会检查传入的varargs是否为偶数，但assoc!不会。我们是否希望保留这种行为还是在两者都进行检查？

Answer 15

评论由：michaelblume 发布

此外，我很想知道内联在这里的相关性怎么样 —— 当存在一个 getRootBinding 步骤时，HotSpot 的内联是否真的与 Var 调用一起工作？