展开小向量

Question

如邮件列表中讨论的那样（链接：1），此补丁包含向量和映射的两种展开变体，并为每种基数提供特殊的内部类。目前，它们的元素数量在增加到六个元素之前，会溢出到数据结构的通用版本，这是基于粗略测试的结果，但可以很容易地更改。根据Rich的要求，我没有将其融入其余代码中，并为每个添加了顶层静态的create()方法。

这个补丁的唯一原因是性能，既涉及创建数据结构，也涉及在这些数据结构上执行操作。这可以被视为一种更详尽的当前用于PersistentArrayMap溢出到PersistentHashMap的技巧的版本。根据基准测试，可以通过克隆cambrian-collections（链接：2）并运行'lein test :benchmark'来进行。这应该取代PersistentArrayMap。性能至少与PAM相当，并且通常要快得多。值得注意的是创建时间，对于所有大小的映射来说是5倍更快（运行'read test :only cambrian-collections.map-test/benchmark-construction'），对于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}}中的unrolled向量。:-)（可能通过一些条件编译以避免与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发布

请注意，我们目前“重置”了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很大程度可以优化那些无关紧要的事情。