请在 2024 年 Clojure 状态调查! 分享您的想法。

欢迎!请查看 关于 页面了解更多关于此功能的信息。

+9
Clojure

在最近进行性能工作时,我发现将单个 assoc 调用展开到比使用多个键快得多(对于我的特定应用来说大约快10%)。Zachary Tellman 然后指出 clojure.core 实际上根本不会对 assoc 进行展开,即使是相对较低的键的数量。

我们已经展开了其他调用的性能关键函数,例如 update(例如,在 1.7 测试版中已展开到 3 个参数),但 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 测试版中展开到 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 |

基准测试是在之前同一台机器上运行的。在这里,除了列表外,优势并不明显,因为创建seqs和递归的开销似乎明显超过了执行conj的成本(这是有道理的 - 在任何元素列表上的conj应该是一个非常便宜的操作)。原始基准输出在这里:[https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74](https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74)

0

评论者:tcrayford

Michael Blume:我喜欢这些补丁!它们看起来比我最初的补丁要好得多。你检查过这些由宏生成的任何方法是否超出了Hotspot的hot code inlining限制吗?(限制为235个字节码)。这将是我在这里使用宏的唯一担忧 - 容易生成可以打败inline器的代码。

0

评论者:michaelblume

谢谢!这件事对我来说很新,所以我可能做错了,但是我刚刚在两个定义上运行了nodisassemble,每行的“指令编号”旁边增加到219,对于varargs的可变参数arity关联,增加到251对于 assoc!,所以,如果假设我在看正确的东西,也许那个参数需要减掉一个arity?如果我去掉最高的arity,我就得到了232个varargs,这正好低于15行。

我想,我们可以用assoc!代替varargs arity中的assoc!*,这将移除大量代码 -- 那种情况下,它对于varargs是176,对于六个对是149。

0

评论者:michaelblume

哎呀,我忘记在varargs调用assoc!时包含coll了。

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

0

评论者:michaelblume

好的,我已经在检查反汇编输出后对一些地方进行了修复。我修改了assoc!*宏以确保正确的类型提示 - 我真的不确定为什么之前没有正确地进行类型提示,但现在它做了。此外,我将varargs版本中顶部六个条目的调用从宏调用更改为函数调用,以便在251个可内联的字节码内 fit。(这再次假设我阅读输出正确)。

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)
异常:无法在当前上下文中解析符号: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

此外,我很想知道在这种情况下内联的相关性有多大——当有getRootBinding步骤在进行时,HotSpot内联实际上能够与Var调用一起工作吗?

...