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

Question

当前clojure.core/distinct的实现使用持久集合。此补丁通过使用transient集合替代，提高了懒操作符的性能约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集合可以被原地修改。
驱动器是否设计为支持多线程使用？因为现有的实现中明显存在竞态条件。我认为解决这个问题代价巨大（我们需要使用同步代码块），所以或许应该有一个仅在必要时使用的专用驱动器？

Answer 3

评论者：alexmiller

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

是的，在 core.async go 块中的 transducer 通道（例如）中从多个线程使用驱动器。

Answer 4

评论者：alexmiller

我还应该强调，预计驱动器不会同时被多于一个线程使用，因此不存在竞态条件。但是，随着时间的推移，从多个线程中使用需要适当的安全发布。

Answer 5

评论者：tonsky

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

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

这也意味着 {{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中讨论并展示正确示例的内容。

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

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

Answer 7

评论者：tonsky

[~alexmiller] 以下是一个快速测试，展示了在一个线程中对瞬态集合（它不过是瞬态映射的包装）所做的修改，不一定能从另一个线程中看到。

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

这意味着如果我们尝试使用瞬态对象进行例如 distinct（唯一化）操作，可能会错过重复的项。

Answer 8

评论者：tonsky

由于转换器可能会被多个线程访问，因此从 distincts 的转换器中移除了瞬态对象。

Answer 9

评论者：tonsky

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

Answer 10

评论者：alexmiller

我认为测试展示了瞬态集合/映射的一个漏洞，你应该为此提交一个工单，因为它比这个增强更重要的是。

distinct 应该能够在转换器和懒序列实现中同时使用瞬态。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报告）