通过使用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集合可以被原地修改
转换器是否打算在多个线程中同时使用？因为现有的实现明显存在竞争条件。我想象修复这个问题将耗费很大代价（我们需要一个同步代码区域），因此可能应该有一个仅在需要时使用的专用转换器？

Answer 3

评论者：alexmiller

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

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

Answer 4

评论者：alexmiller

我应该指出，转换器并不预期会被多个线程同时使用，因此不存在竞争问题。但长期来看，从多个线程使用需要正确安全地发布。

Answer 5

评论者：tonsky

引用。长期来看，从多个线程使用需要正确安全地发布。

这是否意味着在转换器中不能使用瞬态（因为瞬态实现所基于的底层数组是原地修改的，所以不同的线程可能会看到瞬态对象的不同状态）？

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

引用。瞬态集合无法原地修改 - 必须使用返回值。

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

Answer 6

评论者：alexmiller

引用。这是否意味着在转换器中不能使用瞬态（因为瞬态实现所基于的底层数组是原地修改的，所以不同的线程可能会看到瞬态对象的不同状态）？

瞬态对象只需要确保同时不被超过一个线程访问，因此在传输器中使用是安全的。然而，它们应确保发布的安全性。核心异步通道作为其实施的一种副产品已经做到了这一点，但其他传输器上下文可能就不行。

无论并发与否，禁忌对象绝对不应该用作“原地突变”。尽管在某些情况下它们可能看似“工作”，但这从根本上来说是错误的（最终更新操作将返回一个新的实例；如果您原地突变，那么您将丢失数据）。相关信息和正确示例在 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 的转换符 arity 中删除了瞬态。

Answer 9

评论者：tonsky

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

Answer 10

评论者：alexmiller

我会说这个测试是在证明瞬态集/映射的 bug，您应该为这个 bug 提票，因为它的价值远大于这个增强。

distinct 应该能够在转换器和懒序列实现中使用瞬态。contains? 不会在瞬态上工作的问题实际上是另一个单独的问题 - http://dev.clojure.org/jira/browse/CLJ-700，它可能需要一些类层次结构的重排。我认为我们不会在修复这个问题之前采取这个更改（这样您就可以避免依赖于类和 Java 方法变体）。

Answer 11

评论者：tonsky

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

bq. 临时对象需要线程隔离。使用特定的临时实例应通过将其用于单线程范围或强制执行该规则的框架来控制。

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

这反过来又意味着，无论涉及的变量的易变性如何，1号线发生的所有写入操作都对2号线可见。实际上，我们可以从临时对象的实现中删除所有易变变量，并可能使它们更快，因为我们通过请求“一次不超过一个线程”来强制用户在部分之间建立“发生之前”关系，这将给出我们所需的全部安全发布保证。

我的理解正确吗？我错失了什么吗？

Answer 12

评论者：tonsky

此外，长期存在的临时对象（例如与队列关联的变换器中的）会保留创建它们的线程的引用。这是一件坏事吗？我们应该切换到布尔标志吗？

Answer 13

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