展开小型向量

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-向量与 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}}的几点评论

在{{Transient}}类中应该更可能是这样的：{{private *transient* boolean edit = true;}}
应该
{{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

作为不展开地图性能分析的一个补充，我已经运行了基准测试并在 https://gist.github.com/ztellman/10e8959501fb666dc35e 上发布了结果。一些值得关注的结果

• conj 比 generic vectors 快 3 倍： https://gist.github.com/ztellman/10e8959501fb666dc35e#file-gistfile1-txt-L329-L451
• reduce + 比 generic vectors 快 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

是的，这次提交覆盖了这个功能。它采用了一种不同的方法，从小核心开始构建，而不是在每个类中有很多冗余定义，以最大程度地提高基础的改进。这也允许立即集成，而不必过多担心正确性，因为代码量很少。它还强调了元组的用例，例如作为不会更改的值使用的小向量，从而降低了“可变”函数的重要性。我不同意很多必要的改进被省略了。补丁“优化”了很多不 important的东西。此外，对于嵌入式函数的改进并不大。此外，提交中还包含了一小部分集成工作，大小是补丁的四分之一。总的来说，要让补丁符合这种方法比完成所有工作需要更多的来回沟通，但我非常感谢灵感和推动 - 谢谢！

Answer 15

评论者：richhickey

尽管如此，这个提交不一定是最终的选择——它可以作为进一步优化的基准。但最好是按照需求驱动。Clojure可能会因为优化那些不重要的事情而变得10倍之大。