展开的小向量

Question

如邮件列表中讨论的（链接：1），此补丁包含两个展开的向量映射变体，每个基数都有特殊的内部类。目前，这两个都长到六个元素后才会溢出到数据结构的一般版本，这在粗略测试的基础上，但可以轻松更改。应 Rich 的要求，我没有将其包含到其余代码中，并且为每个都有顶级静态 create() 方法。

此补丁的唯一原因是性能，既包括创建数据结构，也包括对它们进行操作。这可以看作是当前与 PersistentArrayMap 泄漏到 PersistentHashMap 所玩技巧的更冗长的版本。根据基准测试（可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来运行），这应该取代 PersistentArrayMap。性能至少与 PAM 相当，而且通常要快得多。特别值得一提的是创建时间，对于所有大小映射（'lein test :only cambrian-collections.map-test/benchmark-construction'），它是 5 倍更快，对于 3 向量来说，与 PAM 相当，但 5 向量的速度是 PAM 的 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 非常重要。我也非常关注 core.matrix 中对 mapv 的应用（它是使用 Clojure 向量实现的许多数值操作的基础）

如果有必要，我很乐意创建一个沿着这些方向的补丁。

Answer 3

评论者：ztellman

reduce 的改进可能是由于展开的 reduce 和 kvreduce 实现，但其他改进可能是由于展开的 transient 实现引起的。这些额外代码的添加量并不大。

Answer 4

评论者：mikera

我实际上将 Transient 和 TupleSeq 的代码压缩到了一个单一流实现。我认为不需要为每个 Tuple 类型完全展开。这有助于使代码更小（并且可能也有助于性能，考虑到 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

彼得，我无法再现你的结果，其中一些与我的预期差距如此之大，以至于我必须认为在数据收集上出现了错误。例如，关联操作速度较慢是不可理解的，因为展开版本不会进行任何复制等。另外，你的所有数字都明显慢于我在四年前旧电脑上的测试，这也很奇怪。

为了确保我们在比较苹果和苹果，我已经将你的基准测试改造成了可以打印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 docs: https://goo.gl/khgT83

请注意，我已经在Google文档中为你添加了一个额外的表单标签，你可以在其中输入自己的数据，链接地址为：https://gist.github.com/ztellman/3701d965228fb9eda084。

我仍然难以生成任何一致且显著的针对tuple实施在微观基准和一个小型的vec-heavy系统上的受益结果。

在我看来，这可能意味着JIT实际上在实践中优化掉了大多数非tuple的低效问题？

当然，我的结果很可能不准确，或者我的期望错误。这些数字很难固定下来。

有一个标准化参考微观基准作为工作对照确实很有帮助（《https://github.com/ztellman/tuple-benchmark》）。我能否建议一个类似的参考《宏观》基准（比如来自core.matrix，Mike的某项工作）？

也许为这些在纳秒范围内运行的操作定义一个有价值的性能差异目标是一个好主意？（或者对于更大的参考宏观基准？）

这只是转瞬即逝的一些想法，如果对您有所帮助；既然很多人已经深深涉足其中很长时间了，因此对于任何不合理的输入，请随意忽略 :-)

感谢大家所有的努力，干杯！

Answer 9

由 richhickey 发布的评论：

我认为每个人都应该对此方法的热诚保持克制。经过大量分析，我发现tuples确实会有明确的负面影响，尤其是Zach提出的具有多个类的建议。在实际的代码中，许多tuple类会导致观察不同尺寸向量的调用位置变成巨形态的，没有任何优化得到充分针对。特别是，会看到tuple大小的调用位置及大型向量（即大量库代码）将根据它们首次看到的是什么进行不同的优化。所以，如果你在看到tuples的向量代码上运行了tight loop，那么后续的代码在大型向量上可能会比在添加tuples补丁之前表现差得多（50-100%）。在大集合上运行速度减慢是由小集合上略微加快速度进行的糟糕交易。

当然，为0-6的组合使用不同的tuple类是一个死胡同。你从一个单类中得到同样的或更好的优化（以存储大小为代价），例如一个有四个字段的单一代，它涵盖了大小0-4。我在一个本地分支中有这样一个工作的版本。它在包括pvectors的位置上只有双态性，但我仍然有点紧张，因为已经看到了这些问题。

另一个教训是，微观基准儿乎无法检测这些问题。

Answer 10

评论者：ztellman

我非常确定，我所使用的所有关于tuples的实际世界应用（通过clj-tuple）都已被解决，并且不会出现任何此类问题。感谢你把这个想法进行了检验。

Answer 11

评论者：mikera

这些见解很深刻——您是否有一个用来代表真实世界代码的基准测试？

我同意如果我们能避免调用点变成巨形是件好事，尽管我同时也认为，当我们考虑到已经存在的多重IPersistentVector类型（MapEntry、PersistentVector、SubVector以及任何库定义的IPersistentVector实例，如clojure.core.rrb-vector）时，这一轮已经结束了。结果是，JVM通常无法证明特定IPersistentVector接口调用是单态的，而这恰恰是在出现真正大优化的时候。

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

一个大小为0-4的单个元组类对于SIZE是有趣的，尽管我忍不住想到，很多性能提升可能源于许多代码做类似（reduce conj (链接： ) ……）或transient等价物的事情，这对元组来说尤其是一个糟糕的使用案例，至少从调用站点缓存的角度来看。可能有更好的方法来优化这种案例，而不仅仅是尝试使元组更快……例如，对Tuple0调用asTransient()可能直接切换到PersistentVector实现。

Answer 12

评论者：colinfleming

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

Answer 13

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