展开的小矢量

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向量，与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

我想知道在类中有元数据和两个哈希字段的开销是什么。您考虑过这样一个版本，其中在运行时计算哈希，并且您有两组集合，一个带有元字段，一个不带，在元数据附加到集合时使用前者吗？

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

根据我和Alex在Conj上的谈话，这里有一个只包含展开向量的补丁，并使用PersistentVector 泄漏时的更有效的构造函数。

Answer 15

评论者：alexmiller

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