展开小向量

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

屏幕说明：方法清晰易懂。鉴于生成的代码量很大，我相信最好的方法是尽快让人们使用它，并将 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}} 在小向量上中断，因为它检查了底层结构。这还将破坏其他检查向量实现内部结构的库，尽管我不了解任何其他的——当然不是任何其他的贡献库。

另外，对 {{unrolled-vector.patch}} 的两点评论：

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

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

Answer 2

评论者：alexmiller

Jean - 了解此补丁的潜在影响范围将是整合此补丁过程中的一个部分。感谢提醒。虽然我们尽量减少此类问题的影响，但对于依赖实现内部结构的库而言，这可能不可避免。

Answer 3

_评论者：michalmarczyk_

一旦 unrolled vectors 登陆到 master，我会为 {{core.rrb-vector}} 添加对它们的支持。:-)（可能通过一些条件编译，以便在不破坏与 Clojure 早期版本兼容性的情况下进行——到时候我们就知道了。）

Answer 4

评论者：michalmarczyk

我应该说明，在线性时间内将这些“类似向量”倒入常规向量中，可能会支持任何类型的“类似向量”。乍看之下，这似乎与库的基本承诺不符，但在我实际做出更改之前，我会再思考一下。

Answer 5

评论者：ztellman

不出所料，我在切掉之前的补丁后一天，有人发现了一个问题（链接：1）。简而言之，我对ArrayChunk包装器使用中应用了两次偏移量。

这没有被collections-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

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