20

我正在编写一个程序，其中大量代理侦听事件并对其做出反应。由于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的语义？

4

3 回答 3

21

该程序将执行得很糟糕。您正在生成 10,000 个线程，所有这些线程都将排队等待写入单个 TVar。因此，一旦它们全部启动，您很可能会发生这种情况：

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

所以每个项目都会导致处理 O(10,000)。如果您看到每秒 100 个事件，这意味着每个线程需要大约 1 微秒才能唤醒，读取几个 TVar，写入一个并再次排队。这似乎并没有那么不合理。不过，我不明白为什么该程序会完全停止。

一般来说，我会废弃这个设计并替换它，如下所示：

有一个线程读取事件通道，它维护从坐标到感兴趣接收器通道的映射。然后，单线程可以在 O(log N) 时间内从地图中挑选出接收者（比 O(N) 好得多，并且涉及的常数因子要小得多），并将事件发送给感兴趣的接收者. 因此，您只与相关方进行一两次通信，而不是与每个人进行 10,000 次通信。该想法的基于列表的形式在本文的第 5.4 节中用 CHP 编写：http: //chplib.files.wordpress.com/2011/05/chp.pdf

于 2011-06-22T13:22:06.793 回答
9

这是一个很好的测试案例！我认为您实际上已经创建了一个罕见的真正活锁/饥饿实例。我们可以通过编译-eventlog和运行-vst或通过编译-debug和运行来测试它-Ds。我们看到，即使程序“挂起”，运行时仍然在疯狂地工作，在阻塞的线程之间跳转。

高层次的原因是你有一个（快速）作家和许多（快速）读者。读取器和写入器都需要访问表示队列末尾的同一个 tvar。假设发生这种情况时，一个线程不确定地成功，而所有其他线程都失败了。现在，当我们将争用线程数增加到 100*100 时，阅读器取得进展的概率迅速趋近于零。与此同时，实际上作者访问该 tvar 所需的时间比阅读者要长，这使得事情变得更糟。

在这种情况下，在每次调用gowriter 之间放一个小节流（比如threadDelay 100）就足以解决问题。它给读者足够的时间在连续写入之间全部阻塞，从而消除活锁。但是，我确实认为改进运行时调度程序的行为以处理此类情况将是一个有趣的问题。

于 2011-06-22T14:43:08.780 回答
6

添加到 Neil 所说的内容中，您的代码也有空间泄漏（通过更小更明显n）：通过使 tuples strict空间泄漏解决明显的元组构建问题后，我得到了以下配置文件：我认为这里发生了什么主线程将数据写入共享数据的速度比工作线程读取数据的速度要快（像 一样，是无界的）。因此，工作线程大部分时间都在重新执行各自的 STM 事务，而主线程则忙于将更多数据填充到通道中；这解释了为什么您的程序挂起。具有严格元组的配置文件TChanTChanChan

于 2011-06-22T14:23:19.363 回答