展开小型向量

Question

如邮件列表（链接：1）上所讨论的，此补丁有两个展开向量和映射的变体，并为每个基数提供了特殊内部类。目前，两者都在增长到六个元素之前扩展到常规数据结构版本，这是基于粗略测试的，但可以很容易地更改。应 Rich 的请求，我没有将其集成到其他代码中，并且为每个都提供了顶级静态 create() 方法。

此补丁的唯一理由是性能，无论是创建数据结构还是对其执行操作。这可以被视为将 PersistentArrayMap 扩展到 PersistentHashMap 中使用的特技的更详尽版本。根据基准（可通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 以运行），这应该会取代 PersistentArrayMap。性能至少与 PAM 相当，并且通常要快得多。特别值得注意的是创建时间，对于所有大小的映射而言，其速度是 PAM 的 5 倍（运行 lein test :only cambrian-collections.map-test/benchmark-construction），但对于 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发表

我对这个实现很感兴趣，所以我创建了一个分支出于Zach的无环向量的Clojure 1.8.0-alpha2之上。我还简化了一些代码（例如，我认为元数据处理或无环序列不值得

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

谢谢， cheers！ :-)

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

嗨，扎克，谢谢你！

已更新结果 -
Gist链接：https://gist.github.com/ptaoussanis/0a294809bc9075b6b02d
Google docs链接：https://goo.gl/khgT83

请注意，我在Google文档中为您添加了一个额外的表格，用于输入自己的数据，链接为https://gist.github.com/ztellman/3701d965228fb9eda084。

我仍在努力产生结果，以证明任何与元组实现相关的、具有一致性和显著性低于JIT的益处，无论是针对微基准测试还是我所掌握的另一个大型小型vec系统。

在我看来，这可能意味着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发表

Rich，这些见解很好——你是否有使用作为现实世界代码代表的基准？

我同意，如果我们能避免调用点变成巨大形态，那就太好了。然而，考虑到已经存在的多种IPersistentVector类型（MapEntry、PersistentVector、SubVector以及任何库定义的IPersistentVector实例，如clojure.core.rrb-vector），我认为这一艘船已经远航。因此，JVM通常无法证明特定IPersistentVector接口调用是单态的，这正是实现真正重大优化的地方。

在我接触的绝大多数现实世界代码中，相同的大小/类型的向量被反复使用（例如：遍历映射条目、处理大小为N的向量序列），因此在这种情况下，我们应该能够依赖多态内联缓存来做正确的事情。

对于大小0-4的单个元组类很有趣，尽管我不禁想到，从这个方面来说，性能提升可能来自于很多代码都做一些像(reduce conj ...)或transient等效的事情，这对于元组来说尤其是糟糕的使用案例，至少从调用站缓存的角度来看。可能有一种更好的方法来优化这些情况，而不仅仅是为元组加速……例如，在Tuple0上调用asTransient()可能可以直接切换到PersistentVector实现。

Answer 12

评论来自：colinfleming

以下是来自谷歌Guava项目的一个相关问题，他们也在固定大小的集合中发现了严重的性能下降：[雷 次 处/ray m.php/ ...](https://github.com/google/guava/issues/1268)。这里有许多有趣的细节，关于性能如何崩溃。

Answer 13

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