展开小向量

Question

如邮件列表（链接：1）中讨论的那样，本补丁有两个向量和映射的展开变体，每个基数都有特殊的内部类。目前它们都增长到六个元素，然后溢出到数据结构的一般版本，这是基于粗略测试，但可以很容易地进行更改。根据Rich的要求，我没有将其集成到其他代码中，并为每个包含顶层静态 create() 方法。

这个补丁的唯一原因是为了性能，无论是在创建数据结构上还是在执行操作上。这可以视为目前与 PersistentArrayMap 大量溢入 PersistentHashMap 中的技巧的更详尽的版本。基于基准测试（通过克隆 cambrian-collections (链接：2) 并运行 'lein test :benchmark' 可运行），这应该会取代 PersistentArrayMap。性能至少与 PAM 保持一致，并且往往更快。特别是创建时间，所有大小为地图的时间至少是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

我想知道在类中保留元数据和两个哈希字段的开销是什么。您是否有考虑过哈希在运行时计算，并使用具有元字段的集合集和没有元字段的集合集的版本，当实际元数据附加到集合时使用前者?

Answer 6

评论者：ztellman

我使用正确的方法附加了一个补丁。不知为何，我漏掉了如何做到这一点的详细说明，对此表示歉意。我知道指南说不应删除以前的补丁，但由于第一个补丁没有用，我已经删除它以减少混淆。

我进行了 print-dup 友好创建方法，然后意识到一旦这些方法被正确集成，'pr' 将会仅作为向量输出这些内容。我相当肯定创建方法是不必要的，所以我将它们注释掉，但如果它们在其他我无法理解的情况下有用，我很愿意重新添加它们。

我没有过多考虑内存效率，但我认为缓存散列是有益的。我明白创建每个集合的“带有元数据”版本可能是有道理的，但由于这将使补丁的大小翻倍，我认为这应该推迟。

Answer 7

评论者：ztellman

我找到了一个bug！就像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，而在没有数据结构（仅通过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

根据我在Clojure Conj与Alex的谈话，这是一个只包含展开向量的补丁，并在溢出时使用更有效的PersistentVector构造函数。

Answer 15

评论者：alexmiller

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