展开小型向量

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 行），并且审查起来可能会有些痛苦。我的正确性假设是基于集合检查的使用以及底层方法非常简单。不过，我愿意提供关于采用的方法的高级描述，以帮助审查过程。

我希望将其纳入 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

_Comment made by: hypirion_

可能需要注意，此补丁将打破对小向量的支持，因为它会查看底层结构。这还将打破其他查看向量实现内部的库，尽管我还没有意识到任何其他，肯定不是其他contrib库。

另外，对 {{unrolled-vector.patch}} 的两个评论。

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

{{conj}} 在 {{Transient}} 实现中 _可能_ 无问题（{{edit = false;}}）地使其自身无效，如果它被转换为 TransientVector（即溢出）——除非它有显著的开销。这种失效可以防止有关错误使用 transient 的一些细微的 bug。

Answer 2

Comment made by: alexmiller

Jean - 正确理解此补丁的影响范围将是集成的过程的一部分。感谢提前通知。虽然我们试图最大限度地减少对这种情况等的破坏，但对于依赖于实现内部的库，这可能是不可避免的。

Answer 3

_Comment made by: michalmarczyk_

他们在主分支上落地时，我将立即为 {{core.rrb-vector}} 添加对非展开向量的支持。:-)（可能通过一些条件编译，以免破坏 Clojure 早期版本的兼容性——到时候再说。）

Answer 4

Comment made by: michalmarczyk

我应该说明，通过将它们转换为线性时间中的常规向量，可以添加对任何“类似向量”的通用支持。乍一看，这似乎与库的基本承诺不符，但在实际更改落地之前，我会多考虑一下。

Answer 5

评论者：ztellman

不出所料，我在实施上一个补丁的第二天，有人发现了一个问题（链接：1）。简而言之，我在使用 ArrayChunk 包装器时将偏移量应用了两次。

这没有被 collection-check 捕获，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

Comment made by: alexmiller

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

Answer 8

Comment made by: alexmiller

顺便说一句，我们暂时已经“重置”了1.8的所有大型功能（除了socket repl工作）。我们仍然可能将其包含在内——这个决定将在以后做出。

Answer 9

评论者：ztellman

好的，知道什么时候会做出决定吗？我们似乎终于在这个问题上取得了进展，我对此很兴奋。

Answer 10

Comment made by: alexmiller

不，但是现在它在我的工作列表上。

Answer 11

评论者：richhickey

我想知道所有的APersistentVector覆写是否都带来了重要好处 - 例如迭代器、哈希码等。

Answer 12

评论者：ztellman

在哈希码的情况下，绝对是：[链接](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倍。