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

Question

当前{{clojure.core/distinct}}的实现使用持久集合。此补丁通过使用transient集合改善懒惰语法的性能约25%-30%，以及化简器(TRANSUCER)性能约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 块中的变换器通道中）。

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}这也意味着 partition-by 和 partition-all 需要修复（它们使用 java.util.ArrayList，作为引用数组，没有安全的发布语义）？{quote}

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

Answer 7

_评论者: tonsky_

[~alexmiller] 这里有一个快速测试，它显示在一个线程中对瞬态集合（它不过是一个瞬态映射的包装）进行的修改并不总是能从另一线程中看到。

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

这意味着如果我们尝试使用瞬态数据，例如 distinct，将丢失重复的项

Answer 8

评论者：tonsky

从 distinct 的 transducer 形式中去掉了瞬态数据，因为 transducer 可能会被多个线程访问

Answer 9

_评论者: tonsky_

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

Answer 10

评论者: alexmiller

我觉得这个测试揭示了瞬态集合/映射中的一个错误，你应该为这个错误提交一个工单，因为这比这个增强要重要得多。

distinct 应该能够在 transducer 和 lazy seq 实现中都使用瞬态数据。contains? 在瞬态数据上不工作的问题实际上是一个独立的工单 - http://dev.clojure.org/jira/browse/CLJ-700，这可能会要求对类层次结构进行调整。我认为我们不会采取这个更改，直到这个问题被解决（这样你就可以避免依赖于类和 Java 方法变体）。

Answer 11

_评论者: tonsky_

Answer 12

评论者：tonsky

Answer 13