展开小型向量

Question

如邮件列表中所述（链接：1），此补丁有两个向量与映射的展开版本，针对每种基数有特殊的内部类。目前两者增长到六个元素后，将超出数据结构的一般版本，这基于粗略测试，但可以轻松更改。根据Rich的要求，我还没有将其集成到其余的代码中，并为每个都提供了顶级静态的create()方法。

此补丁的唯一原因是为了性能，无论是创建数据结构还是对它们执行操作。这可以被视为PersistentArrayMap溢出PersistentHashMap当前使用的技巧的更冗余版本。基于基准测试（可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来运行），这应该取代PersistentArrayMap。性能至少与PAM相当，通常更快。特别是创建时间，对于所有大小的映射都是5倍更快（运行测试：仅 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解码的基准测试，但这只是许多可能的真实世界基准测试之一。可能需要有一份 agreed-upon 列表，以便我们在讨论什么是或在不是有用的时可以使用。

Answer 2

评论者：mikera

我对这个实施方法很感兴趣，因此创建了一个分支，将 Zach 的未展开向量化集成到 clojure 1.8.0-alpha2 上。我还简化了一些代码（例如，我认为元数据处理或未展开的 seqs 没有多大意义）

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 实现，所以 reduce 的改进可能是由于 unrolled，但其他可能是因为未展开的 transient 实现带来的。实现这些所需添加的额外代码将很适度。

Answer 4

评论者：mikera

我实际上已经将代码简化为一个针对Transient和TupleSeq的实现。我认为这些代码没有必要完全展开以适应每种元组类型。这样做可以使代码更加精简（也许还有助于性能，考虑到JVM的inline缓存等）。

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

嗨，扎克，谢谢！

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

请注意，我已经在Google文档中为您的数字添加了一个额外的表格/标签，详情请见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个元素个数的不同元组类是一个已经过时的想法。您通过单一类（例如具有四个字段的类）可以获得同样好甚至更好的优化（在大小上有所牺牲）。我在本地分支有一个这样的工作版本。它更好，因为包含pvectors的位置只有二态，但对我已经有点害怕了。

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

Answer 10

评论者：ztellman

我相当肯定，我使用元组（通过clj-tuple）的所有真实世界的应用都已经被修复了固定基数，并且没有暴露出任何这样的问题。感谢您对这个想法进行了测试。

Answer 11

评论者：mikera

Rich 这些见解很好 -你是否有一个基准用来代表实际代码的效率？

我同意如果我们能避免调用点变为大规模形态会很好，但考虑到已经存在的多种 IPersistentVector 类型（MapEntry、PersistentVector、SubVector 以及任何库定义的 IPersistentVector 实例，如 clojure.core.rrb-vector），我认为在那方面已经没有什么方法了。因此，JVM 通常无法证明特定的 IPersistentVector 接口调用是同态的，而这正是发生真正大优化的地方。

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

单个 Tuple 类对于大小 0-4 感觉很有趣，但我还是认为性能提升可能更多地源于很多代码像这样做东西（reduce conj（link:）...）或者 transitory 相似，这对 Tuple 是一个特别糟糕的使用案例，至少从调用站点缓存的角度来看。可能还有更好的方法来优化这些案例，而不仅仅是尝试让 Tuple 更快。例如，在 Tuple0 上调用 asTransient() 可能直接切换到 PersistentVector 实现。

Answer 12

评论者：colinfleming

这是从 Google 的 Guava 项目的一个相关issue，他们也在固定的集合中发现严重的性能下降：[https://github.com/google/guava/issues/1268](https://github.com/google/guava/issues/1268)。有很多有趣的细节介绍了性能是如何分解的。

Answer 13

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