展开的小向量

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向量，与PAM相当，但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仓库中。我们不必 necessarily自动化运行它，但如果将来需要对其进行调整，那就很方便。

(链接：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

扎克，你添加的补丁格式不正确，它们需要使用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'上传），但显然，有一个bug的地方，可能还有其他bug。

(链接：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 为地图工作创建了一个新的占位符。