展开的小向量

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向量性能相当，但对于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 类添加一个创建(Map x)静态方法，并为内部 PersistentUnrolledVector 类添加一个创建(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' 会将它们作为向量输出。我相当确定创建方法是不必要的，因此我已经将其注释掉，但如果它们对某些我看不见的理由有帮助，我也乐意重新添加。

我还没有过多考虑内存效率，但我认为缓存散列是有价值的。我可以看到为每个集合创建一个 "带元数据" 版本的理由，但由于这将使补丁的大小翻倍（目前补丁已很大），我认为这应该暂时推迟。

Answer 7

由 ztellman 发表评论

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

我已经仔细检查了我的测试覆盖率中的其他漏洞，但没有找到。我认为这个补丁的风险实质上没有改变（已上传为'unrolled-collections-2.diff'的更新版本），但很显然，如果一个bug存在，可能还有其他bug。

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

Answer 8

由 ztellman 发表评论

作为一个额外数据点，我在Cheshire JSON库中替换了数据结构。在“没有关键字-fn decode”基准测试中，当前实现耗时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日发布，1.6.0于2014年3月25日发布。所以，目前的节奏大约是每年一次。

Answer 12

由 alexmiller 发表评论

约翰，类似的评论没有意义。请让我们将问题评论集中在问题上。

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