展开小向量

Question

正如在邮件列表（链接：1）上所讨论的，这个修补程序包含了向量和映射的两个展开变体，每个基数都有特殊的内部类。目前，这两种都扩展到六个元素，然后溢出到数据结构的一般版本，这是基于粗略测试的，但可以轻松更改。应瑞克的请求，我未将其集成到代码的其他部分中，并为每个创建了顶级静态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行），并且将很难进行审查。我的正确性假设是基于集合检查的使用以及背景方法非常简单的事实。不过，如果有助于审查过程，我很乐意提供所采取方法的概述。

我希望把它放到1.7中，如果有我可以做的事情来帮助实现这一点，请告诉我。

(链接：1) https://groups.google.com/forum/#!topic/clojure-dev/pDhYoELjrcs
(链接：2) https://github.com/ztellman/cambrian-collections

修补程序: unrolled-vector-2.patch

镜头说明：方法清晰易懂。考虑到生成的代码数量巨大，我认为提高对该代码的信心最好的办法是尽快让人们使用它，并将集合-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)静态方法和一个create(ISeq x)静态方法，为内部PersistentUnrolledVector类添加。

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库中的数据结构。在“无关键词函数解码”基准测试中，当前实现需要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。