展开的小向量

Question

如邮件列表（链接：1）上所讨论的，此补丁有两个向量和映射的展开变体，并为每个基数提供了特殊的内部类。目前两者在增长到六个元素之前都会溢出到通用的数据结构版本中，这基于粗略测试，但可以很容易地更改。根据Rich的要求，我没有将任何集成到代码的其他部分，并为每个都提供了顶层静态create()方法。

此补丁的唯一原因是为了性能，无论是在创建数据结构还是在它们身上执行操作。这可以看作是当前正在进行的将PersistentArrayMap溢出到PersistentHashMap的技巧的更冗长的版本。根据基准测试，可以通过克隆cambrian-collections（链接：2）运行‘lein test :benchmark’来运行。这应该取代PersistentArrayMap。性能至少与PAM相当，并且通常要快得多。特别是创建时间，对于所有大小的映射都是5倍更快（运行test :only cambrian-collections.map-test/benchmark-construction），对于3向量与PAM相当，但对于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}}将因查看底层结构而损坏小数组。这也会损坏其他查看数组实现内部结构的库，尽管我不了解有任何其他的，当然不是任何其他贡献库。

另外，关于{{unrolled-vector.patch}}的几点评论

{{private *transient* boolean edit = true;}}
在Transpose类中可能应该为
{{private *volatile* boolean edit = true;}}
因为transient在Java中的意思完全不同。

{{conj}}在{{Transient}}实现中，在不引起任何问题的情况（{{edit = false;}}）下，如果它转换为一个TransientVector（即溢出）_可能_会使其自己无效化。这种无效化可以防止一些与错误使用瞬时的微妙错误。

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

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