对少量参数展开 assoc 和 assoc!

Question

最近在进行性能工作的时候，我发现对于少量参数，展开单次关联调用比使用多个键要快得多（对于特定应用程序大约快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 来运行基准测试

关于这个补丁有一个悬而未决的问题：应该展开这些调用多远？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 进行了基准测试，范围包括核心数据类型（列表、集、向量，每个都是空的，然后有 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 |
| | | | | |
| 二十个元素列表（未展开） | 8.9ns | 26ns | 49ns | 49ns |
| 二十个元素列表（展开） | N/A | 15ns | 19ns | 30ns |
| | | | | |
| 空集（未展开） | 64ns | 170ns | 286ns | 290ns |
| 空集（展开） | N/A | 154ns | 249ns | 350ns |
| | | | | |
| 二十个元素集（未展开） | 33ns | 81ns | 132ns | 130ns |
| 二十个元素集（展开） | N/A | 69ns | 108ns | 139ns |

基准测试在同一台机器上运行，除了列表，这里的好处不那么明显，列表中的创建序列和递归的开销似乎明显大于 conj 的成本（这很有道理 —— 在任何元素列表上进行的 conj 应该是一个非常低廉的操作）。原始基准测试输出在这里： https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

Answer 5

评论由：tcrayford 发布

Michael Blume：我喜欢这些补丁！它们比我的原始补丁读起来好多了。你检查过这些由宏生成的任何方法是否超出了Hotspot的热代码内联限制吗？（限制为235个字节码）。这是我在这里使用宏的唯一担心——很容易生成可以被内联器击败的代码。

Answer 6

评论由：michaelblume 发布

谢谢！这件事对我来说是新的，所以我可能正在做错事，但我刚刚对两个定义都运行了 nodisassemble，每个命令行旁边的“指令编号”分别升高到219（对于varargs的arity的asso）和251（对于asso!），所以，假设我看的是正确的，可能需要删除最大的arity？如果我去掉最高的arity，我得到232个varargs，这刚好低于行。

我认为另一种选择是在varargs的arity中调用asso!，而不是asso!*，这将删除大量的代码——在这种情况下，varargs为176，六个对为149。

Answer 7

评论由：michaelblume 发布

糟糕，我忘记在varargs调用asso!中包含coll了。

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

Answer 8

评论由：michaelblume 发布

好的，这是我在检查反汇编输出后所做的某些修正。我对asso!*宏进行了一些更改，以确保它能正确类型提示——我真心不知道为什么之前无法正确类型提示，但现在可以了。此外，我将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)
主线程出现异常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版本在运行时会检查是否传递了偶数个可变参数，但assoc!并不会。我们希望保留此行为还是两项都进行检查？

Answer 15

评论由：michaelblume 发布

此外，我很想知道内联在这里的相关性 -- HotSpot内联是否确实在使用Var调用时与getRootBinding步骤协同工作？