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

Question

当前clojure.core/distinct的实现使用持久集合。本补丁通过使用transient集合代替，提高了惰性操作性能约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 chans。

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 的转换器 arity 中删除瞬态对象

Answer 9

评论由：tonsky

可能需要更新https://clojure.org/reference/transients文档，指出瞬态对象在多线程中使用时并不安全，因为一个线程所做的更改对另一个线程可能不可见。即使它们没有竞争

Answer 10

评论由：alexmiller

我认为这个测试展示了瞬态集/映射的 bug，你应该为这个 bug 提交一张工单，因为它比这个增强功能更重要。

distinct 应该能够在转换器和懒情序列实现中同时使用瞬态对象。contains? 在瞬态对象上不工作的问题实际上是一个单独的工单 - http://dev.clojure.org/jira/browse/CLJ-700，这可能需要一些类层次结构的重新排列。我认为我们不会在修复之前采用这个变更（这样你就可以避免依赖类和 Java 方法变体）。

Answer 11

评论由：tonsky

我必须承认，我的测试显示了我没有预料到的东西：没有适当的线程隔离。所以这是一个并发问题，而不是“安全发布”问题。我的理解是这样的：

bq. Transients需要线程隔离。应该通过在单线程范围内使用，或者在强制执行此操作的框架中使用特定瞬态实例进行控制。

这个保证隐含地假设了多个线程中transient使用的happens-before关系。没有其他方法可以定义“一次只有一个线程在此处”。

这意味着线程1中发生的所有写入对线程2都是可见的，无论涉及变量的可变性如何。实际上，我们可以从transients实现中去掉所有可变的，可能还会使它们更快，因为通过要求“一次只有一个线程”，我们强制用户在部分之间建立happens-before关系，这将给我们所有需要的确保安全发布。

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

Answer 12

评论者: tonsky

此外，长寿命的transients（例如与队列关联的transducers）将保留创建它们的线程引用。这是否不好？我们应该切换到布尔标志吗？

Answer 13

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