展开小型向量

Question

如邮件列表中讨论的（链接：1），这个补丁有两个展开的向量及映射的变种，针对每个基数有特殊的内部类。目前它们在增加至6个元素之前，会溢出到通用数据结构版本，这基于粗略的测试，但可以轻松更改。根据Rich的要求，我没有将其集成到其余的代码中，而且对于每个都提供了顶层静态 create() 方法。

这个补丁的唯一原因是为了性能，无论是创建数据结构还是对这些结构进行操作。这可以看作是当前与 PersistentArrayMap 溢出至 PersistentHashMap 所使用技巧的更详细版本。根据基准测试（通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 可运行），这应该取代 PersistentArrayMap。性能至少与 PAM 相当，并且通常更快。值得注意的是创建时间，对于所有大小的映射都是5倍更快（通过运行 'lein test :only cambrian-collections.map-test/benchmark-construction'），而对于3元组，与PAM相当，但对于5元组，则快20倍。在哈希和等价计算以及调用 reduce() 上也存在类似的好处。

这是一个很大的补丁（超过5k行），并可能很难审查。我的正确性假设基于使用 collection-check，以及底层方法非常简单的事实。尽管如此，我很乐意提供采用方法的高级描述，如果这有助于审查过程。

我希望将其融入 1.7，请告诉我我能做些什么来帮助实现这一点。

(链接：1) https://groups.google.com/forum/#!topic/clojure-dev/pDhYoELjrcs
(链接：2) https://github.com/ztellman/cambrian-collections

补丁: unrolled-vector-2.patch

筛选笔记：该方法清晰易懂。鉴于生成的代码量很大，我相信最好的方法是将此代码尽快投入使用，并将 collection-test（链接：3）添加到 Clojure 测试套件中。我还希望将生成器（链接：4）包含在 Clojure 仓库中。我们不一定需要自动运行它，但如果我们想将来修改某些东西，最好将它放在附近。

(链接：3) https://github.com/ztellman/collection-check/blob/master/src/collection_check.clj
(链接：4) https://github.com/ztellman/cambrian-collections/blob/master/generate/cambrian_collections/vector.clj

Answer 1

评论者：ztellman

“相关”性能的参考是什么？我可以提供微基准测试，例如用于计算散列，但这并不能证明它是一个重要的改进。我之前在Cheshire中提供了JSON解码的基准测试，但这只是众多可能的现实基准之一。可能有一个商定的基准测试列表是有用的，我们可以用它来辩论什么是和无用。

Answer 2

评论者：mikera

我对这个实现感兴趣，因此创建了一个分支，在clojure 1.8.0-alpha2上集成了Zach的展开向量。我还简化了一些代码（例如，我认为元数据处理或展开序列是不必要的）

GitHub分支：https://github.com/mikera/clojure/tree/clj-1517

然后我运行了由Peter Taoussanis创建的一组微基准测试

结果：https://gist.github.com/mikera/72a739c84dd52fa3b6d6

我从这次测试中发现的几点
- 大多数测试中性能相当（±20%）
- Zach的方法在四个操作（reduce，mapv，into，等价性）上的速度明显更快（70-150%）

我认为这些额外的优化是值得的。特别是，我认为reduce和into非常重要。我也非常关心mapv对于core.matrix的重要性（它是使用Clojure向量和数组执行许多数值操作的基本操作）。

如果可以接受，我将愿意按照这种路线创建补丁。

Answer 3

评论者：ztellman

很可能由于展开的reduce和kvreduce实现，reduce改进了性能，但其他改进可能是因为展开了transient实现。为了添加这些所必需的额外代码相当有限。

Answer 4

评论者：mikera

我实际上已经将代码压缩到单个对 Transient 和 TupleSeq 的实现。 我认为这些并不需要为每种元组类型完全展开。 这有助于使代码更小（而且可能也提高了性能，考虑到 JVM 内联缓存等。）

Answer 5

评论者：ptaoussanis

大家好，

这是个愚蠢的问题：大家现在到底有没有使用一套特定的参考基准来测试元组的工作？我发现我的微基准测试集性能波动很大花了一些时间才注意到。

我将所有运行次数增加到噪声开始 ~ 消失，现在我看到的数字似乎和这里别人的不一致（？）。

Google Docs 链接： https://docs.google.com/spreadsheets/d/1QHY3lehVF-aKrlOwDQfyDO5SLkGeb_uaj85NZ7tnuL0/edit?usp=sharing
基准测试的gist： https://gist.github.com/ptaoussanis/0a294809bc9075b6b02d

谢谢，干杯！:-)

Answer 6

评论者：ztellman

彼得，我无法重现你的结果，其中一些与我预期的误差很大，我必须认为存在数据收集错误。例如，关联操作变慢是难以理解的，因为未展开的版本不做任何复制，等等。此外，你的所有数字都比我4年的电脑上的慢得多，这也有些奇怪。

为了确保我们是在比较相同的东西，我已经将你的基准测试改编成了可以显示1.7、1.8-alpha2和迈克的1517分支的平均运行时间和方差。它位于 https://github.com/ztellman/tuple-benchmark，以及在 https://gist.github.com/ztellman/3701d965228fb9eda084 的一次运行的成果。

Answer 7

评论者：mikera

大家好，我刚才查看了你的基准测试，并且它们确实与我所看到的一致。从与类似代码的经验来看（例如，在 vectorz-clj中处理小向量），我从头到尾的纳秒计时看起来是正确的。

Answer 8

评论者：ptaoussanis

嗨，Zach，谢谢！

我已更新了结果 -
摘要：https://gist.github.com/ptaoussanis/0a294809bc9075b6b02d
Google文档：https://goo.gl/khgT83

请注意，我已经在Google文档中增加了一个额外的表格/标签页，您可以在其中输入自己的数据，具体可参考https://gist.github.com/ztellman/3701d965228fb9eda084。

我仍在努力产生结果，以显示任何tuple实现（针对微基准测试和手头一个较大的、以小向量为主的小型系统）在JIT后表现出的任何一致性或显著的收益。

看起来，实际上JIT可能正在优化掉大部分的非tuple低效问题？

当然，我的结果可能不正确，或者我对预期的看法可能不对。这些数字难以确定。

有一个标准的参考微基准测试来对照着做确实很有帮助（https://github.com/ztellman/tuple-benchmark）。我是否可以建议一个类似的参考宏观基准（比如core.matrix中的东西，或者Mike的？）

也许为这些在纳秒级别运行的运算定义一个有意义的目标性能差值会是好主意？（或者对于更大的参考宏观基准呢？）

以下是一些随想，仅供参考，知道很多人已经在这方面投入了很长时间，所以请随意忽略任何毫无帮助的输入 :-)

非常感谢大家的努力，干杯！

Answer 9

由 richhickey 发表的评论：

我认为每个人都应该对这个方法稍微保持点距离。经过大量的分析，我发现tuple确实存在负面影响，特别是Zach提出的多个类方法。在实际代码中，许多tuple类会使看到不同尺寸向量的调用点变为多态，并且什么都没有得到适当的优化。特别是，调用点将看到尺寸大小和大型向量（即大量库代码）将根据它们首先看到的进行不同的优化。因此，如果你首先在一个看到tuple的紧密循环上运行向量代码，那么这段代码在之后可能会比tuple补丁之前做得更差（50-100%）。对于小集合来说，在大型集合上很快并不值得换取在小集合上的稍微快一点。

当然，对于0-6个参数的tuple类的不同类别是一个淘汰的想法。你可以从单个类中获得同样好或更好的优化（代价是大小），例如具有四个字段的类，覆盖尺寸0-4。我在一个本地分支中有这个功能的一个工作副本。它在包含pvectors的调用点是双态的，但我对于我所看到的问题仍然有些犹豫。

另一个启示是，微基准测试在检测这些问题上几乎毫无价值。

Answer 10

评论者：ztellman

我非常确定我的所有关于tuple的实际应用（通过clj-tuple）都是固定的基数，不会暴露出任何这样的问题。感谢你让这个想法得到检验。

Answer 11

评论者：mikera

丰富的见解——您是否使用基准来代表实际世界代码?

我同意，如果我们能避免调用点成为巨型形态是件好事，尽管我也相信，当考虑到已经存在的多种 IPersistentVector 类型（MapEntry、PersistentVector、SubVector以及任何库定义的 IPersistentVector 实例，如 clojure.core.rrb-vector）时，这方面的船可能已经远航。因此，JVM 通常无法证明特定的 IPersistentVector 接口调用是单态的，而这正是真正的大优化发生的时候。

在我接触的大部分实际代码中，相同大小/类型的向量被反复使用（例如：遍历映射条目，处理大小为N的向量序列），因此在这些情况下，我们应该能够依靠多态内联缓存来正确地进行。

一个0-4尺寸的单个 Tuple 类的想法很令人感兴趣，尽管我不禁想到，从性能的角度来看，这种方法的性能提升可能主要来自于大量代码执行类似（reduce conj (link: ) .....) 或其瞬态等价的操作，而这对于 Tuples 来说可能是特别糟糕的使用案例。我们可能有更好的方法来优化这些案例，而不是仅仅试图使 Tuples 更快……例如，在 Tuple0 上调用 asTransient() 可能可以直接切换到 PersistentVector 实现。

Answer 12

评论者：colinfleming

这是谷歌 Guava 项目中的一个相关问题，他们发现固定大小的集合存在严重的性能下降：https://github.com/google/guava/issues/1268。其中包含很多关于性能分解的有趣细节。

Answer 13

参考： https://clojure.atlassian.net/browse/CLJ-1517 （由 ztellman 报告）