展开小向量

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-向量，与 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，因为现有的包装器可以使用unrolled map实现。然而，如果有一个，它会有适度的速度和内存效率，所以如果它看起来值得，请告诉我。

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

我很想知道在类中有meta和2个hash字段的开销是什么。您是否考虑过这样的版本，其中hash是动态计算的，并且您有两个集合集合，一个带有meta字段，另一个不带，在将实际元数据附加到集合时使用前者？

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

John，这种评论是没有意义的。让我们请专注于问题本身。

Answer 13

评论者：ztellman

我在此补丁上做了一些小的概述，这应该有助于最终的代码审查：http://blog.factual.com/using-clojure-to-generate-java-to-reimplement-clojure

Answer 14

评论者：ztellman

根据我在Conj上与Alex的对话，这是一份仅包含非展开向量的补丁，并在溢出时使用更高效的PersistentVector构造函数。

Answer 15

评论者：alexmiller

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