展开小型向量

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”将只会将这些作为向量发出。我相当确定创建方法是不必要的，因此我已经将其注释掉，但如果它们在无法看清的原因下有用，我会很高兴将其添加回来。

我没有过多考虑内存效率，但我觉得缓存哈希值是值得的。我可以理解创建每个集合的“带有元数据”版本的论点，但由于这将使已非常大的补丁的大小加倍，我认为这应该等待一段时间。

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 微秒。其他基准测试也有类似的结果。所以至少在这种场景下，它将开销减半。

可以克隆 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

约翰，这样的评论没有意义。让我们请专注于问题本身。

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