performance - STM 性能不佳/锁定

Question

我正在编写一个程序，其中大量代理监听事件并对其使用react。由于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。因此，一旦它们全部启动，您很可能会发生这种情况:

10,000 个线程中的每一个都尝试从 channel 读取，发现它是空的，然后将自己添加到底层 TVar 的等待队列中。因此，您将有 10,000 个排队事件，以及 TVar 的等待队列中的 10,000 个进程。

某些内容被写入 channel 。这将使 10,000 个线程中的每一个都出队并将其放回运行队列(这可能是 O(N) 或 O(1)，具体取决于 RTS 的编写方式)。

然后，10,000 个线程中的每一个都必须处理该项目以查看它是否对它感兴趣，而大多数线程不会对此感兴趣。

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

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

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