展开的小向量

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倍。对于哈希和相等计算以及callreduce()也有类似的收益。

这是一个很大的补丁（超过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 发布

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

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 发布

我实际上将代码压缩成针对 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 发布

嗨彼得，我无法重现你的结果，其中一些与我的预期偏差甚大，以至于我认为可能存在某些数据收集错误。例如，关联操作变得更慢几乎无法解释，因为非展开版本没有进行任何复制。此外，你所有的数字都显著慢于我的四年前旧笔记本电脑上的数字，这也很奇怪。

为了确保我们比较的是同一种 apples，我将你的基准测试修改成了一个可以打印出1.7、1.8-alpha2和Mike的1517分支的平均运行时间和方差的工具。它可以在https://github.com/ztellman/tuple-benchmark找到，运行结果在https://gist.github.com/ztellman/3701d965228fb9eda084。

Answer 7

评论由：mikera 发布

嗨Zach，刚刚看了你的基准测试，它们很确定地与我看到的一致。从我使用类似代码的经验来看，整体纳秒级时间似乎很合理（例如，在vectorz-clj中处理小向量）。

Answer 8

注释由：ptaoussanis 发表

嗨Zach，谢谢！

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

请注意，我在谷歌文档中额外添加了一个工作表/选项卡，用于您自己的数字，链接为 https://gist.github.com/ztellman/3701d965228fb9eda084。

我仍在努力产生结果，这些结果显示出对任何元组实现相对于微基准和小型高速系统（我手头现有的）的JIT后的任何一致且有意义的益处。

在我看来，可能实际上JIT优化了大部分非元组低效？

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

有一个标准化的参考微基准用于工作肯定有帮助（https://github.com/ztellman/tuple-benchmark）。我能否建议一个类似的参考 宏基准（可能是来自core.matrix，Mike提供的）？

可能还需要为这些以纳秒为时间范围运行的操作（或较大的参考宏基准）定义一个有价值的目标性能差异。

这只是某人漫步时的想法，如果它们有任何用处；知道你们许多人已经深深地参与其中一段时间了，所以请随意忽略任何无用的输入 :-)

感谢所有的努力， cheers！

Answer 9

评论者：richhickey

我认为每个人都应该减少对这个方法的热情。经过大量分析，我在元组（特别是扎克提出的多个类的方法）上看到了明显的负面影响。在实际代码中，许多元组类使得看到不同大小的向量的调用位置变成了巨形态，而没有得到足够的优化。特别是，将看到元组大小 以及 大向量的调用位置（即很多库代码）将根据它们首先看到的类型进行不同的优化。所以，如果你在看到元组的向量代码的第一个紧循环中运行，那段代码可能后来在进行大量的大型向量操作时表现得会差得多（50-100%），比在元组补丁安装之前更差。在大型集合上运行得慢是相对于在小型集合上稍微快一点的糟糕权衡。

当然，arity 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 ...)这样的操作，或者是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报告）