性能 – Haskell:并发数据结构指南

我一直在努力了解并发性,并且我一直在努力找出更好的东西,一个大的IORef锁或许多TVars.我已经达到了以下指导原则,我们将不胜感激,评论这些是否大致正确,或者我是否错过了这一点.

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

(1)如果您的交易看起来大致类似于m [f_easy(…)] = f_hard(…),请使用带有atomicModifyIORef的IORef.懒惰将确保m只被锁定一小段时间,因为它是用thunk更新的.计算索引有效地锁定了结构(因为某些东西会被更新,但我们还不知道是什么),但是一旦知道该元素是什么,整个结构上的thunk只会移动到thunk上的那个特定元素,然后只有那个特定元素被“锁定”.

(2)如果您的交易看起来大致相同m [f_hard(…)] = f_easy(…),并且不要过多冲突,请使用大量的TVars.在这种情况下使用IORef将有效地使应用程序成为单线程,因为您无法同时计算两个索引(因为在整个结构中将存在未解决的thunk). TVars允许你同时计算出两个索引,但是,否定的是,如果两个并发事务都访问同一个元素,其中一个是写入,则必须废弃一个事务,这会浪费时间(这可能是在别处使用).如果这种情况发生了很多,你可能会更好地使用来自IORef的锁定(通过黑洞),但如果它不会发生很多,你将获得更好的与TVars的并行性.

基本上在情况(2)中,使用IORef你可以获得100%的效率(没有浪费的工作),但只使用1.1线程,但如果你的冲突数量很少,你可以获得80%的效率,但使用10个线程,所以你即使浪费了工作,仍然会快7倍.

您的指南有点类似于[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

回答@克林顿的评论:

如果单个IORef包含您的所有数据,您只需使用atomicModifyIORef进行合成.但是,如果您需要处理大量对该数据的并行读/写请求,则性能损失可能会变得很严重,因为对该数据的每对并行读/写请求都可能导致冲突.

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

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

相关文章
相关标签/搜索