为少数几个参数展开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

Patch v2 包含了 assoc！

Answer 4

评论者：tcrayford

我用类似展开的方式对核心数据类型（列表、集合、向量）进行了基准测试，涵盖了从空（然后是包含20个元素的）到相对广泛的数据类型

| | 1 | 2 | 3 | 4 |
| :-- | :-- | :-- | :-- | :-- | :-- |
| 空向量（未展开） | 19ns | 57ns | 114ns | 126ns |
| 空向量（展开后conc） | N/A | 44ns | 67ns | 91ns |
| | | | | |
| 20个元素的向量（未展开） | 27.35ns | 69ns | 111ns | 107ns |
| 20个元素的向量（展开后conc） | N/A | 54ns | 79ns | 104ns |
| | | | | |
| 空列表（未展开） | 7ns | 28ns | 53ns | 51ns |
| 空列表（展开后conc） | 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 |

基准测试在之前的同一台机器上运行。这里的优势不是特别明显，除了列表之外，创建seqs和递归的开销似乎明显超过了实际执行 Conj 的成本（这是有道理的——对任何元素列表的联合操作应该是一个非常便宜的运算）。原始基准测试输出在此：https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

Answer 5

评论者：tcrayford

Michael Blume：我喜欢这些补丁！它们比我原来的补丁读起来要好得多。你检查过那些宏生成的方法是否超出了Hotspot的热代码内联限制了吗？（限制为235个字节码）。我对此处的宏使用有点担心——容易生成被内联器抵消的代码。

Answer 6

评论者：michaelblume

谢谢！这对我是新鲜的，所以我可能正在做错事，但我只是运行了nodisassemble来查看这两个定义，每个语句旁边的“指令编号”都达到了219（对于变元个数的assoc）和251（对于assoc!），所以，如果我的观察是正确的，可能需要减去一个arity。如果我去掉最大的arity，变元个数的数字是232，略低于线。

或者，我们可以在变元个数中用assoc!代替assoc!*，这样可以移除很多代码——在这种情况下，变元个数为176，六个对为149。

Answer 7

评论者：michaelblume

哦，我忘记在变元个数的assoc!调用中包含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)
主线程中发生异常 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 调用配合工作？