展开的小向量

Question

如邮件列表（链接：1）中所讨论的，此补丁有两个向量与映射的展开变体，每个都可以用特殊的内部类进行优化。目前两者在增长到六个元素后，会溢出到一般的数据结构版本，这是基于粗略测试，但可以很容易地更改。根据 Rich 的要求，我没有将其集成到代码的其他部分，并且为每个都提供了顶层静态的 create() 方法。

此补丁的唯一原因是为了性能，不仅是在创建数据结构时，而且在操作它们时。这可以视为与 PersistentArrayMap 溢出到 PersistentHashMap 被使用的技巧更复杂的一种形式。根据基准测试（可以通过克隆 cambrian-collections（链接：2）并运行 'lein test :benchmark' 来运行），此补丁应取代 PersistentArrayMap。性能至少与 PAM 相当，并且通常更快。特别值得一提的是创建时间，对于所有大小的映射（运行 'lein test :only cambrian-collections.map-test/benchmark-construction'），其速度比 PAM 快 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

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

我想知道类中包含 meta 和 2 个哈希字段的开销是什么。您是否考虑过一种版本，其中哈希是即时计算的，并且有两个集合集，一个包含 meta 字段，一个不包含，当实际元数据附加到集合时使用前者？

Answer 6

评论者：ztellman

我已经使用正确的方法附上了一个补丁。不知何故，我遗漏了如何操作的详细说明，很抱歉。我知道指南说不应该删除以前的补丁，但由于第一个补丁没有用，我已经删除了它以减少混淆。

我完成了print-dup友好的创建方法，然后意识到一旦这些被适当集成，'pr'将只需将这些作为向量化输出。我相当确定创建方法是不必要的，所以我已经将它们注释掉，但如果它们在某些我看不见的原因有用的话，我也乐意再次添加它们。

我没有充分考虑到内存效率，但我想缓存散列值是有价值的。我认为创建每个集合的“with-meta”版本是合理的，但由于这将使已非常庞大的补丁的大小加倍，我认为这应该等待。

Answer 7

评论者：ztellman

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

我已经仔细查找测试覆盖中的其他差距，但没有发现任何。我不认为这实质上改变了这个补丁的风险（已作为“unrolled-collections-2.diff”上传的更新版本），但显然，出现了一个bug，可能还有其他。

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

Answer 8

评论者：ztellman

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

可以通过克隆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日发布，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的讨论，这只是一个包含未展开向量且使用更高效构造函数的持久向量的补丁，当溢出时使用。

Answer 15

评论者：alexmiller

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