展开小向量

Question

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

此补丁的惟一原因是为了性能，无论是在创建数据结构还是在操作它们时。这可以看作是当前在 PersistentArrayMap 中使用的技巧的更详尽的版本，该技巧会溢出到 PersistentHashMap。根据基准测试（可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来运行），这应该取代 PersistentArrayMap。性能至少与 PAM 相当，而且通常更快。特别值得注意的是创建时间，对于所有大小的映射（lein test :only cambrian-collections.map-test/benchmark-construction）快 5 倍，对于 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;}}
在Transcient类中可能应该是
{{private *volatile* boolean edit = true;}}
因为Java中的transient意味着完全不同的意思。

{{conj}}在{{Transient}}实现中，它可以（没有问题地将自己置为无效（{{edit = false;}}））转换成TransientVector（即溢出）——除非它有一个显着的开销。这种无效化可以防止一些与错误使用transient相关的微妙错误。

Answer 2

评论由：alexmiller

Jean，理解该补丁的影响范围将是整合过程中的一个部分。我感谢您的提醒。虽然我们试图最小化此类情况对开发的影响，但可能不可避免地对依赖于实现内部结构的库造成破坏。

Answer 3

评论由：_Comment made by: michalmarczyk_

一旦transpose vectors landed on master，我将添加对unrolled vectors的支持。:-) （可能使用一些条件编译来确保与Clojure早期版本兼容——到时候我们再看看。）

Answer 4

评论由：_Comment made by: michalmarczyk_

我应该说，可以通过将它们线性地倾倒入常规向量来为任何“看起来像向量”的通用支持。乍一看，这似乎与库的基本承诺不符，但在实际更改到位之前，我还会再想一些。

Answer 5

评论由：_Comment made by: 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

评论由：_Comment made by: 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

评论由：_Comment made by: ztellman_

好了，什么时候会做出决定？我非常高兴我们似乎终于在这方面开始前进了。

Answer 10

评论由：alexmiller

不，但现在它在我的工作列表中。

Answer 11

评论者：richhickey

我想知道对APersistentVector的所有重写是否都会带来重要的好处——例如，迭代器、hashCode等。

Answer 12

评论由：_Comment made by: ztellman_

在hashCode的情况下，绝对是：《https://gist.github.com/ztellman/10e8959501fb666dc35e#file-gistfile1-txt-L1013-L1076》这实际上是我最初想要加速的事情之一。

在迭代器的情况下，可能不会。我会很乐意去掉它。

Answer 13

评论由：_Comment made by: ztellman_

所以我是否应该从https://github.com/clojure/clojure/commit/36d665793b43f62cfd22354aced4c6892088abd6中推断出这个问题已经解决？如果是这样，我认为还有许多改进被留在了桌面上，而没有特别的原因。

Answer 14

评论者：richhickey

是的，这个提交包括了这个功能。它在建立小核时的方法与补丁不同，最大限度地提高基础知识而不是在每一个类中有很多冗余定义。这也允许立即集成，而不必过于担心正确性，因为新的代码很少。这也强调了元组的用例，例如，用作值的小向量不会更改，从而减轻了对“可变”函数的关注。我不同意许多必要的改进都被遗漏了。补丁“优化”了许多不重要的事情。此外，没有大规模改进到普遍的内联。此外，提交包括了一小部分的集成工作，而不像补丁那么大。总之，要将补丁按照这种方法进行调整，可能需要更多的来回交流，但我也感激灵感和推动——谢谢！

Answer 15

评论者：richhickey

也就是说，这个提交不必是最后的话 - 它可以作为一个进一步优化的起点。但我更希望这是由需求驱动的。Clojure可能会因为优化一些不重要的事情而变得非常大。