展开的小向量

Question

如邮件列表中讨论的（链接：1），此补丁包含向量和映射的两种展开变体，每个基数都有一个特殊的内部类。目前，两者都在扩展到六个元素之前增长，然后溢出到一般版本的数据库结构，这基于大致的测试，但可以轻易更改。应Rich的要求，我没有将其包括到整个代码中，并为每个都提供了顶层静态的create()方法。

此补丁的唯一原因是性能，无论是创建数据结构还是对这些结构执行操作。这可以看作是更详尽的当前在PersistentArrayMap中溢出到PersistentHashMap的技巧的版本。基于性能测试，可以通过复制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}} 的两点评论

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

{{conj}} 在 {{Transient}} 实现中 _可能_ 会因为没有问题（{{edit = false;}}）而自行失效 – 除非它有显著的开销。这种失效可以防止与错误的 transient 使用相关的某些微妙错误。

Answer 2

评论由：alexmiller 发布

Jean - 理解这个补丁的影响范围无疑是集成过程中的一个部分。感谢提前通知。虽然我们试图尽量减少对像这样的东西的破坏，但对于依赖于实现内部细节的库，这可能不可避免。

Answer 3

_评论由：michalmarczyk 发布

一旦它们被推送到 master，我会在 {{core.rrb-vector}} 中添加对 unrolled 向量支持。:-) （可能还有一些条件编译，以避免与 Clojure 早期版本的不兼容性——当时候到了我们就会知道。）

Answer 4

评论由：michalmarczyk 发布

我必须说，通过将它们线性时间内倒入常规向量，可以为任何 "vector 类似物" 添加泛型支持。乍一看，这似乎与库的基本承诺不符，但在变化实际应用之前，我将再思考一下。

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

作为unrolled 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做出

是的，这个提交涵盖了这个功能。它在构建一个小核心的方法上与补丁有所不同，并且最大化了基础的改进，而不是在每个类中有大量的冗余定义。这也允许在不太多关注正确性的情况下立即整合，因为新的代码很少。这也强调了元组的用例，例如用作不会改变值的值的小向量，从而强调了'mutable'函数的重要性。我不认为许多必要的改进被遗漏了。补丁“优化”了许多不重要的东西。进一步，对普遍的内联并没有大的改进。此外，提交包括了与补丁大小只有一小部分的集成工作。总的来说，要将补丁与这种方法一致需要更多的来回，但我要感谢灵感和驱动 - 谢谢！

Answer 15

评论由：richhickey做出

尽管如此，这个提交不必是最后一词 - 它可以作为进一步优化的基线。但是，我更希望它是由需求驱动的。Clojure可能在优化不重要的事情上变得大10倍。