展开小型向量

Question

在邮件列表上讨论过（链接：1），这个补丁有两个向量和映射的展开变体，每个基数都有特殊的内部类。目前两者都增长到六个元素，然后溢出到基于粗略测试的通用数据结构版本，这可能很容易改变。根据Rich的请求，我没有将其集成到其他代码中，并为每个都提供了顶级静态create()方法。

这个补丁的唯一原因是性能，无论是在创建数据结构还是在它们的操作中。这可以被视为PersistentArrayMap溢出到PersistentHashMap所使用的技巧的更冗长的版本。根据基准测试，这可以通过克隆cambrian-collections（链接：2）并运行'lein test :benchmark'来完成，它应该取代PersistentArrayMap。性能至少与PAM相当，并且通常要快得多。特别是创建时间，对于所有大小的映射，是5倍更快（运行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，因为现有的封装已经可以使用unrolled map实现。然而，有一个会更快、更节省内存的版本，如果这样做似乎值得，请告诉我。

Answer 2

评论者：bronsa

Zach，你添加的补丁格式不正确，它们需要使用git format-patch创建

Answer 3

评论者：bronsa

此外，我不确定这些与问题单的范围是否相符，但那些补丁与**print-dup**冲突，因为它期望每个内部类都有一个静态创建(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

我已经使用正确的方法附上了补丁，但遗憾的是我遗漏了对如何操作的具体说明。我知道指导方针说不应该删除以前的补丁，但由于第一个补丁没有用，我已将其删除以减少混淆。

我做了打印友好的创建方法，然后意识到这些被适当集成后，'pr'会将这些作为向量化输出。我相当确信创建方法是不必要的，因此我已经注释掉了它们，但如果它们在某些我看不见的原因下有用，我很乐意再添加回去。

我没有过多考虑内存效率，但我认为缓存hash是有价值的。我认为为每个集合创建一个"带有元数据"的版本是合理的，但鉴于这会使补丁的大小翻倍，我认为这应该稍后再做。

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解码”基准测试中，当前实现需要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

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