通过使用瞬时集合改进clojure.core/distinct性能

Question

{{clojure.core/distinct}}的当前实现使用持久集合。此补丁通过使用瞬时集合而不是持久集合，将惰性性能提高了约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

不能移除可变的 —— 你仍然需要在多线程transducing上下文中安全发布时使用它。

Answer 2

评论由：tonsky_

[~alexmiller] 你的意思是什么？

- 我没有更新{{seen}}链接，因为在瞬时集合中可以原地修改。
- transducer打算由多个线程使用吗？因为即使是现有的实现也很明显存在竞态条件。我想修复这将是昂贵的（我们需要一个同步块），所以可能应该是一个专门的transducer，你只在需要时使用？

Answer 3

评论由：alexmiller

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

是的，在使用 transducer chans 的 core.async go 块中，会使用多线程中的 transducers。

Answer 4

评论由：alexmiller

我还应该指出，transducers 不应该同时在多于一个线程中使用，因此不存在竞争问题。但长时间从多个线程使用需要适当的安全生产。

Answer 5

评论由：tonsky_

bq. 但长时间从多个线程使用需要适当的安全生产。

这是否意味着在 transducers 中不能使用瞬态（因为瞬态实现所依赖的基本数组是在就地修改的，因此不同的线程可能会看到瞬态对象的不同状态）？

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

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

我在想，{{clojure/core.clj}} 和 {{clojure.lang.ATransientSet.java}} 都是 Clojure 内部的一部分，位于同一位置，因此可以共享一些关于彼此的内部知识。这样做似乎是安全的，因为这种知识不会渗漏到外部，并且如果 ATransientSet 的实现在任何时候发生变化，core.clj 就可以在同一版本中相应更新。当然，我不会在第三方库中这样做。

Answer 6

评论由：alexmiller

{quote}这是否意味着在 transducers 中不能使用瞬态（因为瞬态实现所依赖的基本数组是在就地修改的，因此不同的线程可能会看到瞬态对象的不同状态）？{quote}

瞬态仅要求一次被一个线程调用，因此可以在 transducer 中安全使用。但是，它们应该保证安全发布。core.async 通道作为其实现的一个产物已经这样做了，但其他 transuding 上下文可能没有。

瞬态在不考虑并发的情况下永远不应该用作“就地修改”。虽然在某些情况下它们看起来可能“工作”，但这永远是不正确的（最终更新操作将返回一个新的实例，如果就地修改，您的数据将丢失）。这已在 https://clojure.org/reference/transients 中讨论，并展示了正确的示例。

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

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

Answer 7

评论由：tonsky_

[~alexmiller] 这里有一个快速测试，它表明一个线程中对 transient set（它不过是一个 transient map 的封装）所做的更改在某些情况下并不能被另一个线程看到。

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

这意味着如果我们尝试使用 transient 进行如 distinct 等，可能会错过重复项

Answer 8

评论者：tonsky

因为 transducer 可能会被多个线程访问，所以从 distinct 的 transducer 算子中移除了 transient

Answer 9

评论由：tonsky_

可能该文档 https://clojure.org/reference/transients 应该更新关于 transients 不安全在多个线程中使用，因为一个线程所做的更改可能对另一个线程不可见。即使它们没有竞争

Answer 10

评论由：alexmiller

我会说这个测试显示了 transient set/maps 中的一个 bug，你应该为这个 bug 提交一个工单因为它比这个增强更重要。

distinct 应该能够在 transducer 和懒惰序列实现中同时使用 transient。contains? 不能在 transients 上工作的问题实际上是一个单独的工单 - http://dev.clojure.org/jira/browse/CLJ-700，这可能需要对类层次结构进行调整。我认为我们不会在解决这个问题之前进行这个更改（这样你就可以避免依赖于类和 Java 方法变体）。

Answer 11

评论由：tonsky_

我必须承认我的测试表明了其他东西：没有适当的线程隔离。所以这是一个并发问题，而不是“安全发布”问题。我现在的理解是这样的：

引用。Transients 需要线程隔离。特定 transient 实例的使用应该由在单线程范围内使用它或在一个强制执行此操作的框架中控制。

这种保证隐含地假设了多个线程之间的瞬时的“发生在前”关系。没有其他方法来定义“一次只有一条线程在这个部分”。

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

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

Answer 12

评论者：tonsky

此外，长期存在的瞬时（例如，与队列关联的变换器中的瞬时）将保持对其创建它们的线程的引用。这是否是件坏事？我们应该改用布尔标志吗？

Answer 13

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