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フラグを介して利用できるコアの数も消費します。

さらに、パフォーマンスはかなり悪いようです。1秒あたり約100のイベントのみが処理されます。

これはSTMのバグですか、それともSTMのセマンティクスについて何か誤解していますか?

4

3 に答える 3

21

プログラムのパフォーマンスはかなり悪くなります。あなたは 10,000 のスレッドを生成しており、そのすべてが 1 つの TVar に書き込まれるのを待ってキューに入れられます。したがって、すべてがうまくいくと、次のことが起こる可能性があります。

  1. 10,000 個のスレッドのそれぞれがチャネルからの読み取りを試行し、チャネルが空であることを確認して、基礎となる TVar の待機キューに自身を追加します。したがって、10,000 のキューアップ イベントと、TVar の待機キューに 10,000 のプロセスがあります。
  2. チャネルに何かが書き込まれます。これにより、10,000 個のスレッドのそれぞれがキューから取り出され、実行キューに戻されます (これは、RTS の記述方法に応じて、O(N) または O(1) になる場合があります)。
  3. 次に、10,000 のスレッドのそれぞれがアイテムを処理して、アイテムに関心があるかどうかを確認する必要がありますが、ほとんどのスレッドはそうではありません。

したがって、各アイテムは処理 O(10,000) を引き起こします。1 秒あたり 100 個のイベントが表示される場合、各スレッドがウェイクアップし、いくつかの TVar を読み取り、1 つに書き込み、再びキューに入れるのに約 1 マイクロ秒かかることを意味します。それはそれほど不合理ではないようです。ただし、プログラムが完全に停止する理由はわかりません。

一般的に、私はこのデザインを破棄して、次のように置き換えます。

座標から興味のある受信者チャネルへのマップを維持するイベント チャネルを読み取る単一のスレッドを用意します。単一のスレッドは、O(log N) 時間 (O(N) よりもはるかに優れており、関与する定数係数がはるかに小さい) でマップから受信者を選択し、関心のある受信者だけにイベントを送信できます。 . したがって、全員に 10,000 回の通信を行うのではなく、関心のある当事者に 1 つか 2 つの通信を行うだけです。この論文のセクション 5.4 では、CHP でアイデアのリストベースの形式が書かれています。

于 2011-06-22T13:22:06.793 に答える
9

これは素晴らしいテストケースです!本物のライブロック/飢餓のまれなインスタンスを実際に作成したと思います。-eventlogでコンパイルして実行する-vstか、 でコンパイルし-debugて実行することにより、これをテストできます-Ds。プログラムが「ハング」しても、ランタイムは依然として狂ったように動作し、ブロックされたスレッド間をジャンプしていることがわかります。

大まかな理由は、1 つの (高速) ライターと多数の (高速) リーダーがあるためです。リーダーとライターの両方が、キューの最後を表す同じ tvar にアクセスする必要があります。これが発生すると、非決定論的に 1 つのスレッドが成功し、他のすべてのスレッドが失敗するとします。ここで、競合するスレッドの数を 100*100 に増やすと、リーダーが進行する確率は急速にゼロに近づきます。その間、ライターは実際には、リーダーよりもその tvar へのアクセスに時間がかかるため、事態はさらに悪化します

goこの場合、ライター (たとえば)の各呼び出しの間に小さなスロットルを配置threadDelay 100するだけで、問題を解決するのに十分です。これにより、連続する書き込みの間のすべてのブロックに十分な時間がリーダーに与えられるため、ライブロックが排除されます。しかし、このような状況に対処するためにランタイム スケジューラの動作を改善することは興味深い問題だと思います

于 2011-06-22T14:43:08.780 に答える
6

Neilが言ったことに加えて、コードにもスペースリークがあります(小さい方が目立ちますn):タプルを厳密スペースリークにすることで明らかなタプルビルドアップの問題を修正した後、次のプロファイルが残りました:ここで何が起こっているのか、私は思いますメインスレッドは、ワーカースレッドがデータを読み取ることができるよりも速く共有にデータを書き込んでいます(のように、無制限です)。そのため、ワーカースレッドはほとんどの時間をそれぞれのSTMトランザクションの再実行に費やしますが、メインスレッドはさらに多くのデータをチャネルに詰め込むのに忙しくなります。これは、プログラムがハングする理由を説明しています。厳密なタプルを使用したプロファイルTChanTChanChan

于 2011-06-22T14:23:19.363 に答える