展开的小向量

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;}}
因为Java中transient的含义完全不同。

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

Answer 2

评论者：alexmiller

Jean - 了解此补丁的影响范围将是将其集成到这一过程中的关键部分。我感谢您的提醒。虽然我们试图最小化像这样的事情的破坏，但对于依赖于实现内部结构的库，这可能无法避免。

Answer 3

_评论者：michalmarczyk_

一旦它们应用到master上，我将立即为{{core.rrb-vector}}添加对未缠绕向量的支持。:-)（很可能是通过一些条件编译来保证不与Clojure的早期版本兼容 - 我们到时候再看看。）

Answer 4

评论者：michalmarczyk

我应该指出，通过将它们倒入常规向量，可以在线性时间内为任何“看起来像向量”的东西添加通用支持。乍一看，这似乎与库的初衷不符，但在实际变动落地前，我会再思考一下。

Answer 5

回复人：ztellman

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

这一点没有被集合检查捕捉到，集合检查已经更新，可以捕捉到这个特定的失败。然而，在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的所有大型功能（除以套接字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倍。