展开的小向量

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}}，这还将打断其他检查向量实现内部结构的库，尽管我不了解其他任何库——当然不是任何contrib库。

还有对{{unrolled-vector.patch}}的两个评论。

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

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

Answer 2

评论者：alexmiller

Jean - 了解此补丁的影响范围将是集成此补丁的过程的一部分。我感谢你的提醒。虽然我们尽量减少此类情况造成的破坏，但可能无法避免依赖实现内部结构的库。

Answer 3

_评论者：michalmarczyk_

一旦它们到达master，我将在{{core.rrb-vector}}中添加对非扩展向量的支持。:-)（可能使用一些条件编译来避免与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

作为 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

告知各位，我们目前除了 socket repl 工作外，已经“重置”了 1.8 的所有主要功能。我们仍然可以包括它 - 这个决定将在以后做出。

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倍之大。