展开的小向量

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类提供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' 将会只发布这些向量。我相当确信创建方法是不必要的，所以我已将它们注释掉，但如果有什么我不知道的原因需要它们，我乐意加上它们。

我没有很多考虑内存效率，但我想缓存散列是有价值的。我可以看出创建每个集合的 "with-meta" 版本的理由，但由于这将使补丁的大小翻倍，我认为这可能需要稍后再进行。

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 库中替换了数据结构。在 "无关键字函数解码" 基准测试中，当前实现需要6微秒，而展开的数据结构需要4微秒，而没有数据结构（仅通过 Jackson 解析 JSON）需要2微秒。其他基准测试结果相似。所以至少在这个场景中，它至少减少了50%的开销。

可以通过克隆 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的交谈，这里有一个只包含unrolled vectors的补丁，并且当漾出时使用更有效的PersistentVector构造函数。

Answer 15

评论者：alexmiller

Zach，我在http://dev.clojure.org/jira/browse/CLJ-1610为新映射创建了一个占位符。