展开小型向量

Question

如邮件列表中讨论的（链接：1），这个补丁有两个展开的向量映射版本，每个基数都有一个特殊的内部类。目前，这两者都增长到六个元素，然后溢出到通用版本的数据结构中，这是基于粗略测试的，但可以很容易地更改。按照 Rich 的要求，我没有将其集成到其余的代码中，并且为每个提供顶级静态 create() 方法。

这个补丁的唯一直接原因是为了性能，无论是在创建数据结构还是在它们上执行操作。这可以被视为将目前使用的技巧 PersistentArrayMap 溢出到 PersistentHashMap 的一个更啰嗦版本。根据基准测试（可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来执行），这应该可以替代 PersistentArrayMap。性能至少与 PAM 相当，并且通常更快。特别值得一提的是创建时间，对于所有大小为 5 的映射（使用 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

我对这种实现很感兴趣，因此创建了一个分叉，将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》的改进可能是由于归约和kvreduce的展开实现，但是其他改进可能是由于展开瞬态实现的提升。添加这些所需的额外代码相当有限。

Answer 4

评论人：mikera

我实际上已经将代码压缩为一个针对Transient和TupleSeq的单个实现。我认为这些代码并不需要进行完全展开以适应每种元组类型。这有助于使代码变得更小（也许也有助于性能，考虑到JVM的即时内联缓存等。）

Answer 5

评论者：ptaoussanis

大家好，

一个愚蠢的问题：大家现在到底有没有一套特定的参考基准，用来测试元组上的工作呢？我花了一些时间去注意到自己的一套微观基准的方差有多糟糕。

直到噪音开始消散，我实际上看到的数据与这里的一些数据似乎不一致（?)

谷歌文档链接：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

嘿，扎克，我刚刚看了你的基准，它们确实与我看到的结果更一致。从我在类似代码（例如，在vectorz-clj中处理小向量）的经验来看，整体纳秒级的定时看起来大致正确。

Answer 8

评论者：ptaoussanis

嗨，扎克，多谢了！

我已经更新了结果-
摘要：https://gist.github.com/ptaoussanis/0a294809bc9075b6b02d
谷歌文档：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

Rich 这些见解很好 - 你是否有作为真实世界代码代表的基准测试？

我同意如果能避免调用点变得巨形态那就太好了，尽管我同时认为当考虑到已经存在的多种 IPersistentVector 类型（例如 MapEntry、PersistentVector、SubVector 以及任何库中定义的 IPersistentVector 实例，如 clojure.core.rrb-vector）时，这一点可能已经无法实现了。因此，JVM 通常不可能证明特定的 IPersistentVector 接口调用是单态的，这是真正的大优化发生的时候。

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

为大小 0-4 设计一个单一 Tuple 类的想法很有意思，尽管我不禁想到，从性能提升的角度来看，这其中的很多可能来自大量代码执行类似 (reduce conj (link: ) .....) 或其瞬态等价的操作，这对 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)（由 ztellman 报告）