2024 匈洲语调研调查! 分享您的想法。

欢迎!有关此功能的更多信息,请参阅 关于 页面。

+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 元素持久化 hashmap(未展开) | 190ns | 313ns | 551ns | 651ns |
| 20 元素持久化 hashmap(展开 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包括了关联数组!

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 |

基准测试在同一台机器上进行。这里除列表之外,其他的优势不是很明显,但列表似乎明确地显示创建seq和递归的开销占主导地位,从而主导了conj costs(这是有道理的——在任意元素列表上的conj应该是一个非常便宜的操作)。基准测试的原始输出在这里: https://gist.github.com/tcrayford/51a3cd24b8b0a8b7fd74

0

评论由:tcrayford

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

0

评论由:michaelblume

感谢!对我来说这是全新的,所以我可能做得不对,但我只是运行了nodisassemble来覆盖这两个定义,每一行旁边的“指令编号”都上升到了219个for varargs arity assoc和251个for assoc!,所以,假设我看到的确实是正确的,那么可能需要去掉arity的一部分?如果我移除最高arity,varargs变成232个,这正好低于行。

我想另外一种可能是我们可以在varargs arity中调用assoc!而不是assoc!*,这将删除大量代码 - 在这种情况下,varargs为176,六个对为149。

0

评论由:michaelblume

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

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

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: Unable to resolve symbol: bench in this context, 编译:(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 调用的内联?

...