展开 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 内存）上运行，使用 ubuntu 12.04 和 Java 8 的最新版本。附上了 cpuinfo、uname 和 java -version 的输出。

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

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

对于这个补丁有一个悬而未决的问题：我们应将调用展开到什么程度？在 1.7 零版本中已展开的 update 展开到 3 个参数。添加更多的展开并不困难，但这会影响 assoc 的可读性。

补丁： CLJ-1656-v5.patch

Answer 1

评论人：tcrayford

好的，附上了 assoc.diff，这个将它扩展到比当前代码更高的一个层级（因此支持两个键/值对而不需要递归）。如果我们继续这样进行，代码将变得相当复杂，所以我不确定这是否是一个好的方法，但是性能的提升看起来非常令人信服。

Answer 2

评论人：michaelblume

鉴于解卷的代码有点复杂，为什么不做一个宏来自动生成呢？

Answer 3

评论人：michaelblume

补丁v2包含了assoc！

Answer 4

评论人：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 |

基准测试是在与之前相同的机器上运行的。这里除了列表之外，其他类型的收益不太明显，对于列表，创建序号的开销以及对 conj 的递归调用似乎占据了实际 conj 成本的主导地位（这是有道理的——对任何带元素的列表的 conj 应该是一个非常廉价的操作）。原始基准输出在这里：[链接](https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74)

Answer 5

评论人：tcrayford

Michael Blume：我喜欢这些补丁！它们比我原来的补丁读起来要好得多。你检查过这些宏生成的方法中有任何触发了Hotspot的热代码内联限制吗？（限制为235字节码）。这是我使用宏的唯一担忧 - 容易生成让内联器失效的代码。

Answer 6

评论人：michaelblume

谢谢！对我来说这是新内容，我可能做错了，但是我运行了nodisassemble来检查这两个定义，并且每行的“指令号”最多增加到219，对于可变参数arity的关联项，以及最多增加到251，对于关联项！，因此，假设我看对了的话，可能需要减去一个arity？如果我将最高的arity移除，可变参数将变为232，这接近于行的限制。

我想另一种方案可能是在可变参数arity中调用关联！而不是关联!*，这样可以删除大量代码 -- 在这种情况下，可变参数为176，六个对为149。

Answer 7

评论人：michaelblume

啊，我忘记在关联！的可变参数调用中加入coll了。

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

Answer 8

评论人：michaelblume

好的，这是我在检查反汇编输出后所做的一些修改。我更改了 assoc!* 宏，以确保它正确地类型提示 - 我真的不知道为什么之前它没有正确地类型提示，但现在做到了。另外，我将 varargs 版本中顶部的前六个条目的调用从宏调用更改为函数调用，以便在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" 中 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)

Answer 13

评论人：michaelblume

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

Answer 14

评论人：michaelblume

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

Answer 15

评论人：michaelblume

此外，我对内联的关联性很感兴趣——当存在一个 getRootBinding 步骤时，HotSpot 是否真正的与 Var 调用内联一起工作？