展开的小向量

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 存储库中。我们不一定需要自动化运行它，但如果我们想要稍后对其进行修改，最好将其放在手边。

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

我使用了正确的方法附加了一个补丁。不知怎么地，我遗漏了详细说明如何进行的介绍，对此表示歉意。我知道指导方针说不应该删除之前的补丁，但由于第一个补丁没有用处，我已经删除它以减少混淆。

我完成了对友好打印的创建方法的处理，然后意识到一旦这些方法得到适当的集成，'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库中替换了数据结构。在“无关键字fn解码”基准测试中，当前实现需要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 为地图任务创建了一个新的占位符。