展开小向量

Question

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

此补丁的唯一原因是为了性能，无论是创建数据结构还是对其执行操作。这可以看作是当前在持久数组映射中使用的溢出技巧的更详细版本。根据基准测试（可以通过克隆cambrian-collections（链接：2）并运行“leich test :benchmark”进行运行），这应该会取代持久数组映射。性能至少与PAM相当，而且通常更快。尤其值得注意的是创建时间，对于所有大小的映射（leich test :only cambrian-collections.map-test/benchmark-construction）可提高5倍，对于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

审查笔记：方法清晰易懂。鉴于生成的代码量很大，我相信最佳方法是尽快让人们使用它，并将其添加到Clojure测试套件中的collection-test（链接：3）。我还希望将生成器（链接：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一样，我对比较关键字有一条专门的代码路径，但我的集合检查生成器之前仅使用了整数字符。在 transient map实现中（链接：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

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

Answer 15

评论者：alexmiller

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