展开小向量

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元组，速度持平，但对于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

评论者：ztellman

哦，我忘记了提到，我没有制作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

我想知道在类中拥有元数据和2个哈希字段的开销是什么。你考虑过这样一个版本吗？在这个版本中，哈希是在实时计算的，你拥有两组集合，一组带有元数据字段，一组没有，使用前者，当实际元数据附加到集合时。

Answer 6

评论者：ztellman

我已经使用正确的方法附上了补丁。不知道为什么我错过了如何做这一点的详细解释，对此表示抱歉。我知道指南说不应该删除以前的补丁，但既然第一个补丁没有用，我已经删除它来减少混淆。

我完成了 print-dup 友好的创建方法，然后意识到一旦这些方法得到适当的整合，'pr' 就会自动将这些作为向量发出。我相信创建方法不一定必要，所以我已将它们注释掉，但如果有特殊原因我看不到它们的有用之处，我也乐意把它们回来。

我没有过多考虑内存效率，但我认为缓存哈希值是值得的。我可以看出创建每个集合的“带有元数据”版本的论点，但由于这将使补丁的大小翻倍，我觉得这应该等到以后。

Answer 7

评论者：ztellman

我发现了一个错误！和 PersistentArrayMap 一样，我有专门用于比较键字的代码路径，但我的集合检查生成器之前只使用整数键。瞬态映射实现中有一个偏离一个的错误（链接：1），在非关键字查找中不存在。

我已经仔细检查我的测试覆盖的其它空白，但找不到。我认为这个补丁（已作为 'unrolled-collections-2.diff' 上传的更新版本）的风险实质上没有改变，但显然，一个错误可能还有其他的。

(链接：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

嗨，Zach，这确实被认为很重要，但我们决定为1.7版本放弃几乎所有未完成的任务。下一个发布的期限尚不明确，但肯定不会超过一年。 :)

Answer 11

评论由：jszakmeister

你们可以自由决定时间表，但我想指出，Zach并没有完全离谱。Clojure 1.4.0于2012年4月5日发布。Clojure 1.5.0于2013年3月1日发布，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创建了映射工作的新占位符。