展开的小向量

Question

如邮件列表中讨论的（链接：1），此补丁有两个向量映射的不展开版本，每个基数有特殊的内部类。目前两个都扩展到六个元素，然后在结构化数据结构的通用版本中溢出，这是基于粗略测试，但可以很容易地更改。根据Rich的要求，我没有包含任何与其他代码的集成，并为每个提供了顶级静态 create() 方法。

此补丁的唯一原因是性能，无论是创建数据结构还是对它们的操作。这可以看作是 PersistentArrayMap 扩展到 PersistentHashMap 时所使用的技巧的更冗长版本。根据 benchmarks，可以通过克隆 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

_评论由：hypirion_发表的

也许应该注意到，{{core.rrb-vector}} 由于会窥视底层结构，所以在本补丁中可能会破坏小向量。这也会破坏其他窥视向量实现内部结构的库，尽管我不知道任何其他——当然不是任何其他 contrib 库。

关于 {{unrolled-vector.patch}} 的两条评论

在 Transient 类中，{{private *transient* boolean edit = true;}}
应该可能是
{{private *volatile* boolean edit = true;}}
因为 transient 在 Java 中意味着完全不同的东西。

{{conj}} 在 {{Transient}} 的实现中也可能没有问题（{{edit = false;}}）地使自身无效（即转换为 TransientVector —— 即溢出）——除非它有显著的开销。无效化可以防止一些与错误使用 transient 相关的微妙错误。

Answer 2

评论由：alexmiller

Jean - 理解此补丁的 Impact 范围将是集成过程的一部分。感谢提前通知。虽然我们试图最小化诸如此类事物的破坏性，但对于依赖于实现内部结构的库，可能不可避免。

Answer 3

_评论由：michalmarczyk_发表的

我会在 unrolled vectors 技术集成到 master 的时候支持它们。:-) （可能使用条件编译以避免与 Clojure 的早期版本不兼容——我们到时候看吧。）

Answer 4

评论由：michalmarczyk

我应该说，可以通过在线性时间内将它们倒入普通向量来为任何“类似向量”添加通用支持。乍一看，这似乎不符合库的基本承诺，但在更改真正落地之前，我会再深思熟虑。

Answer 5

评论者：ztellman

颇可预料的是，我在上次删除补丁的第二天，有人发现了一个问题（链接：1）。简而言之，我在使用ArrayChunk包装器时，两次应用了偏移量。

这个故障没有被collection-check捕获，该功能已经更新以捕获这一特定失败。然而，在Michael Blume试图将这些更改合并到Clojure时，它触发了Clojure测试套件中的大量警报，这个问题才被揭露。我自己的尝试在添加分块序列功能之前进行，因此这个问题一直持续到现在。

就像往常一样，可能还有更多问题潜伏。我希望我们能在现在和1.8之间能尽可能多地将代码展示出来。

(链接：1) https://github.com/ztellman/cambrian-collections/commit/2e70bbd14640b312db77590d8224e6ed0f535b43
(链接：2) https://github.com/MichaelBlume/clojure/tree/test-vector

Answer 6

评论者：ztellman

作为对未展开map问题中性能分析的补充，我已经运行了基准测试，并将结果发布在https://gist.github.com/ztellman/10e8959501fb666dc35e。一些值得注意的结果

• conj比通用向量的速度快3倍：https://gist.github.com/ztellman/10e8959501fb666dc35e#file-gistfile1-txt-L329-L451
• reduce + 比通用向量的速度快3倍：https://gist.github.com/ztellman/10e8959501fb666dc35e#file-gistfile1-txt-L795-L887

Answer 7

评论由：alexmiller

Stu：我认为在完成实际集成和构建工作（如果生成器被集成）之前，不应将这个补丁标记为“已审查”。

Answer 8

评论由：alexmiller

通知：我们目前暂时“重置”了1.8版本的所有大型特性（除了socket repl的工作）。我们可能仍然会包括它 - 这个决定将会稍后做出。

Answer 9

评论者：ztellman

好吧，有没有人知道什么时候会做出决定？我感到兴奋，我们似乎最终在这个问题上取得了进展。

Answer 10

评论由：alexmiller

没有，但现在它已经在我的工作列表中。

Answer 11

评论者：richhickey

我想知道所有这些对APersistentVector的重写是否都能带来重要的好处——例如，迭代器、hashCode等。

Answer 12

评论者：ztellman

在hashCode的情况下：肯定如此：https://gist.github.com/ztellman/10e8959501fb666dc35e#file-gistfile1-txt-L1013-L1076。这实际上是我最初想要加速的一部分。

在迭代器的情况下，可能不是。我可以去掉它。

Answer 13

评论者：ztellman

所以，我是从https://github.com/clojure/clojure/commit/36d665793b43f62cfd22354aced4c6892088abd6中推断出这个问题是无效的吗？如果是这样，我认为还有很多改进被留在了桌上而没有特定原因。

Answer 14

评论者：richhickey

是的，这次提交涵盖了这项功能。它采用了与补丁不同的方法，不是从小核心开始构建，而是尽可能地最大化和基础改进，而不是为每个类定义大量冗余的代码。这也允许在几乎不考虑正确性的情况下立即集成，因为新的代码很少。它还强调了元组的使用案例，例如用作不变的值的短向量，因此减轻了'可变'函数的重要性。我不同意许多必要的改进都被省略了。这个补丁对许多无关紧要的事情进行了'优化'。此外，对普遍的内联并没有很大的改进。另外，提交中还包含了补丁大小的一部分集成工作。总的来说，要使补丁符合这种方式，反而比完成所有工作需要更多的往返沟通，但我要感谢这种灵感和激发——谢谢！

Answer 15

评论者：richhickey

话虽如此，这次提交不应该是最后一句话——它可以作为进一步优化的基础。但是，我更希望它是根据需要驱动的。Clojure可能会因为优化无关紧要的事情而变得体积增大10倍。