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

Question

当前 {{clojure.core/distinct}} 的实现使用了持久集合。这个补丁通过使用动态集合将惰性参数的性能提高了约 25%-30%，并提高了约 40%-50% 的 transducer。


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}} 链接，因为动态集合可以原地修改。
传感器是否设计成可以在多个线程中使用？因为现有的实现显然存在竞争条件。我想修正这会相当昂贵（我们需要同步代码块），所以可能应该有一个专门用于需求时的传感器？

Answer 3

评论由：alexmiller

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

是的，传感器可以在多个线程中一起使用（例如在 core.async 的 go 块中的 transducer chan）。

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] 以下是一个快速测试，显示在一个线程中对暂态集合（实际上 nothing but a wrapper around transient map）所做的更改，并不总是可见于另一个线程。

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

这意味着如果我们尝试使用暂态对象来例如 distinct，它将错过重复项

Answer 8

注释由：tonsky 提出

从 distinct 的 transducer 形参中移除了 transients，因为 transducers 可能会被多线程访问

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

我必须承认，我的测试证明的并非是我最初设想的内容：没有适当的线程隔离。因此，这是一个并发问题，而不是“安全发布”问题。我的当前理解是这样的

bq. 瞬时（transients）需要线程隔离。特定瞬时实例的使用应受控，要么在其单线程环境中使用，要么在一个强制执行此要求的框架中使用。

这种保证隐含地假设了来自多个线程的瞬时使用之间存在发生之前（happens-before）的关系。没有其他方式来定义“一次只有一个线程在此部分”。

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

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

Answer 12

注释由：tonsky 提出

此外，持久化的瞬时（例如，与队列关联的transducers）将持有创建它们的线程的引用。这是否是一件坏事？我们应该改用布尔标志吗？

Answer 13

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