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

Question

当前{{clojure.core/distinct}}的实现使用持久集合。此补丁通过使用transient集合而不是持久集合，将惰性算子和transducer的性能分别提高了约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。您仍需要在多线程transducing上下文中安全发布时使用它。

Answer 2

评论由：tonsky

[~alexmiller] 您是什么意思？

- 我没有更新 {{seen}} 链接，因为transient集合可以就地修改。
—are transducers intended to be used by multiple threads? Because the existing implementation clearly has a race condition. I imagine fixing this would be expensive (we'll need a synchronized section), so maybe it should be a specialized transducer that you only use when necessary?

Answer 3

评论由：alexmiller

非持久化集不能就地修改 - 您必须使用返回值。

是的，在核心异步go块中（例如，transducer通道）会从多个线程中使用transducers。

Answer 4

评论由：alexmiller

我也想说，transducers不应该一次性被多个线程访问，因此不存在竞争问题。但是随着时间的推移，从多个线程使用确实需要适当的保护发布。

Answer 5

评论由：tonsky

bq. 但是随着时间的推移，从多个线程使用确实需要适当的保护发布。

这是否意味着在transducer中不能使用任何非持久化实例（因为非持久化实例所依据的底层数组是就地修改的，所以不同的线程可能会看到非持久化对象的不同的状态）？

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

bq. 非持久化集不能就地修改 - 您必须使用返回值。

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

Answer 6

评论由：alexmiller

{quote}这是否意味着在transducer中不能使用任何非持久化实例（因为非持久化实例所依据的底层数组是就地修改的，所以不同的线程可能会看到非持久化对象的不同的状态）？{quote}

非持久化要求它们在同一时间内只能被单个线程请求，因此可以在transducer中安全使用。但是，它们应该保证安全的发布。核心异步通道已经作为实现的结果这样做，但其他transucing环境可能不会。

瞬态对象永远不应该用作“原地修改”，不管在任何并发环境下。虽然在某些情况下它们看起来似乎“可以工作”，但这绝对是不正确的（最终更新操作会返回一个新实例，如果你正在原地修改，那么你将丢失数据）。这已经在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

由于transducers可能会被多线程访问，从distinct的transducer arity中移除了瞬态对象

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. 临时变量需要线程隔离。特定临时实例的使用应该通过在单线程范围内使用它或在强制执行此规则的框架中使用它来控制。

这个保证隐含地假定，多个线程之间的临时变量使用存在“happens-before”关系。没有其他方法可以定义“一次只有一个线程在这个部分”。

这反过来意味着，在1号线程中发生的所有写入对于2号线程都是可见的，无论涉及的变量的易变性如何。事实上，我们可以从临时变量的实现中删除所有易变性，也许可以使它们更快，因为通过要求“一次只有一个线程”，我们强制用户在部分之间建立happens-before关系，这将给我们所有需要的安全发布保证。

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

Answer 12

评论者：tonsky

此外，长寿的临时变量（例如，与队列关联的转换器中的临时变量）将保留对创建它们的线程的引用。这是不好的吗？我们应该切换到布尔标志吗？

Answer 13

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