通过使用transient集合提高clojure.core/distinct性能

Question

当前clojure.core/distinct的实现使用持久化集合。此补丁通过使用transient集合代替持久化集合，将懒 Convenientity 的性能提高了约25%-30%，将转换器的性能提高了约40%-50%。


10个元素
(doall (distinct coll))      5.773439 µs => 4.179092 µs (-27%)
(into [] (distinct) coll)      3.238236 µs => 1.943254 µs (-39%)

100个元素
(doall (distinct coll))      67.725764 µs => 42.129993 µs (-37%)
(into [] (distinct) coll)      35.702741 µs => 16.495947 µs (-53%)

1000个元素
(doall (distinct coll))      540.652739 µs => 399.053873 µs (-26%)
(into [] (distinct) coll)      301.423077 µs => 164.025500 µs (-45%)

10000个元素
(doall (distinct coll))      3.439137 ms => 3.058872 ms (-11%)
(into [] (distinct) coll)      1.437390 ms => 848.277178 µs (-40%)


基准代码： https://gist.github.com/tonsky/97dfe1f9c48eccafc983a49c7042fb21

Answer 1

评论人员：alexmiller

不能移除volatile - 你们仍然需要在多线程转换器场景中安全发布。

Answer 2

_评论人员：tonsky_

[~alexmiller] 你怎么说的？

- 我不更新{{seen}}链接，因为transient集合可以原地更改
- 转换器是否意味着可以从多个线程使用？因为现有的实现明确存在竞争条件。我想修复这将是昂贵的（我们需要同步段落），所以也许应该有一个专门用于需要时才使用的转换器？

Answer 3

评论人员：alexmiller

瞬态集合不能原地修改 - 您必须使用返回值。

是的，在多个线程中以（例如在 core.async go 块中的 transducer-chan）使用 transducer。

Answer 4

评论人员：alexmiller

我也应该说的是，transducer 不期望被两个以上的线程同时使用，所以没有竞态问题。但是随着时间的推移在多个线程中使用，需要适当的发布安全性。

Answer 5

_评论人员：tonsky_

但是随着时间的推移在多个线程中使用，需要进行适当的发布安全性。

这个是否意味着不能在 transducer 中使用瞬态（因为基于瞬态实现的基础数组是原地修改的，因此不同的线程可能会看到瞬态对象的不同状态）？

这也意味着 {{partition-by}} 和 {{partition-all}} 应该被修复（它们使用 {{java.util.ArrayList}}，作为一个引用数组，没有安全的发布语义）？

瞬态集合不能原地修改 - 您必须使用返回值。

我在想，{{clojure/core.clj}} 和 {{clojure.lang.ATransientSet.java}} 都是 Clojure 内部的一部分，并列放置，所以可以共享一些彼此的内部知识。这样做似乎是安全的，因为这种知识不会泄漏在外，并且如果 ATransientSet 的实现发生任何变化，core.clj 可以在相同版本中进行更新。当然，我不会在任何第三方库中这样做。

Answer 6

评论人员：alexmiller

“这是否意味着不能在 transducer 中使用瞬态（因为基于瞬态实现的基础数组是原地修改的，因此不同的线程可能会看到瞬态对象的不同状态）？”

瞬态的要求仅仅是它们在同一时间只能被单个线程请求，因此在 transducer 中使用是安全的。然而，它们应该保证安全的发布。core.async 通道已经通过其实现的方式作为这个特性的一部分做了这一点，但其他 transducing 上下文可能不会。

无论并发性如何，瞬态决不应该用作“原地修改”。尽管在某些情况下它似乎会“工作”，但这决不是正确的（最终更新操作会返回一个新实例，如果你正在原地修改，那么你的数据将丢失）。这一点已在 https://clojure.org/reference/transients 上讨论，并展示了正确示例。

{quote}这也意味着分区 (partition-by) 和全部分区 (partition-all) 也应该修复（它们使用 java.util.ArrayList，作为一个引用数组，没有安全发布的语义）吗？{quote}

这是Rich和我正在讨论的事情，但很可能是。

Answer 7

_评论人员：tonsky_

[~alexmiller] 以下是一个快速测试，展示了在单个线程中对transient集合（实际上是transient映射的包装）所做的更改在其他线程中并不总是可见。

https://gist.github.com/tonsky/62a7ec6d539fc013186bee2df0812cf6

这意味着如果我们尝试使用transient来进行例如distinct操作，将会错过重复项

Answer 8

评论者为：tonsky

从distinct的transducer操作数中删除了transients，因为transducer可能会被多个线程访问

Answer 9

_评论人员：tonsky_

也许这个文档https://clojure.org/reference/transients应该更新一下，关于transients在多个线程中不可安全使用，因为一个线程所做的更改不一定对另一个线程可见。即使它们不竞争

Answer 10

评论人员：alexmiller

我认为这个测试展示了transient集合/映射的一个bug，你应该提交一个票证，因为这对于这个增强功能来说非常重要。

distinct 应该能够在transducer和lazy seq实现中同时使用transients。与transients上contains?不工作的问题实际上是一个单独的票证 - http://dev.clojure.org/jira/browse/CLJ-700，这可能会要求重新排列一些类的层次结构。我认为我们不会在修复这个问题之前采纳这个更改（这样你就可以避免依赖于类和Java方法变体）。

Answer 11

_评论人员：tonsky_

我必须承认，我的测试演示的是另一方面：没有适当的线程隔离。因此，这是一个并发问题，而不是“安全发布”问题。我的目前的理解是这样的

注意。转瞬即逝的数据需要线程隔离。对特定转瞬即逝实例的使用应通过将其用于单线程作用域或强制执行此要求的框架来控制。

这种保证隐含地假定多个线程对转瞬即逝实例的使用之间存在happens-before关系。没有其他方法可以定义“一次只有一个线程在这个部分”。

这意味着所有在线程1中发生的写入都可以在线程2中看到，无论涉及变量的易变性如何。实际上，我们可以从转瞬即逝实例的实现中删除所有易变性，并可能使它们更快，因为通过要求“一次只有一个线程”我们可以强制用户在区域之间建立happens-before，这将为我们提供所有所需的确保安全发布保证。

我的理解正确吗？我遗漏了什么吗？

Answer 12

评论者为：tonsky

此外，持久化的转瞬即逝实例（例如与队列关联的transducers）将保留它们创建的线程的引用。这是坏事吗？我们应该改为布尔标志吗？

Answer 13

参考资料：https://clojure.atlassian.net/browse/CLJ-2090（由tonsky报告）