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

Question

当前{{clojure.core/distinct}}的实现使用持久集合。这个补丁通过使用transient集合，将懒arity的性能提高了约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

您不能移除volatile - 在多线程transducing环境中还需要它以确保安全发布。

Answer 2

_评论由：tonsky_

[~alexmiller] 你怎么说的？

- 我不更新{{seen}}链接，因为transient集合可以就地修改
- 是否打算在多线程中使用transducers？因为现有的实现显然存在竞争条件。我想修复这个可能会很昂贵（我们需要一个同步段），所以也许应该是一个仅在需要时使用的专用transducer？

Answer 3

评论由：alexmiller

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

是的，在 (例如) core.async 的 transducer chan 中，transducers 可以从多个线程中使用。

Answer 4

评论由：alexmiller

我还应该说的是，期望 transducers 在一次不可能由多个线程使用，因此不存在竞争问题。但随着时间的推移，在多个线程中使用需要正确的安全发布。

Answer 5

_评论由：tonsky_

引用。但随着时间的推移，从多个线程中使用需要正确的安全发布。

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

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

引用。瞬态集合不允许就地修改 - 您必须使用返回值。

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

Answer 6

评论由：alexmiller

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

瞬态只要求它们一次只被一个线程询问，因此可以在 transducer 中安全使用。但是，它们应该保证安全发布。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

这意味着如果我们尝试使用“转瞬即逝的”来执行 e.g. distinct 操作，将会丢失重复的项

Answer 8

来自：tonsky

从 distinct 的 transducer 阶段移除了 transients，因为 transducer 可能会被多个线程访问

Answer 9

_评论由：tonsky_

或许，文档https://clojure.org/reference/transients应该针对这一点进行更新：由于一个线程所做的更改可能不会对另一个线程可见，因此“转瞬即逝的”在多个线程中是不安全的。即使它们没有竞争也是如此。

Answer 10

评论由：alexmiller

我认为，这个测试项展示了 transient 集合/映射中的一个 bug，你应该为这个 bug 提交一个 ticket，因为这个 bug 的修复比这个增强更重要。

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

Answer 11

_评论由：tonsky_

我必须承认我的测试证明了其他事情：没有适当的线程隔离。所以这是一个并发问题，而不是“安全发布”问题。我目前的理解是这个

注意。瞬态需要线程隔离。特定瞬态实例的使用应通过在其单线程范围内使用或在一个强制执行此的框架中使用来控制。

这个保证隐含地假定多个线程中的瞬态使用之间存在发生之前的关系。没有其他方法可以定义“一次只有一个线程在这个部分”。

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

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

Answer 12

来自：tonsky

此外，长期存在的瞬态（例如，与队列关联的转置器中的瞬态）将保留一个指向创建它们的线程的引用。这是件坏事吗？我们应该切换到布尔标志吗？

Answer 13

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