请分享您的想法,参加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 RAM)上运行,使用Ubuntu 12.04和Java 8的一个近期版本。附带了cpuinfounamejava -version的输出。

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

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

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

补丁: CLJ-1656-v5.patch

25回答

0

评论由:tcrayford

好吧,附上了 assoc.diff,它将这个算法展开至比当前代码多一个层级(因此可以支持不采用递归的两个键值对)。如果继续这种方式,代码将会相当复杂,因此我不确定这种方法是否可行,但是性能提升的优势非常明显。

0

评论由:michaelblume

由于展开试图相当复杂,为什么不写一个宏来自动生成它呢?

0

评论由:michaelblume

版本v2包含关联数组!

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 |

本次基准测试在同一台机器上进行。在这方面的好处不太明显,除了列表,创建seqs和递归的开销似乎明显超过了实际执行conj(这在逻辑上是合理的 - 任何元素列表上的conj应该是一个非常便宜的操作)。原始基准测试输出在此:https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

0

评论由:tcrayford

Michael Blume:我喜欢那些补丁!它们对我来说比我的原始补丁好多了。你检查过任何这些宏生成的方法是否会使Hotspot的hot code inlining限制失效吗?(限制是235个字节码)。这是我在这里使用宏的最大担忧 - 很容易生成可以抵制inliner的代码。

0

评论由:michaelblume

谢谢!这对我来说是新的,所以我可能做错了,但我刚刚运行了nodisassemble在两个定义上,并且每行的“指令数字”旁边都上升到了219个varargsarityassoc和251个assoc!,所以,假设我看对了,也许这一点需要subtract一个arity? 如果我移除最高的arity,那么varargs将变为232,刚刚低于行。

我想另一方案是,在varargsarity中调用assoc!而不是assoc!*,这会减少很多代码 - 在这种情况下,varargs为176,六个对为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 group这么奇怪?

0

评论由:michaelblume

现有的assoc版本检查传入的参数数量是偶数,但assoc!不是。我们是要保留这种行为还是要在这两种情况下都进行检查?

0

评论由:michaelblume

此外,我还想知道内联在这里的相关性如何--HotSpot在存在getRootBinding步骤时,是否能实际与Var调用内联工作?

...