展开小向量

Question

如邮件列表中讨论的（链接：1），此补丁包含两个展开的向量和map的变体，每个基数都有特殊的内部类。目前，这两个在增长到六个元素之前溢出到数据结构的一般版本，这是基于粗略测试的，但可以很容易地更改。根据Rich的要求，我没有将任何集成到其余代码中，并为每个创建了顶级静态create()方法。

此补丁的唯一原因是性能，无论是创建数据结构还是对它们执行操作。这可以被视为目前使用的PersistentArrayMap溢出到PersistentHashMap的技巧的更多字符版本。根据基准测试，可以通过克隆cambrian-collections（链接：2）并运行'lein test :benchmark'来运行，这将取代PersistentArrayMap。性能至少与PAM相似，并且通常要快得多。特别值得注意的是创建时间，对于所有大小的map（运行lein test :only cambrian-collections.map-test/benchmark-construction）快5倍，对于3向量，但对于5向量，速度几乎相同，但对于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 发表

我实际上将这些代码精简为单个用于 Transient 和 TupleSeq 的实现。我认为不需要为每个 Tuple 类型完全展开。这有助于使代码更加精简（可能也有助于性能，考虑到 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 发表

彼得，我无法重现你的结果，其中一些与我的预期相差甚远，我不得不认为在数据收集上存在一些错误。例如，关联操作变慢是有点不可思议的，考虑到扩展版不会进行任何复制等。此外，所有这些数字都比我4年前的笔记本电脑上的数字慢得多，这也是有点奇怪。

为了确保我们是在进行苹果对苹果的比较，我已经将你的基准调整为可用于显示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的结果。

我仍在努力产生结果，以展示任何在微基准测试和一个小型vec重的系统中对元组实现的JIT后的一致性+显著效益。

在我看来，可能是在实际中JIT确实优化掉了大部分非元组低效的问题？

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

有一个标准化的参考微基准来对照工作确实有帮助（https://github.com/ztellman/tuple-benchmark）。我是否能建议一个类似的参考宏基准（比如从core.matrix，Mike那里来的东西）？

也许为这些在纳秒级范围内运行的运算定义一个有价值的性能变化目标是个好主意？

这是我作为一个掠过的人的一些想法，如果他们对您有所帮助；我知道很多人已经深入研究这个问题了，所以请随意忽略任何无用的输入：）

感谢大家的努力，干杯！

Answer 9

评论者：richhickey

我认为每个人都应该减少对这个方法的热忱。经过大量分析，我看到了元组（尤其是Zach提出的多个类方法）的明显负面影响。在现实代码中，许多元组类会导致不同大小的向量的调用站点成为多态，没有任何东西得到适当的优化。特别是，那些会看到元组大小和大型向量的调用站点（即大量库代码）将根据它们看到的顺序进行不同的优化。所以，如果你在看到元组的向量代码的第一个紧密循环运行时，这段代码可能在元组补丁 application 之前在大型向量上的性能会比之前下降很多（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接口调用的单形性，这正是真正的大优化发生的时候。

在我所合作的绝大多数真实世界代码中，相同的尺寸/类型的向量会反复使用（例如：迭代map条目、处理大小为N的向量序列），因此在这种情况下，我们应该能够依赖多态内联缓存正确地完成工作。

单个Tuple类用于0-4大小的想法很有趣，尽管我不禁想到，这种性能优势的大部分可能来自于很多代码都进行类似(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报告）