展开小向量

Question

如邮件列表中所讨论（链接：1），此补丁有两个向量和映射的展开变体，每个基数都有特殊的内部类。当前这两个向量和映射在增长到六个元素之前才会溢出到数据结构的一般版本，这基于粗略测试但可以轻松更改。按照 Rich 的要求，我没有将其整合到其余代码中，每个都包含了顶级静态 create() 方法。

此补丁的唯一原因是性能，无论是创建数据结构还是在这些数据结构上执行操作。这可以看作是当前在 PersistentArrayMap 中使用的溢出 PersistentHashMap 的技巧的更详细版本。基于基准测试（可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来执行），这应该取代 PersistentArrayMap。性能至少与 PAM 相当，而且在很多情况下要快得多。特别值得注意的是创建时间，对于所有大小的映射，它是 5 倍更快（运行 lein test :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;}}
因为在Java中transient有完全不同的意义。

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

Answer 2

评论者：alexmiller

Jean - 了解这个补丁的影响范围将是整合过程的一部分。感谢您的提醒。虽然我们试图尽可能减少这方面的问题，但对于依赖于实施内部的库可能无法避免。

Answer 3

_评论者：michalmarczyk_

一旦它们合并到master，我会在{{core.rrb-vector}}中添加对unrolled向量的支持。（可能用某些条件编译，这样就不会破坏与Clojure早期版本的兼容性——到时候看吧。）

Answer 4

评论者：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

作为未展开映射问题性能分析的补充，我已经运行了基准测试，并将结果发布在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可能会因为优化无关紧要的事务而变得十倍之大。