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

Question

当前{{clojure.core/distinct}}的实现使用持久集合。该补丁通过使用transient集合将懒惰参数性能提高约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集合可以就地修改
- transducer打算在多线程中使用吗？因为即使现有实现显然存在竞争条件。我想修复这可能会成本很高（我们需要一个同步区段），所以也许它应该是一个专用的transducer，只在需要时使用？

Answer 3

发表评论者：alexmiller

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

是的，转变器可以在多个线程中使用（例如在 core.async 的 go 块中的转变器通道中）。

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 的 transducer 运算符中移除了瞬态对象，因为 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. 可变（transient）需要线程隔离。特定可变实例的使用应该通过在单线程环境中使用它，或在强制执行此要求的框架中来实现来控制。

这种保证隐含地假设了多个线程之间可变使用有 happens-before 关系。没有其他方法来定义“一次只有一个线程位于此部分”。

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

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

Answer 12

评论者：tonsky

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

Answer 13

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