展开的小向量

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向量与它们相当，但对于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个操作上明显更快（减少70-150%），操作包括reduce、mapv、into、平等

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

如果可以接受，我很乐意创建相应的补丁。

Answer 3

评论由：ztellman

减少（reduce）的改进可能是由于非折叠的reduce和kvreduce实现，但其他的是因为非折叠瞬态实现。添加这些所需额外的代码量相当有限。

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

Peter，我无法重现你的结果，其中一些与我的预期差距甚远，我必须认为存在数据收集错误。例如，关联操作变慢是不可解释的，因为未展开的版本没有进行任何复制等操作。此外，所有数字都比我四年前老的笔记本电脑慢得多，这也是有点奇怪。

为了确保我们是在比较相同的事物，我将你的基准测试进行了修改，以展示1.7，1.8-alpha2和Mike的1517分支的均值运行时间和方差。可以在https://github.com/ztellman/tuple-benchmark找到，运行结果在https://gist.github.com/ztellman/3701d965228fb9eda084。

Answer 7

评论由：mikera

Hey Zach，我刚刚看了你的基准测试，它们确实与我所看到的更一致。从我有相似代码（例如在vectorz-clj中处理小向量）的经验来看，整体纳秒时间看起来是正确的。

Answer 8

评论由：ptaoussanis发表

Hi Zach，谢谢！

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

注意，我已经在Google文档中添加了一个额外的表格，其中包含你在https://gist.github.com/ztellman/3701d965228fb9eda084的数字。

我还在努力制作出能展示增值后的一致性增强效果的结果，无论是对比微基准测试中的元组实现，还是我手头的一个大型小矢量关注系统。

在我看来，也许实际的JIT优化已经在实践中排除了大部分非元组低效之处？

当然，我的结果很可能不准确，或者我对结果的预期有误。数字很难确定。

拥有一个标准的参考微基准测试非常有帮助（https://github.com/ztellman/tuple-benchmark）。我能建议一个类似的参考宏基准测试吗（比如来自core.matrix，Mike的某个东西）？

也许为这类在纳秒范围内运行的操作定义一个有价值的性能改进目标是一个好主意？

这只是我的一些想法，仅供参考；知道你们中的很多人已经在这上面投入了很多时间，所以请随意忽略任何无用的意见 :-)

感谢大家的努力，干杯！

Answer 9

评论者：richhickey

我认为所有人都应该稍微放慢对这个方法的热情。经过大量的分析，我发现在元组上确实有明确的负面影响，特别是Zach提出的多重类方法。在实际代码中，许多元组类会导致调用点在不同大小的矢量之间成为多态的，而没有得到足够的优化。特别是那些会看到元组大小和大型矢量的调用点（即大量的库代码）将根据它们首次遇到的类型进行不同的优化。所以，如果你在一个看到 tuples 的向量代码上运行了一个紧密的循环，那段代码后来在大矢量上的性能可能会大幅下降（50-100%），比 tuples 补丁出现之前还要差。在大型数组上运行得慢是一个糟糕的权衡，以换取在小型数组上略有提升。

当然，对于 0-6 的情况的不同元组类是一个已经失败的想法。使用单一类（例如，拥有四个字段的类，覆盖大小范围 0-4）可以获得同样或更好的优化（以一些体积损失为代价）。我在一个本地分支上有这个功能的实现版本。它在包含 pvectors 的站点上只具有双态性，但我仍然有些紧张，因为我看到了这些问题。

另一个教训是微基准测试几乎无法检测这些这些问题。

Answer 10

评论由：ztellman

我很确定我所有的通过 clj-tuple 使用的元组（具有固定的基数）都没有出现任何问题。感谢大家对这个想法的实际测试。

Answer 11

评论由：mikera

Rich，这些是很好的见解 - 你有一个你用作代表实际代码的基准测试吗？

我认为如果我们能够避免调用站点出现 megamorphic（巨大变形）的情况是很好的，尽管考虑到已经存在的多种 IPersistentVector 类型（例如 MapEntry、PersistentVector、SubVector 以及任何库定义的 IPersistentVector 实例，如 clojure.core.rrb-vector），我认为这方面的船已经开走了。因此，JVM 通常无法证明特定的 IPersistentVector 接口调用是 monomorphic 的，这时才会出现真正的优化。

在我处理的大部分现实世界代码中，相同的尺寸/类型的向量会被重复使用（例如：遍历映射条目、处理大小为 N 的序列），因此在这种情况下，我们应该能够依赖多态的内联缓存来正确地完成工作。

为 0 到 4 的大小使用单个 Tuple 类很有趣，但我忍不住想，从性能提升的角度来看，这可能更多地来源于许多代码都做类似 (reduce conj (link: )).. 或者 transient 等价的操作，这对 Tuple 来说是一个特别糟糕的使用场景，至少是从调用站点缓存的角度来看。可能有一种更好的方法来优化这种场景，而不是简单地尝试让 Tuple 更快……例如，对 Tuple0 调用 asTransient() 可能会直接切换到 PersistentVector 实现中。

Answer 12

评论者：colinfleming

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

Answer 13

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