通过使用transient set改进clojure.core/distinct性能

Question

当前{{clojure.core/distinct}}实现使用持久集合。此补丁通过使用transient set而不是持久集合，将懒加性性能提高了约25%-30%，而transducer性能提高了约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 - 您仍然需要该属性在多线程transducing上下文中安全发布。

Answer 2

评论者：tonsky

[~alexmiller] 您怎么说的？

- 我没有更新{{seen}}链接，因为transient set可以就地修改。
变送器是否打算从多个线程中使用？因为现有的实现显然存在竞争条件。我想修复这个问题可能代价高昂（我们需要同步区域），所以或许应该是一个专用变送器，你只在需要的时候使用它？

Answer 3

评论者：alexmiller

瞬态集合不允许原地修改 - 你必须使用返回值。

是的，变送器在（例如）核心异步go块中的变送器通道中可以从多个线程中使用。

Answer 4

评论者：alexmiller

我应该说，变送器并不期望一次由多个线程使用，因此没有竞争问题。但长期从多个线程中使用需要正确的安全发布。

Answer 5

评论者：tonsky

bq. 长期从多个线程中使用需要正确的安全发布。

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

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

bq. 瞬态集合不允许原地修改 - 你必须使用返回值。

我在想，{{clojure/core.clj}}和{{clojure.lang.ATransientSet.java}}都是Clojure内部的组成部分，已经在同一位置，因此可以稍微共享一些彼此的内部知识。这样做似乎是安全的，因为这种知识不会泄露到外部，并且如果ATransientSet的实现有任何更改，core.clj可以在同一个版本中相应地更新。当然，我不会在第三方库中这样做。

Answer 6

评论者：alexmiller

{quote}这是否意味着在变送器中不能使用瞬态（因为瞬态实现基于的底层数组是原地修改的，因此不同的线程可能会看到瞬态对象的不同的状态）？{quote}

瞬态对象只需要确保一次最多只有一个线程请求它们，因此在变换器中使用是安全的。然而，它们应该保证安全发布。core.async 通道已经通过其实现的方式做到了这一点，但其他变换器上下文可能不是这样。

不论并发与否，都绝对不应该将瞬态对象用作“原地修改”。尽管在某些情况下它们可能看起来“有效”，但这永远是不正确的（最终更新操作将返回一个新实例，如果您正在原地修改，您的数据可能会丢失）。这一点已在 https://clojure.org/reference/transients 中讨论并展示了正确示例。

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

这是Rich和我正在讨论的问题，但可能会这样做。

Answer 7

评论者：tonsky

[~alexmiller] 这是个快速测试，展示了在一个线程中对瞬态集合（只不过是瞬态映射的包装）进行的更改，可能不会在其他线程中始终可见。

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

这意味着如果我们尝试使用瞬态对象，例如，用于“distinct”，将会错过重复项。

Answer 8

评论者：tonsky

由于变换器可能被多个线程访问，已从distinct的转换器中删除瞬态对象。

Answer 9

评论者：tonsky

也许那个文档 https://clojure.org/reference/transients 应该更新，关于瞬态对象不安全地从多个线程中使用的部分，因为一个线程所做的更改不一定对另一个线程可见。即使它们没有竞争。

Answer 10

评论者：alexmiller

我认为这个测试展示了瞬态集合/映射的一个故障，您应该为此创建一个用户案例，因为这比这个增强更为重要。

在转换器和延迟序列实现中，都应该能够使用临时变量。然而，contains? 操作在临时变量上不工作的问题实际上是一个独立的工单 - http://dev.clojure.org/jira/browse/CLJ-700，这个工单可能会要求重新排列类层次结构。我认为，除非这个问题得到解决（这样就可以避免依赖类和Java方法的变体），否则我们不会接受这个更改。

Answer 11

评论者：tonsky

我必须承认，我的测试是在展示其他东西：没有正确的线程隔离。因此这是一个并发问题，而不是“安全发布”问题。我现在理解的是

bq. 临时变量需要线程隔离。使用特定的临时实例应该通过将其放置在单线程作用域中或在强制执行此操作的框架中来实现。

此保证隐含了多个线程之间临时变量使用具有发生之前关系。没有其他方法可以定义“一次只有一个线程在这个部分”。

这意味着线程1中发生的所有写入操作对线程2都是可见的，无论涉及的变量是否易变。实际上，我们可以从临时变量实现中移除所有易变变量，并可能使它们更快，因为我们通过请求“一次只有一个线程”来强制用户在部分之间建立发生之前关系，这将为我们提供我们需要的所有安全发布保证。

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

Answer 12

评论者：tonsky

此外，长生命周期的临时变量（例如与队列关联的转换器中的），将保留创建它们的线程的引用。这是否不好？我们应该改为使用布尔标志吗？

Answer 13

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