展开小向量

Question

如邮件列表中讨论的（链接：1），这个补丁包含向量和映射的两种展开变体，每种基数都有一个特殊的内部类。目前它们都在增长到六个元素之前才溢出到普通数据结构版本，这是基于粗略测试，但可以轻松更改。在 Rich 的要求下，我没有将其集成到其他代码中，并为每个有顶层静态 create() 方法。

这个补丁的唯一原因是为了性能，既包括创建数据结构，也包括对它们进行操作。这可以被视为当前对 PersistentArrayMap 溢出到 PersistentHashMap 玩的技巧的更详尽的版本。根据可以运行 cambrian-collections（链接：2）并运行 'lein test :benchmark' 的基准测试，这应该取代 PersistentArrayMap。性能至少与 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、equality）中有显著提升（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

谢谢，再见！:-)

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。

我仍在努力生成结果，以显示TUPLE实现对微基准测试和手中的一个小型向量重系统在JIT之后带来任何一致性+显著的好处。

看起来，JIT可能实际上已经优化掉了大多数非TUPLE的低效部分？

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

有一个标准化的参考微基准测试来对比是非常有帮助的（https://github.com/ztellman/tuple-benchmark）。我能否建议一个相似的参考宏基准测试（可能是来自core.matrix的，Mike的）

也许还应该为这些在纳秒范围内运行的运算定义一个有价值的性能差异目标？

这只是过客的一些思考，如果有所助益；知道你们许多人都已经深入参与了很长时间，因此请随意忽略任何无用的反馈 :-)

感谢所有的努力，敬意！

Answer 9

评论者：richhickey

我认为每个人都应该放慢对这种方法的热衷。经过大量的分析，我看到TUPLE存在明确的负面影响，特别是Zach提出的多个类的方法。在真实代码中，大量的TUPLE类将导致不同大小向量的调用位置变得巨型，无法得到适当的优化。特别是，将看到TUPLE大小的和大型向量的调用位置（即许多库代码）将根据它们先看到的是什么进行不同的优化。所以，如果你的第一个紧密循环是向量代码，这些代码在TUPLE补丁之后可能会变得比之前糟糕（50-100%）。在大型集合上变得很慢，这是在小型集合上稍快的一个糟糕的权衡。

当然，对于0-6的arity的不同TUPLE类是一个死路。你可以从单个类中获得同样好或更好的优化（以一些大小成本为代价），例如一个有四个字段的类，覆盖大小0-4。我在本地分支有一个实现这个版本的版本。它比包含pvectors的地点更加bi-morphic，但我仍然有些草木皆兵。

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

Answer 10

评论者：ztellman

我非常确定我的所有基于TUPLE的实际应用（通过clj-tuple）都具有固定基数，并且不会出现此类问题。感谢你把这个想法运作起来。

Answer 11

评论者：mikera

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

我同意我们如果能避免调用点成为巨构的类型会是好事，尽管我也相信在已经存在多种IPersistentVector类型（如MapEntry、PersistentVector、SubVector以及任何库定义的IPersistentVector实例，例如clojure.core.rrb-vector）的情况下，这一目标已经失败了。因此，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报告）