展开小型向量

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

筛选说明：该方法清晰易懂。考虑到生成的代码量很大，我认为提高对这代码的信心最好的方式是尽快让人们使用它，并将 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_

当他们着陆到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

作为对未展开向量问题中性能分析的补充，我已经运行了基准测试并发布了结果在 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 评论

我想知道是否所有的@Override 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 评论

是的，这个提交包含了这个功能。它从一个小核心构建，与补丁不同，最大化对基础的改进，而不是在每个类中有大量的冗余定义。这也允许立即集成，而无需过多的关注正确性，因为新代码很少。它还强调了元组的使用案例，例如作为不会改变的值的small vectors，从而降低了 '可变' 函数的重要性。我不同意很多必要的改进被忽视。这个补丁 '优化'了许多不重要的事情。此外，对于普遍的内联没有太大的改进。另外，该提交整合的工作量只是补丁的一小部分。总的来说，要使补丁符合这种方法，会比直接完成任务花费更多的时间和精力，但我感激您的启发和推动 - 谢谢！

Answer 15

由：richhickey 评论

尽管如此，这个提交不需要成为最后一句话 - 它可以作为进一步优化的基准。但我更倾向于由需求驱动。Clojure可以变得很大，因为它优化了那些不重要的事情。