展开小向量

Question

如邮件列表中讨论的那样（链接：1），这个补丁包括向量和映射的两个展开变体，并为每个基数配备了特殊的内部类。目前，两个都扩展到六个元素，然后溢出到基于测试的通用数据结构版本，这可以根据需要轻松更改。根据Rich的要求，我没有将其集成到其余代码中，并且为每个都有一个顶级静态的create()方法。

这个补丁的唯一原因是性能，无论是在创建数据结构还是在操作它们时。这可以看作是当前在PersistentArrayMap溢出到PersistentHashMap所使用的技巧的更详细版本。基于基准测试，可以通过克隆cambrian-collections（链接：2）并运行'lein test :benchmark'来运行这些基准测试。这应该会取代PersistentArrayMap。性能至少与PAM相当，通常要快得多。特别是创建时间，对于所有大小的映射都是5倍更快（运行测试：仅 cambrian-collections.map-test/benchmark-construction），而对于3向量与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}}中的unrolled vectors。:-) （可能需要一些条件编译，这样就不会破坏与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版本的所有大功能（除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 在优化一些不重要的地方可能会膨胀10倍。