performance - Haskell:并发数据结构指南

Question

我一直在尝试理解并发，并且一直在尝试找出更好的方法，一个大的 IORef锁或多个TVar s。我已经得出以下指导方针，我们将不胜感激，关于这些是否大致正确或我是否错过了重点。

假设我们的并发数据结构是一个映射 m , 像 m[i] 一样访问.假设我们有两个函数，f_easy和 f_hard . f_easy很快，f_hard需要很长的时间。我们将假设 f_easy/f_hard 的参数是 m 的元素.

(1) 如果您的交易大致如下 m[f_easy(...)] = f_hard(...) , 使用 IORef与 atomicModifyIORef .懒惰将确保m只锁定了很短的时间，因为它是用 thunk 更新的。计算索引有效地锁定了结构(因为有些东西会被更新，但我们还不知道是什么)，但是一旦知道那个元素是什么，整个结构上的 thunk 就会移动到仅在那个特定元素上的 thunk ，然后只有那个特定的元素被“锁定”。

(2) 如果您的交易大致如下 m[f_hard(...)] = f_easy(...) ，并且不要冲突太多，使用大量TVar s。使用 IORef在这种情况下，将有效地使应用程序成为单线程，因为您不能同时计算两个索引(因为整个结构上会有一个 Unresolved thunk)。 TVar s 让你同时计算出两个索引，但是，不利的是，如果两个并发事务都访问同一个元素，并且其中一个是写入，则必须废弃一个事务，这会浪费时间(本来可以在别处使用)。如果这种情况经常发生，那么使用来自 IORef 的锁(通过黑洞)可能会更好。 ，但如果它不经常发生，您将获得更好的并行性 TVar s。

基本上在情况 (2) 中，使用 IORef您可能会获得 100% 的效率(没有浪费的工作)，但只使用 1.1 线程，但使用 TVar如果您的冲突数量较少，您可能会获得 80% 的效率，但使用 10 个线程，因此即使浪费了工作，您最终仍能快 7 倍。

Answer 1

您的指导方针有点类似于 [1](第 6 节)的结果，其中分析了 Haskell STM 的性能:

"In particular, for programs that do not perform much work inside transactions, the commit overhead appears to be very high. To further observe this overhead, an analysis needs to be conducted on the performance of commit-time course-grain and fine-grain STM locking mechanisms."

我用 atomicModifyIORef或 MVar当我需要的所有同步都是简单锁定将确保的东西时。在查看对数据结构的并发访问时，还取决于该数据结构的实现方式。例如，如果您将数据存储在 IORef Data.Map并经常执行读/写访问然后我认为atmoicModifyIORef正如您所猜想的那样，将降级为单线程性能，但对于 TVar Data.Map 也是如此.我的观点是使用适合并发编程的数据结构很重要(平衡树不是)。

也就是说，在我看来，使用 STM 的获胜论点是可组合性:您可以将多个操作组合成一个事务而不会令人头疼。通常，使用 IORef 是不可能的。或 MVar无需引入新锁。

[1] 软件事务内存 (STM) 的限制:在多核环境中剖析 Haskell STM 应用程序。
http://dx.doi.org/10.1145/1366230.1366241

回复@Clinton 的评论:

如果单个 IORef包含您的所有数据，您可以简单地使用 atomicModifyIORef作曲。但是，如果您需要处理对该数据的大量并行读/写请求，则性能损失可能会变得很大，因为对该数据的每一对并行读/写请求都可能导致冲突。

我会尝试的方法是使用数据结构，其中条目本身存储在 TVar 中。 (与将整个数据结构放入单个 TVar 相比)。这应该会减少活锁的可能性，因为事务不会经常发生冲突。

当然，您仍然希望使您的事务尽可能小，并且仅在绝对有必要保证一致性时才使用可组合性。到目前为止，我还没有遇到过需要将多个插入/查找操作组合到单个事务中的情况。