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

欢迎!请参阅关于页面,了解更多关于这个网站如何运作的信息。

+9
Clojure

在我最近做性能工作时,我发现将单次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的最新版本。附带了cpuinfounamejava -version输出。

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

可以通过克隆存储库,然后运行script/bench来运行基准测试。

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

补丁: CLJ-1656-v5.patch

25 个回答

0

评论者:tcrayford

好吧,附上了 assoc.diff,这使得它比当前代码展开到更少的一级(因此支持不使用递归的两个键值对)。如果我们继续保持这种方式,代码将非常复杂,所以我不确定这是否是一个好的方法,但是性能提升似乎非常有说服力。

0

评论者:michaelblume

由于展开有点复杂,为什么不写一个宏来自动处理呢?

0

评论者:michaelblume

补丁版本v2包含了关联项!

0

评论者:tcrayford

对二维数列与其他数据类型(从核心的列表、集合、向量开始,每个都是空的,然后有20个元素)进行了与相似展开的比较基准测试。

| | 1 | 2 | 3 | 4 |
| :-- | :-- | :-- | :-- | :-- | :-- |
| 空向量(未展开) | 19ns | 57ns | 114ns | 126ns |
| 空向量(展开后的关联项) | 不适用 | 44ns | 67ns | 91ns |
| | | | | |
| 有20个元素的向量(未展开) | 27.35ns | 69ns | 111ns | 107ns |
| 有20个元素的向量(展开后的关联项) | 不适用 | 54ns | 79ns | 104ns |
| | | | | |
| 空列表(未展开) | 7ns | 28ns | 53ns | 51ns |
| 空列表(展开后的关联项) | 不适用 | 15ns | 20ns | 26ns |
| | | | | |
| 有20个元素的列表(未展开) | 8.9ns | 26ns | 49ns | 49ns |
| 有20个元素的列表(展开) | 不适用 | 15ns | 19ns | 30ns |
| | | | | |
| 空集合(未展开) | 64ns | 170ns | 286ns | 290ns |
| 空集合(展开) | 不适用 | 154ns | 249ns | 350ns |
| | | | | |
| 有20个元素的集合(未展开) | 33ns | 81ns | 132ns | 130ns |
| 有20个元素的集合(展开) | 不适用 | 69ns | 108ns | 139ns |

基准测试在与之前相同的机器上运行。这里的好处不是很明显,除了列表,创建序列和递归的开销似乎明显地占主导地位,这导致实际的合并成本很高(这很合理——在任意的元素列表上的合并应该是一个非常便宜的操作)。基准测试的原始输出在这里:https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

0

评论者:tcrayford

Michael Blume:我喜欢这些补丁!它们看起来比我的原始补丁好得多。你检查过这些宏生成的任何方法是否超出了Hotspot的hot代码内联限制吗?(限制是235个字节码)。这可能是我在这里使用宏的唯一担忧——很容易生成能够击败内联器的代码。

0

评论者:michaelblume

谢谢!这对我是新的,所以我可能做了错误的事,但我刚刚运行nodisassemble对两个定义进行了检查,并且每行旁边的“指令编号”增加到219个字节码为varargs arity关联,增加到251个字节码为assoc!,所以,假设我确实看对了,也许需要去掉一个arity?如果我删掉最高的arity,varargs就变成了232个字节码,刚好在行下面。

我想我们可以再叫一下assoc!而不是在varargs arity中使用assoc!*,这样就减少了很多代码——在这种情况下,varargs为176个字节码,六个pair为149个字节码。

0

评论者:michaelblume

哦,我忘了在varargs调用assoc!中包含coll。

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

0

评论者:michaelblume

好的,我在检查了反汇编输出后进行了一些修复。对assoc!*宏的改变以确保它正确类型提示——我确实不太清楚为什么之前没有正确类型提示,但现在它可以了。此外,我将varargs版本顶部前六个条目的调用从宏调用更改为函数调用,使其适合251个可内联的字节码。(这同样是我正确读取输出的假设)。

0

评论者:tcrayford

Michael:想把带有这些补丁的分支推送到clojars或其他地方吗?然后我可以用补丁中的确切代码重新运行基准测试。

0

评论者:michaelblume

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

0

评论者:michaelblume

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

0

评论者: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)
0

评论者:michaelblume

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

0

评论者:michaelblume

现有的assoc版本在运行时会检查通过的varargs是否是偶数,但assoc!则不是。我们希望保留这种行为还是在两边都进行检查?

0

评论者:michaelblume

此外,我很好奇内联在这里是否相关——在存在一个getRootBinding步骤的情况下,HotSpot内联是否真的与Var调用一起工作?

...