展开小向量

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

评论由：ztellman 提出

哦，我忘了说，我没有创建 PersistentUnrolledSet，因为现有的封装可以直接使用 unrolled 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' 将直接输出这些向量大小的值。我认为这些创建方法可能不是必要的，所以我已将其注释掉，但如果有什么我看不见的原因有用，我也愿意将其重新启用。

我没有过多考虑内存效率，但我认为缓存哈希是有价值的。我可以看到创建包含“元信息”（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库中的数据结构。在“没有关键函数解码”的基准测试中，当前实现花费6微秒，使用打滚数据结构的需要4微秒，而没有数据结构（仅通过Jackson解析JSON）仅需2微秒。其他基准测试也有类似的结果。所以在这一场景中，它至少减少了50%的额外开销。

可以通过克隆 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为地图工作创建了一个新的占位符。