STM性能不佳/锁定

Question

我正在编写一个程序,其中有大量代理监听事件并对它们做出反应.由于Control.Concurrent.Chan.dupChan被弃用,我决定使用TChan的广告.

TChan的表现比我预期的要糟糕得多.我有以下程序来说明问题:

{-# LANGUAGE BangPatterns #-}

module Main where

import Control.Concurrent.STM
import Control.Concurrent
import System.Random(randomRIO)
import Control.Monad(forever, when)

allCoords :: [(Int,Int)]
allCoords = [(x,y) | x <- [0..99], y <- [0..99]]

randomCoords :: IO (Int,Int)
randomCoords = do
  x <- randomRIO (0,99)
  y <- randomRIO (0,99)
  return (x,y)

main = do
  chan <- newTChanIO :: IO (TChan ((Int,Int),Int))

  let watcher p = do
         chan' <- atomically $ dupTChan chan
         forkIO $ forever $ do
                    r@(p',_counter) <- atomically $ readTChan chan'
                    when (p == p') (print r)
         return ()

  mapM_ watcher allCoords

  let go !cnt = do
       xy <- randomCoords
       atomically $ writeTChan chan (xy,cnt)
       go (cnt+1)

  go 1

编译(-O)并运行程序时,首先会输出如下内容:

./tchantest
((0,25),341)
((0,33),523)
((0,33),654)
((0,35),196)
((0,48),181)
((0,48),446)
((1,15),676)
((1,50),260)
((1,78),561)
((2,30),622)
((2,38),383)
((2,41),365)
((2,50),596)
((2,57),194)
((3,19),259)
((3,27),344)
((3,33),65)
((3,37),124)
((3,49),109)
((3,72),91)
((3,87),637)
((3,96),14)
((4,0),34)
((4,17),390)
((4,73),381)
((4,74),217)
((4,78),150)
((5,7),476)
((5,27),207)
((5,47),197)
((5,49),543)
((5,53),641)
((5,58),175)
((5,70),497)
((5,88),421)
((5,89),617)
((6,0),15)
((6,4),322)
((6,16),661)
((6,18),405)
((6,30),526)
((6,50),183)
((6,61),528)
((7,0),74)
((7,28),479)
((7,66),418)
((7,72),318)
((7,79),101)
((7,84),462)
((7,98),669)
((8,5),126)
((8,64),113)
((8,77),154)
((8,83),265)
((9,4),253)
((9,26),220)
((9,41),255)
((9,63),51)
((9,64),229)
((9,73),621)
((9,76),384)
((9,92),569)
...

然后,在某些时候,将停止写任何东西,同时仍然消耗100%的CPU.

((20,56),186)
((20,58),558)
((20,68),277)
((20,76),102)
((21,5),396)
((21,7),84)

使用-threaded,锁定速度更快,仅在少数几行之后发生.它还将消耗通过RTS'-N标志提供的任意数量的内核.

此外,性能似乎相当差 - 每秒只处理大约100个事件.

这是STM中的错误还是我误解了STM的语义？

Answer 1

该计划将表现得非常糟糕.你将产生10,000个线程,所有这些线程都会排队等待单个TVar被写入.所以一旦他们全力以赴,你很可能会发生这种情况:

1. 10,000个线程中的每一个都尝试从通道读取,发现它为空,并将其自身添加到底层TVar的等待队列中.因此,您将在TVar的等待队列中拥有10,000个队列事件和10,000个进程.
2. 有东西被写入频道.这将使10,000个线程中的每一个出错并将其放回运行队列(这可能是O(N)或O(1),具体取决于RTS的写入方式).
3. 然后,10,000个线程中的每个线程必须处理该项目以查看它是否对它感兴趣,而大多数线程都不会.

因此每个项目将导致处理O(10,000).如果您每秒看到100个事件,则意味着每个线程需要大约1微秒才能唤醒,读取几个TV,写入一个并再次排队.这似乎并不那么无理.我不明白为什么程序会彻底停止.

一般情况下,我会废弃此设计并将其替换如下:

有一个线程读取事件通道,它维护从坐标到感兴趣的接收器通道的映射.然后,单个线程可以挑选出从澳地图接收器(一个或多个)(日志N)的时间(比O(N)好多了,并与参与小得多常数因子),并发送事件只是感兴趣的接收器.因此,您只需向相关方执行一两次通信,而不是与所有人进行10,000次通信.这个想法的基于列表的形式写在CHP的本文第5.4节:http://chplib.files.wordpress.com/2011/05/chp.pdf

Answer 2

这是一个很好的测试案例!我认为你实际上创造了一个罕见的真正活锁/饥饿的例子.我们可以通过编译-eventlog和运行-vst来编译,或者通过编译-debug和运行来测试它-Ds.我们看到,即使程序"挂起",运行时仍然像疯了一样工作,在被阻塞的线程之间跳转.

高级别的原因是你有一个(快速)作家和许多(快速)读者.读者和作者都需要访问表示队列末尾的相同tvar.假设一个线程成功,并且在发生这种情况时所有其他线程都失败了.现在,当我们将争用中的线程数增加到100*100时,读者快速进展的概率趋向于零.与此同时,作者实际上访问该tvar 所需的时间比读者更长,因此使事情变得更糟.

在这种情况下,在编写器的每次调用之间放一个小油门go(比方说threadDelay 100)就足以解决问题了.它为读者提供了足够的时间来连续写入之间的所有阻塞,因此消除了活锁.但是,我确实认为改善运行时调度程序的行为以处理这种情况将是一个有趣的问题.

Answer 3

除了Neil所说的,你的代码还有一个空间泄漏(明显更小n):通过使元组严格修复明显的元组构建问题后,我留下了以下配置文件:我认为,这里发生的是主线程将数据写入共享的TChan速度比工作线程可以读取它的速度快(TChan就像Chan是无限制的).因此,工作线程花费大部分时间重新执行各自的STM事务,而主线程忙于将更多数据填充到通道中; 这解释了为什么你的程序挂起了.