展开 assoc 和 assoc! 操作以适应少量参数

Question

在最近进行的性能工作中，我发现将关联展开为单个关联调用比使用多个键要快得多（我特定应用程序的比率约为10%）。Zachary Tellman 接着指出，clojure.core 实际上根本不会展开关联，即使是相对较少键的情况。

我们已经展开了对通过 apply 调用的其他关键性能函数，例如 update https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L5914》，但是（我认为是许多应用程序和库的关键路径），可能会从中受益。

我尚未为此开发补丁，但我进行了一些独立的基准测试

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 |
| 空数组映射（展开关联） | N/A | 51ns | 80ns | 110ns |
| | | | | |
| 20个元素的持久性哈希映射（未展开） | 190ns | 313ns | 551ns | 651ns |
| 20个元素的持久性哈希映射（展开关联） | N/A | 250ns | 433ns | 524ns |
| | | | | |
| 记录（未展开） | 12ns | 72ns | 105ns | 182ns |
| 记录（展开关联） | N/A | 21ns | 28ns | 41ns |

每次测量都在一个独立的 JVM 中进行，以避免 JIT 路径依赖。

基准测试在一台常规服务器（8个 CPU、32GB 内存）上运行，使用 Ubuntu 12.04 和最近的 Java 8 版本。附上了 cpuinfo、uname 和 java -version 输出。

启用了相对标准的 JVM 生产标志，并且已采取措施禁用 leiningen 的启动时间优化（这将禁用许多 JIT 优化）。

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

对于此补丁有一个悬而未决的问题：我们应该展开多少次调用？update（在 1.7 alpha 中展开）展开为 3 个参数。增加更多展开并不困难，但这会影响关联的可读性。

补丁： CLJ-1656-v5.patch

Answer 1

评论由：tcrayford 发布

好吧，附上了 assoc.diff 文件，它将此代码展开至比当前代码多一个层级的单一级别（所以支持两个键/值对而无需递归）。如果我们继续这样下去，代码将会变得更加复杂，所以我不确定这是否是一个好的方法，但性能上的好处确实非常诱人。

Answer 2

评论由：michaelblume 发布

由于展开出来的结构有些复杂，为什么不写个宏来自动生成呢？

Answer 3

评论由：michaelblume 发布

补丁v2包含关联数组！

Answer 4

评论由：tcrayford 发布

我运行了与相似展开后的 comparable 标准测试，覆盖了从核心（列表、集合、向量，每个都为空，然后再加入20个元素）的相对广泛的数据类型。

| | 1 | 2 | 3 | 4 |
| :-- | :-- | :-- | :-- | :-- | :-- |
| 空向量（未展开） | 19ns | 57ns | 114ns | 126ns |
| 空向量（未展开的联合操作） | N/A | 44ns | 67ns | 91ns |
| | | | | |
| 20元素向量（未展开） | 27.35ns | 69ns | 111ns | 107ns |
| 20元素向量（展开的联合操作） | N/A | 54ns | 79ns | 104ns |
| | | | | |
| 空列表（未展开） | 7ns | 28ns | 53ns | 51ns |
| 空列表（未展开的联合操作） | 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 和递归的开销似乎明显地占主导地位，而这正好与联合操作的真正成本形成对比（这是合理的——在任何元素列表上的联合操作应该是一个非常便宜的操作）。原始基准测试输出在这里：https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

Answer 5

评论由：tcrayford 发布

Michael Blume：我喜欢这些补丁！它们对我来说读起来比我的原始补丁要好得多。您检查过这些宏生成的方法是否超出了Hotspot的热代码内联限制吗？（限制为235个字节码）。这将是我在这里使用宏的唯一担忧 - 容易生成被内联器破坏的代码。

Answer 6

评论由：michaelblume 发布

谢谢！这个问题对我来说是新的，所以我可能做错了，但我只运行了nodisassemble来查看两个定义，每行旁边的“指令编号” upp到219个varargs的arity关联以及up to 251个assoc!，所以，如果我是正确的，那么可能需要去掉一个arity。如果我去掉最高的arity，我得到232个varargs，这刚好低于这个界限。

我想另一种可能是我们在varargs arity中调用assoc!而不是assoc!*，这样会删除很多代码 - 在这种情况下，varargs为176，六个pair为149。

Answer 7

评论由：michaelblume 发布

啊，我忘记在assoc!的varargs调用中包含coll了。

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

Answer 8

评论由：michaelblume 发布

好的，这是我检查了反汇编输出后做的几个改进。我在assoc!*宏中做了一些改变以确保类型提示正确 - 我真的不知道为什么它之前没有正确地做类型提示，但现在它的确做了。还有，我把从顶部的六个条目到varargs版本中的assoc!的调用从一个宏调用改为一个函数调用，这样它就能适应251个可内联的字节码。（这再次是基于我对输出正确解读的假设）。

Answer 9

评论由：tcrayford 发布

Michael：你想要把这些补丁推送到clojars或其他地方吗？然后我可以使用补丁中的确切代码重新运行基准测试。

Answer 10

评论由：michaelblume 发布

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

Answer 11

评论由：michaelblume 发布

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

Answer 12

评论由：tcrayford 发布

Michael：这个分支是基于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" 中发生异常：无法在此上下文中解析符号：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)

Answer 13

评论由：michaelblume 发布

好的，你是怎么构建的？为什么clojure group那么奇怪？

Answer 14

评论由：michaelblume 发布

当前的assoc版本在运行时会检查传递了偶数个varargs，但assoc!不会。我们是否希望保留此行为或在两者中都进行检查？

Answer 15

评论由：michaelblume 发布

此外，我对内联的相关性也很感兴趣——当存在getRootBinding步骤时，HotSpot内联实际上是否支持Var调用？