未展开的小向量

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;}}
在Transisent类中可能应该改为
{{private *volatile* boolean edit = true;}}
因为在Java中transient意味着完全不同的东西。

{{conj}}在{{Transient}}实现中_{不}_会因任何问题（{{edit = false;}}）而使自身无效——除非它具有明显的开销。无效化可以防止一些与错误透时使用相关的微妙错误。

Answer 2

评论者：alexmiller

Jean - 了解该补丁的适用范围将是集成此补丁过程的一部分。我感谢你的提醒。虽然我们试图最大限度地减少诸如此类东西的破坏性，但对那些依赖于实现内部机制的库来说，这可能不可避免。

Answer 3

评论者：michalmarczyk

它们一旦包含在master中，我就会支持{{core.rrb-vector}}的展开向量。:-)（可能使用一些条件编译，以便不破坏与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可能会因为优化那些无足轻重的事情而变得大10倍。