Clojure 2024 调查问卷!中分享您的想法。

欢迎!请查看关于页面以获取更多有关该功能的信息。

+9
Clojure

在最近进行性能工作时,我发现将单次关联调用展开相较于多次使用多个键要快很多(对我来说大约是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 的最新版本。附上 cpuinfounamejava -version 的输出。

启用了相对标准的 JVM 生产标志,并注意禁用 leiningen 的启动时间优化(这将禁用许多 JIT 优化)。

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

对于此补丁有一个未解决的问题:我们应该展开这些调用的范围有多远?update(在 1.7 零版本中展开)展开为 3 个参数。添加更多展开并不困难,但这会影响到 assoc 的可读性。

补丁: CLJ-1656-v5.patch

25 个答案

0

评论由:tcrayford 撰写

好吧,附上了 assoc.diff,它将此内容展开到比当前代码多一个层级(因此支持两个键/值对而不使用递归)。如果我们继续这样下去,代码将会变得非常复杂,所以我不确定这是否是一个好的方法,但性能优势似乎非常有说服力。

0

评论由:michaelblume 撰写

由于展开变得有点复杂,为什么不用宏来自动编写呢?

0

评论由:michaelblume 撰写

补丁v2包括assoc!

0

评论由: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)操作的代价(这很有道理——对任何元素列表中的合取操作都应该是一个非常廉价的操作)。原始的基准测试输出在这里:https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

0

评论由:tcrayford 撰写

迈克尔·布卢梅:我喜欢这些补丁!它们比我的原始补丁读起来要好得多。你检查了那些由宏生成的方法是否超出了Hotspot的hot代码内联限制吗?(为235个字节代码)。这对我来说是使用宏的唯一担忧——生成的代码可能会使内联失效。

0

评论由:michaelblume 撰写

感谢!这对我来说是个新话题,所以我可能做错了,但我只是对两个定义进行了nodisassemble处理,并且每行的“指令编号”旁边升高到219(varargs arity的关联)和高达251(!关联),所以,假设我看对了的话,也许其中一个需要减少一个arity?如果我去掉最高的arity,我会得到232(varargs),这正好在行下面。

我想另一个选择就是在varargs arity中调用!关联而不是*关联,这可以删除大量代码—在这种情况下,varargs为176,六对为149。

0

评论由:michaelblume 撰写

糟糕,我忘了包括varargs中的coll在!关联调用的参数中。

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

0

评论由:michaelblume 撰写

好的,我对分析后的输出进行了一些修正。对!*关联宏进行了更改,以确保它正确类型提示——老实说我不知道为什么它之前没有正确类型提示,但现在确实正确了。此外,我将varargs版本顶部前六个条目的调用从宏调用更改为函数调用,这样它就可以适应251个可内联的字节码。(这再次假设我正确解读了输出)。

0

评论由:tcrayford 撰写

迈克尔:想把这些补丁推送到 clojars 或者其他地方吗?这样我就可以用补丁中的确切代码重新运行基准测试。

0

评论由:michaelblume 撰写

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

0

评论由:michaelblume 撰写

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

0

评论由: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
主线程中出现异常 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)
0

评论由:michaelblume 撰写

好的,你是如何构建的?为什么 clojure group 那么奇怪?

0

评论由:michaelblume 撰写

现有的 assoc 版本在运行时会检查是否有偶数个 varargs 被传递,但 assoc! 则不会。我们是要保留这种行为,还是同时在两边进行检查?

0

评论由:michaelblume 撰写

此外,我对内联的相关性很感兴趣--在存在获取根绑定步骤的情况下,HotSpot 内联是否真的与 Var 调用一起工作?

...