性能差/與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. 每10000個線程試圖從通道讀取，發現它空，並增加了本身爲基礎的TVar等待隊列。因此，您將有10,000個隊列事件，並且在TVar的等待隊列中有10,000個進程。
2. 將某些內容寫入頻道。這將取消10,000個線程中的每個線程並將其放回到運行隊列中（這可能是O（N）或O（1），具體取決於RTS的寫入方式）。
3. 10,000個線程中的每一個線程都必須處理該項目以查看它是否對其感興趣，而這些線程絕大多數不會。

因此，每個項目將導致處理O（10,000）。如果您每秒看到100個事件，那意味着每個線程都需要大約1微秒的時間才能喚醒，讀取幾個TVar，寫入一個並再次排隊。這似乎並不合理。不過，我不明白爲什麼這個計劃會完全停止。

一般情況下，我會放棄這個設計如下替換：

有一個線程讀取事件通道，它保持的地圖從協調到感興趣的接收器通道。然後，單線程可以在O（logN）時間內（比O（N）好得多並且包含一個小得多的常數因子）從地圖中挑選出接收者，並將事件發送給感興趣的接收者。所以你只向有關方面進行一兩次溝通，而不是向每個人傳達一萬次溝通。第5部分將衛生保健計劃寫成一個基於清單的想法。本文的4：http://chplib.files.wordpress.com/2011/05/chp.pdf

Answer 2

添加到什麼尼爾說，你的代碼也有一個空間泄漏（明顯較小n）：固定明顯的元組堆積問題by making tuples strict後，我留下了以下配置文件： 這裏發生了什麼，我認爲是主線程將數據寫入共享的TChan的速度比工作線程能夠讀取的速度快（TChan，如Chan，無界限）。因此，工作線程spend most of their time重新執行它們各自的STM事務，而主線程正忙於將更多數據填充到通道中;這解釋了爲什麼你的程序掛起。

Answer 3

這是一個很棒的測試案例！我認爲你實際上已經創造了一個真正的活鎖/飢餓罕見的例子。我們可以通過編譯-eventlog並使用-vst或編譯-debug並使用-Ds運行來測試。我們看到，即使程序「掛起」，運行時仍然像瘋了一樣工作，在被阻塞的線程之間跳轉。

高層次的原因是你有一個（快速）作家和許多（快速）閱讀器。讀者和作者都需要訪問代表隊列末尾的相同tvar。比方說，非確定性的一個線程成功，所有其他線程都會失敗。現在，當我們增加競爭線程的數量爲100 * 100時，讀者迅速進展的可能性趨於零。同時，作者實際上比讀者需要更多的來訪問該tvar，所以這讓事情變得更糟。

在這種情況下，在作者（即，threadDelay 100）的每次調用go之間加上一個微小的限制就足以解決問題。它爲讀者提供足夠的時間在連續寫入之間阻止所有塊，並消除活鎖。但是，做認爲改善運行時調度程序處理類似情況的行爲將​​是一個有趣的問題。