展开的小向量

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向量来说与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

评论由：ztellman发表

哦，我忘了提，我没有创建PersistentUnrolledSet，因为现有的封装可以启用非滚动Map实现。然而，如果有一个将会更高效一些，所以如果我似乎值得让你知道。

Answer 2

评论由：bronsa发表

Zach，你添加的补丁格式不正确，它们需要通过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'将直接将这些输出为向量。我相当确信创建方法并非必需，因此已将它们注释掉，但若在某些我看不见的理由上有用，我也会高兴地将其添加回来。

我在内存效率方面没有过多思考，但我认为缓存哈希值是值得的。我可以看出创建每个集合的“with-meta”版本的论点，但鉴于这会使已经非常大的补丁大小翻倍，我认为这可能暂时不宜实施。

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 处创建了一个新的地图工作占位符。