通过使用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_

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] 这里有一个快速测试展示了在某个线程中对 transient set（实际上是 transient map 的包装）进行的修改，有时并不能在另一个线程中看到。

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

这意味着如果我们尝试使用瞬态for例，例如distinct，就会错过重复的项目

Answer 8

评论者：tonsky

由于转换器可能从多个线程访问，已从 distinct 的转换器 arity 中删除瞬态。

Answer 9

_评论者：tonsky_

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

Answer 10

评论者：alexmiller

我会说这个测试证明了 transient set/maps 中有一个错误，你应该为这个错误提交一个票证，因为它的意义比这个增强更重要。

distinct 应该能够在转换器和懒惰序列实现中使用瞬态。contains? 在瞬态中不起作用的真正问题是一个单独的票证 - http://dev.clojure.org/jira/browse/CLJ-700，这可能会需要一些类层次结构的重新排列。我认为我们不会采纳这个更改，直到这个问题得到解决（这样你就可以避免依赖于类和 Java 方法变体）。

Answer 11

_评论者：tonsky_

我必须承认我的测试演示了其他事情：没有适当的线程隔离。因此，这是一个并发问题，而不仅仅是“安全发布”问题。我现在的理解是

bq.瞬态需要线程隔离。特定的瞬态实例的使用应该通过在单线程环境中使用或在强制执行此要求的框架中使用来控制。

这个保证隐式地假设多个线程之间的瞬态使用存在happens-before关系。没有其他方法可以定义“一次只有一个线程在这个区域”。

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

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

Answer 12

评论者：tonsky

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

Answer 13

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