展开小型向量

Question

正如在邮件列表（链接：1）中讨论的那样，此补丁包含两个向量和映射的展开版本，并为每个基数提供了特殊的内部类。目前，这两个都在超过六个元素之后扩展到通用数据结构的版本，这是基于粗略测试的，但可以很容易地更改。根据Rich的要求，我没有将其集成到其余的代码中，并为每个提供了顶级静态create()方法。

此补丁的唯一原因是性能，无论是在创建数据结构还是对它们执行操作方面。这可以看作是当前在PersistentArrayMap中用PersistentHashMap溢出的技巧的更详尽的版本。根据基准测试（通过克隆cambrian-collections（链接：2）并运行“lein测试：基准”可以运行），这应该取代PersistentArrayMap。性能至少与PAM相当，并且通常要快得多。最值得注意的是创建时间，对于所有大小的映射（“lein测试：only cambrian-collections.map-test/benchmark-construction”）快5倍，而对于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的方法在4个操作（reduce, mapv, into, 协同性）上明显更快（70-150%）

我认为这些额外的优化是值得的。特别是，我认为reduce和into非常重要。我也非常在乎mapv针对core.matrix（这是使用Clojure向量实现的大多数数值操作的基础）。

如果可以接受，我可以创建一个沿这些方向的补丁。

Answer 3

点评作者：ztellman

《reduce》的改进可能是由于未滚动的reduce和kvreduce实现，但其他改进可能是因为未滚动的transient实现。为此所需的额外代码相对较少。

Answer 4

点评作者：mikera

我实际上已将代码简化到一个针对Transient和TupleSeq的单一代码实现。我认为这些并不需要为每个元组类型完全展开。这有助于让代码更小巧（并且可能也有助于性能，考虑到JVM内联缓存等）。

Answer 5

评论者：ptaoussanis

大家好，

一个愚蠢的问题：目前大家是否确实有一个特定的参考基准集用于测试元组的工作？我花了一些时间才注意到我自己的微基准测试的方差有多糟糕。

提高所有运行次数直到噪声开始接近消失，我现在看到的数字似乎与其他人的数据不一致（？）。

Google文档链接： 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和Mike的1517分叉的均值运行时间和方差。可以在https://github.com/ztellman/tuple-benchmark找到，并且在https://gist.github.com/ztellman/3701d965228fb9eda084上运行的结果。

Answer 7

点评作者：mikera

嘿Zach，刚刚查看你的基准测试，它们确实与我看到的结果更一致。从我使用类似代码（例如，在vectorz-clj中处理小向量）的经验来看，整体的纳秒级时间看起来是正确的。

Answer 8

评论者：ptaoussanis

嗨Zach，谢谢！

已更新结果-
Gist: https://gist.github.com/ptaoussanis/0a294809bc9075b6b02d
Google文档: https://goo.gl/khgT83

请注意，我为您的数字添加了一个额外的电子表格/选项卡到谷歌文档中，您可以在https://gist.github.com/ztellman/3701d965228fb9eda084找到。

我还在努力生成结果，以显示在微基准测试和一个小型而重的系统（我手头有的）中，哪种元组实现都没有在JIT后的任何一致的显著效用。

在我看来，也许 JIT 实际上正在优化掉大多数非元组的低效性？

当然，我的结果可能不准确，或者我的预期可能不正确。这些数字很难确定。

有一个标准化的参考微基准测试来工作肯定有帮助（https://github.com/ztellman/tuple-benchmark）。我能否建议一个类似的参考 宏观 基准测试（也许可以从 core.matrix 或 Mike 那里找一个）？

也许还应该为这些在纳秒范围内运行的操作定义一个值得追求的性能差异目标？

这是我路过时的几点想法，如果对您有所帮助；我知道许多人已经深深地涉足其中一段时间了，所以请随意忽略任何无用的输入 :-)

感谢所有的努力，干杯！

Answer 9

评论者：richhickey

我认为大家应该对此方法的热潮稍微退一下。经过大量分析，我看到了元组（特别是 Zach 提出的多个类方法）的明确负面影响。在真实代码中，许多元组类会导致调用点在不同的向量大小之间变得巨形，没有任何操作得到足够的优化。特别是在看到元组和大型向量的调用点（即大量库代码），根据他们先看到哪个来优化不同的结果。所以，如果你在看到元组的向量代码的第一个紧循环中运行，该代码在元组修复程序安装前可能在大向量上降低 50-100% 的性能。对于小型集合来说，牺牲在大集合上运行速度较慢是不值得的。

对于 0-6 的算术，不同的元组类是一种死想法。你可以从单个类中得到同样好或更好的优化（以一些空间成本为代价），例如一个有四个字段，包括大小 0-4 的类。我在本地分支中有一个这样的版本的示例。它在包含 pvectors 的站点是双形的，但我仍然对所见的结果感到有些犹豫。

另一个教训是，微基准测试在检测这些问题方面几乎毫无价值。

Answer 10

点评作者：ztellman

我相当确定，我的所有真实世界的元组应用（通过 clj-tuple）都是固定基数，这不会引起任何此类问题。感谢对这个想法进行测试。

Answer 11

点评作者：mikera

丰富的见解——你是否有作为真实世界代码代表的基准测试？

我同意如果我们能避免调用点变成巨构体是很好的，但当我考虑到已经存在的多种 IPersistentVector 类型（如MapEntry、PersistentVector、SubVector以及库定义的IPersistentVector实例，如clojure.core.rrb-vector）时，我认为这艘船已经开了。因此，JVM通常无法证明某个具体的IPersistentVector接口调用是单态的，而这时候发生真正的优化。

在我一直在处理的大多数真实世界代码中，使用相同大小/类型的向量是反复发生的（例如：遍历map条目，工作于大小为N的向量序列），因此在这些情况下，我们应该能够依赖于多态的内联缓存做好正确的事情。

对于大小为0-4的单个元组类 ideas 很有趣，尽管我不禁想到，从性能提升来看，这很可能是因为大量代码都执行如(reduce conj ...)或transient等效的操作，这对元组来说尤其是一个糟糕的用例，至少从调用点缓存的角度来看。可能有一种更好的方法来优化这些情况，而不是单纯尝试让元组更快 ... 例如，在 Tuple0 上调用 asTransient() 可能会直接切换到 PersistentVector 实现。

Answer 12

评论者：colinfleming

这是从谷歌声云的项目中提取的一个相关的问题，他们在固定大小集合中也发现了严重的性能下降： https://github.com/google/guava/issues/1268。它有很多有趣的细节说明性能是如何崩溃的。

Answer 13

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