展开小矢量

Question

根据邮件列表上的讨论（链接：1），这个补丁有两个矢量和不定长的变种，每个变体都有特殊的内部类。目前这两个在增长到六个元素之前都会传入通用数据结构版本，这基于粗略的测试，但可以很容易地更改。根据 Rich 的要求，我没有将其集成到其余的代码中，并且为每个变体都有一个顶层静态的 create() 方法。

这个补丁的唯一原因是为了性能，无论是创建数据结构还是在它们上执行操作。这可以看作是一个比目前使用 PersistentArrayMap 泄漏到 PersistentHashMap 的技巧更为详细的形式。基于基准测试，可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来运行，这应该会替代 PersistentArrayMap。性能至少和 PAM 一样好，而且通常要快得多。特别值得一提的是创建时间，对于所有大小的映射来说，它要快5倍（运行测试：'lein test :only cambrian-collections.map-test/benchmark-construction'），对于三维来说也是相等的，但对于五维来说要快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

由 ztellman 发表的评论

哦，我忘记提到我没有创建 PersistentUnrolledSet，因为现有的封装可以直接使用 unrolled map 实现。但是，拥有一个 PersistentUnrolledSet 会使速度更快，并且更节省内存，所以如果它看起来很有价值，请告诉我。

Answer 2

由 bronsa 发表的评论

扎克，你添加的补丁格式不正确，它们需要使用 git format-patch 创建。

Answer 3

由 bronsa 发表的评论

此外，我不确定这个是否在工单的范围之内，但那些补丁与 **print-dup** 碰撞，因为它期望每个内部类都有一个静态 create(x) 方法。

建议为内部 PersistentUnrolledMap 类添加一个 create(Map x) 静态方法，以及为内部 PersistentUnrolledVector 类添加一个 create(ISeq x) 静态方法。

Answer 4

由 alexmiller 发表的评论

关于制作补丁，请参阅： http://dev.clojure.org/display/community/Developing Patches

Answer 5

由 wagjo 发表的评论

我想知道在类中包含元数据和两个哈希字段的开销是什么。你考虑过一种版本，其中在需要实际元数据附加到集合时，哈希值是动态计算的，并且你有两组集合，一组包含元数据字段，另外一组没有元数据字段吗？

Answer 6

由 ztellman 发表的评论

我已经使用正确的方法附带了补丁。不知何故，我遗漏了如何做到这点的详细说明，非常抱歉。我知道指南说不要删除以前的补丁，但由于第一个补丁没有用，我已经删除它以减少混淆。

我做了print-dup友好的创建方法，然后意识到一旦这些方法得到适当整合，'pr'将仅将这些作为向量发出。我相当确信创建方法是不必要的，因此已将它们注释掉，但如果发现了我看不见的某些原因有用的话，我很乐意将它们再添加回去。

我没有充分考虑内存效率，但我想缓存散列是值得的。我可以看到创建每个集合的"带有元数据"版本的论点，但由于这将使已经巨大的补丁的大小加倍，我认为这可能需要稍后再考虑。

Answer 7

由 ztellman 发表的评论

我发现了一个bug！和PersistentArrayMap一样，我对关键字比较有专门的代码路径，但之前在collection-check的生成器中只使用了整数键。在transient map实现中（链接：1）存在一个偏移量错误，而在非关键字查找中则不存在。

我已经仔细检查了我测试覆盖的其他差距，但没有发现。我不认为这会实质性改变这个补丁的风险（作为'unrolled-collections-2.diff'已上传的更新版本），但显然在一个bug存在的地方，可能会有其他bug。

(链接：1) https://github.com/ztellman/cambrian-collections/commit/eb7dfe6d12e6774512dbab22a148202052442c6d#diff-4bf78dbf5b453f84ed59795a3bffe5fcR559

Answer 8

由 ztellman 发表的评论

作为一个额外的数据点，我在Cheshire JSON库中交换了数据结构。在“没有关键字函数解码”基准测试中，当前实现需要6us，使用展开的数据结构需要4us，而没有数据结构（只是通过Jackson解析JSON）需要2us。其他基准测试也有类似的结果。所以，至少在这个场景中，它至少将开销减半。

可以通过克隆https://github.com/dakrone/cheshire来运行基准测试，可以通过使用'unrolled-collections'分支来测试展开的集合。可以通过稍微修改cheshire.parse命名空间来重现纯解析基准测试。

Answer 9

由 ztellman 发表的评论

有没有办法将其放到1.7版本中？推迟一年发布是一个巨大的胜利。

Answer 10

由 alexmiller 发表的评论

Hey Zach，这肯定被认为是重要的，但我们已经决定放弃1.7版本中几乎所有的未完成项目。后续发布的 时间表尚不明确，但肯定比一年要少得多。 :)

Answer 11

评论者：jszakmeister

你们可以自由决定时间表，但我认为应该指出Zach并没有完全偏离观点。Clojure 1.4.0于2012年4月5日发布。Clojure 1.5.0于2013年3月1日发布，Clojure 1.6.0于2014年3月25日发布。看来目前的节奏大约是一年。

Answer 12

由 alexmiller 发表的评论

John，这样评论是没有意义的。让我们请将问题评论集中在问题上。

Answer 13

由 ztellman 发表的评论

我对这个补丁进行了一些简写，应该有助于最终的代码审查： http://blog.factual.com/using-clojure-to-generate-java-to-reimplement-clojure

Answer 14

由 ztellman 发表的评论

根据我在Conj与Alex的谈话，这是一个只包含展开向量的补丁，并在溢出时使用更高效的PersistentVector构造函数。

Answer 15

由 alexmiller 发表的评论

Zach，我在http://dev.clojure.org/jira/browse/CLJ-1610创建了一个新的占位符用于地图的工作。