展开向量

Question

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

这个补丁的唯一原因是为了性能，无论是在创建数据结构还是在上面执行操作。这可以被视为PersistentArrayMap溢出到PersistentHashMap中目前进行的技巧的更verbose版本。根据基准测试，可以通过克隆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

我对这个实现很感兴趣，因此创建了一个分支，将Zach的无卷向量集成到clojure 1.8.0-alpha2上。我也简化了一些代码（例如，我认为元数据处理器或无卷序列是不值得的）

Github分支： https://github.com/mikera/clojure/tree/clj-1517

然后我运行了Peter Taoussanis创建的一系列微基准测试。

结果： https://gist.github.com/mikera/72a739c84dd52fa3b6d6

我从这些测试中获得了一些发现
- 大多数测试中，性能可比较（在+/- 20%范围内）
- 在4个操作（reduce、mapv、into、相等等）中，Zach的方法明显更快（快70-150%）

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

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

Answer 3

评论者：ztellman

可能是因为无卷的reduce和kvreduce实现的改进，所以reduce方面的改进是可能的，但其他改进可能是由于无卷的临时实现的改进。为此添加的额外代码将会相当适度。

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

谢谢，干杯！:-)

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 docs： https://goo.gl/khgT83

请注意，我在Google文档中添加了一个用于您自己数据的额外工作表/标签页，您可以在以下链接找到：https://gist.github.com/ztellman/3701d965228fb9eda084。

我仍然在进行试验，试图找到表明这两个元组实现相对于微基准测试和一个小型大数据集系统的 JIT 后显著收益的结果。

看起来，JIT 实际上可能优化掉了实践中的大部分非元组低效吗？

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

有一个标准化的参考微基准测试来对照工作 definitely helped非常有用（https://github.com/ztellman/tuple-benchmark）。我是否可以建议一个类似的参考宏基准测试（可能是来自 core.matrix 或 Mike 的东西）？

定义一个值得目标性能差的操作（例如，这些在纳秒范围内的操作）或者更大的参考宏基准测试可能也是一个好主意？

这只是随便说一些想法，如果对任何人有用，请随意忽略不是很有用的任何输入；我知道你们中很多人已经深入参与了这个问题一段时间，所以请随意忽略任何没有帮助的输入 :-)

感谢所有的努力，干杯！

Answer 9

评论者：richhickey

我认为每个人都应该对这个方法降低热情。经过大量分析，我看到元组（特别是 Zach 提出的多个类方法）确实存在负面影响。在实际代码中，多个元组类会导致观察不同大小的向量的调用点变成多型的，而且没有任何充分优化。特别是，那些会看到元组尺寸和大型向量的调用点（即大量库代码）将根据它们首先看到的是哪一个而进行不同的优化。所以，如果你运行你的第一个紧密循环在看到元组的向量代码，这种代码在后续运行在大型向量上可能会比之前 JIT 补丁启用时表现更糟（50-100%）。大型集合运行速度慢是一个相对于小型集合速度快稍微一点的糟糕交易。

显然，对于 0-6 的算术运算符的不同元组类是一个死胡同。你可以从单个类中得到同样好或更好的优化（例如，一个有四个字段，覆盖大小 0-4 的类）。我在本地分支中有一个这样的工作版本。它更好，因为包含 pvectors 的站点只有二型的，但我对所见之处仍然有些紧张。

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

Answer 10

评论者：ztellman

我很确定我在 clj-tuple 中使用元组的所有实际应用都已被固定，并且没有出现任何问题。感谢你对这个想法进行测试。

Answer 11

评论者：mikera

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

我同意如果我们能避免调用点变得多态化会很好，尽管我也认为这个船已经扬帆起航了，因为已经存在多种IPersistentVector类型（MapEntry，PersistentVector，SubVector，以及clojure.core.rrb-vector等由库定义的IPersistentVector实例）。因此，JVM通常无法证明特定IPersistentVector接口调用是一元多态的，即此时发生的真正大优化。

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

为0-4个大小使用单个Tuple类是一个有趣的想法，尽管我忍不住认为性能增益可能源于大量代码做类似于(reduce conj ...)或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 （报告人ztellman）