展开小向量

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

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' 就会将其作为向量发出。我相当确信创建方法并不是必要的，所以我已将其注释掉，但如果它们在某些我看不见的方面有用途，我很乐意把它们加回去。

我没有过多考虑内存效率，但我认为缓存散列是值得的。我可以看到创建每个集合的“带元”版本的论点，但鉴于这会使补丁的大小加倍，我认为这可能需要等待。

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 库中替换了数据结构。在“无关键字 fn 解码”基准测试中，当前实现需要 6us，使用未展开的数据结构需要 4us，没有任何数据结构（仅为杰克逊解析 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日发布，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的谈话，这是一个只包含展开向量的补丁，并使用更高效的构造函数为spilling over的PersistentVector。

Answer 15

评论者：alexmiller

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