展开的小向量

Question

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

此补丁的唯一原因是性能，无论是创建数据结构还是对其执行操作。这可以看作是当前用PersistentArrayMap溢出到PersistentHashMap所玩技巧的更详尽的版本。根据基准测试，可通过复制cambrian-collections（链接：2）并运行'lein test :benchmark'来运行，这应该取代PersistentArrayMap。性能至少与PAM相当，并且通常要快得多。值得注意的是，创建时间对于所有大小的映射至少是5倍（运行测试：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

筛查说明：方法清晰易懂。考虑到生成的代码量很大，我相信最佳方法是通过尽早让人们使用它来提高对此代码的信心，并将集合测试（链接：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的非展开向量。我还简化了一些代码（例如，我认为元数据处理或非展开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的改进可能是由于非展开的reduce和kvreduce实现，但其他可能是由于非展开的transient实现。为此添加的额外代码将相当少。

Answer 4

评论者：mikera

我实际上将代码精简成一个针对Transient和TupleSeq的单个实现。我认为这些并不真正需要为每个Tuple类型完全展开。这通过使代码变得更小（并且很可能也有助于性能，考虑到JVM内联缓存等）来帮助。

Answer 5

评论由：ptaoussanis

大家好，

问一个愚蠢的问题：现在人们是否真的在用某一组特定的参考基准来测试tuple的工作？我花费了一些时间去注意我自己的微基准测试中存在的差异。

所有运行次数一直增加，直到噪声开始慢慢消失，我现在看到的数据似乎与其他人这里的数据不符（？）。

Google Docs链接： https://docs.google.com/spreadsheets/d/1QHY3lehVF-aKrlOwDQfyDO5SLkGeb_uaj85NZ7tnuL0/edit?usp=sharing
基准测试的 gist 链接： https://gist.github.com/ptaoussanis/0a294809bc9075b6b02d

谢谢， cheers! :-)

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

嗨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的？

也许为这些以纳秒级运行的算术操作定义一个有意义的性能改进目标是好主意？

这只是路过时的一些想法，如果它们有一点用处；知道许多人都已经深深涉足其中一段时间了，所以请不要拒绝任何没用的想法:-)

感谢所有努力，干杯！

Answer 9

评论者：richhickey

我认为每个人都应该对这个方法的热情降温。经过大量的分析，我看到了 tuple 的一些明确的负面影响，特别是 Zach 提出的多个类方法。在实际代码中，许多 tuple 类会让看到不同尺寸向量的调用站点变成多态的，而什么也不会得到足够优化。特别是那些将看到元组尺寸和大型向量的站点（即大量的库代码）会根据它们看到的顺序不同而分别优化。所以，如果你第一次对看到元组的向量代码进行紧凑循环，那么该代码可能会在 tuples 补丁到位之前变得糟糕得多（50-100%）。在小集合中略微更快并不是在大型集合中变慢的好交易。

当然，对于 0-6 个参数的不同的 tuple 类是一个过时的想法。你可以通过单个类获得相当或更好的优化（以一些大小的损失为代价），例如一个有四个字段的单例，覆盖尺寸 0-4。我在一个本地分支中有一个这样的工作版本。它更好，因为包含 pvectors 的站点只有双态，但我仍然有些犹豫，因为我已经看到了这些。

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

Answer 10

评论者：ztellman

我相当确定，我所有使用 tuples 的实际应用程序（通过 clj-tuple）都是固定容量的，没有出现任何这样的问题。感谢对这个想法进行了测试。

Answer 11

评论者：mikera

Rich, 这些见解很好 - 你是否有用作现实世界代码代表性的基准测试？

我同意如果我们可以避免调用点成为巨形化是很棒的，但考虑到已经存在的多个IPersistentVector类型（例如MapEntry, PersistentVector, SubVector以及clojure.core.rrb-vector等库定义的IPersistentVector实例），我认为这艘船已经离去了。因此，JVM通常无法证明特定IPersistentVector接口调用是单态的，这才是真正大的优化发生的时候。

在我几乎所有的真实世界代码工作中，相同的尺寸/类型的向量被重复使用（例如：迭代map项，处理尺寸为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报道）