展开小向量

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向量快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

我实际上已经将代码缩减为单个实现，用于瞬态和元组序列。我认为这些并不需要为每个元组类型完全展开。这有助于使代码更加简洁（也许也提高了性能，考虑到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

只看了你的基准测试，它们确实与我看到的一致。基于我在类似代码（例如在vectorz-clj中处理小型向量）的经验，报告的纳秒级时间看起来是正确的。

Answer 8

评论者：ptaoussanis

嗨，Zach，谢谢您的回答！

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

请注意，我在Google doc中为您添加了一个额外的表/选项卡，用于输入您的数据，可以在以下链接找到：https://gist.github.com/ztellman/3701d965228fb9eda084。

我仍在努力获得任何一致且有显著效果的基准测试结果，这些结果表现在tuple实现（针对微观基准测试和一个小型的、以小向量为主的系统）上。

看起来可能是JIT实际上在实践中优化掉了大部分非tuple的低效问题？

当然有可能我的结果是错误的，或者我的期望也是错误的。这些数字很难固定。

有一个标准的参考微观基准测试进行比较是非常有帮助的（https://github.com/ztellman/tuple-benchmark）。或许我可以建议一个类似的参考宏观基准测试（也许是从core.matrix，Mike那里）？

也许定义一个有价值的性能变化目标对于这些在纳秒范围内运行的运算（或对于更大的参考宏观基准测试）也是一个好主意？

这只是一些来自过客的想法，如果对您有所帮助，请随时忽略任何不哪有帮助的输入；我知道许多人已经在这件事上投入了很长时间，所以请随意忽略任何不利的输入 :-)

感谢大家的努力， cheers！

Answer 9

评论区由：richhickey 提出

我认为每个人都应该减少对这个方法的热情。经过大量分析，我发现tuple（尤其是Zach提出的多类方法）确实会产生负面影响。在真实代码中，许多tuple类会导致在看到不同大小向量的调用点变得多态化，没有任何东西得到有效的优化。特别是，可以看到tuple大小的和大型向量的调用点（即很多库代码），将根据它们看到的是什么进行不同的优化。所以，如果你在看到tuple的紧凑循环代码上运行第一个循环，那么这段代码可能在新版本的tuple补丁之前，对大型向量的性能会有所下降（50-100%）。对于小集合性能的提升，相对于大型集合性能的下降，是一个不好的权衡。

当然，为0-6个元数的tuple定义不同的类是一个死路。你从单类中得到同样好或更好的优化（以一些大小成本为代价），例如一个包含四个字段的类，可以覆盖大小0-4。我有一个在这个本地分支上工作的这个版本，它更好，因为使用pvectors的站点只有二态性，但鉴于我所看到的，我还有点害怕。

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

Answer 10

评论者：ztellman

我相当确定，我所有的clj-tuple的tuple应用都已经被修复了，并且不会出现任何这样的问题。感谢您对这个想法进行测试。

Answer 11

评论者：mikera

丰富的内容，您是否有一个作为实际代码代表的基准测试？

我同意如果我们可以避免调用点变成巨型多态，尽管我认为当考虑已存在的多种 IPersistentVector 类型（如 MapEntry、PersistentVector、SubVector 以及 clojure.core.rrb-vector 等）时，在这方面已经无力回天。因此，JVM 通常无法证明特定 IPersistentVector 接口调用是一致多态的，这通常是最大优化的发生时刻。

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

对于0-4个大小使用单个 Tuple 类的想法很有趣，尽管我忍不住想，性能的提升很大程度上可能源于很多代码像 (reduce conj (link: ) ...) 这样的操作或transient的等价物，这可能是 Tuple 的一个特别糟糕的使用情况，至少从调用站点缓存的角度来看。可能存在一种更好的优化此类情况的方式，而不仅仅是尝试使 Tuple 更快……例如，在 Tuple0 上调用 asTransient() 可能直接切换到 PersistentVector 实现。

Answer 12

评论者：colinfleming

以下是来自谷歌Guava项目的相关问题，他们也在固定大小的集合中发现严重性能下降：https://github.com/google/guava/issues/1268。其中包含大量有趣的细节，说明了性能如何分解。

Answer 13

参考资料：https://clojure.atlassian.net/browse/CLJ-1517（由 ztellman 提供）