Низкая производительность/блокировка с помощью STM

Я пишу программу, в которой большое количество агентов слушает события и реагирует на них. Поскольку 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
                    [email protected](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% процессор.

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

С -пожаром блокировка выполняется быстрее и происходит только после нескольких строк. Он также будет потреблять любое количество ядер, доступных через флаг RTS -N.

Кроме того, производительность кажется довольно низкой - обрабатывается только около 100 событий в секунду.

Является ли это ошибкой в STM или я что-то не понимаю о семантике STM?

Ответ 1

Программа будет работать довольно плохо. Вы создаете 10 000 потоков, все из которых будут стоять в очереди, ожидая, когда будет записан один TVar. Поэтому, как только они все пойдут, вы вполне можете это сделать:

Каждый из 10 000 потоков пытается прочитать из канала, находит его пустым и добавляет себя в очередь ожидания для базового TVar. Таким образом, у вас будет 10 000 событий очереди и 10 000 процессов в очереди ожидания для TVar.
Что-то записывается на канал. Это приведет к немедленному вызову каждого из 10000 потоков и вернет его в очередь выполнения (это может быть O (N) или O (1), в зависимости от того, как записывается RTS).
Каждый из 10 000 потоков должен затем обработать элемент, чтобы узнать, интересуется ли он им, чего больше не будет.

Таким образом, каждый элемент вызовет обработку O (10000). Если вы видите 100 событий в секунду, это означает, что каждый поток требует около 1 микросекунды, чтобы проснуться, прочитать пару ТВАР, записать в один и снова поставить в очередь. Это не кажется столь необоснованным. Я не понимаю, почему программа остановилась бы на полной остановке.

В общем, я бы отказался от этой конструкции и заменил ее следующим образом:

Проведите один поток, читающий канал событий, который поддерживает карту от координаты к каналу интересующего-приемника. Один поток может затем выбрать приемник с карты в O (log N) времени (намного лучше, чем O (N) и с гораздо меньшим постоянным фактором) и отправить событие только заинтересованному получателю, Таким образом, вы выполняете только одну или две сообщения для заинтересованной стороны, а не 10 000 сообщений для всех. Форма идеи на основе списков написана в CHP в разделе 5.4 настоящей статьи: http://chplib.files.wordpress.com/2011/05/chp.pdf

Ответ 2

Это отличный тест! Я думаю, что вы на самом деле создали редкий случай подлинного оживления/голодания. Мы можем протестировать это, скомпилировав с помощью -eventlog и работая с -vst или компилируя с помощью -debug и работая с -Ds. Мы видим, что даже когда программа "зависает", среда выполнения все еще работает как сумасшедшая, прыгая между заблокированными потоками.

Причина высокого уровня заключается в том, что у вас есть один (быстрый) писатель и множество (быстрых) читателей. Читатели и писатели должны получить доступ к одному и тому же твару, представляющему конец очереди. Скажем, что недетерминистически один поток преуспевает, а все остальные терпят неудачу, когда это происходит. Теперь, когда мы увеличиваем количество потоков в конфликте до 100 * 100, вероятность того, что читатель быстро прогрессирует, приближается к нулю. Между тем, писатель фактически занимает больше времени в своем доступе к этому твари, чем читатели, что ухудшает его.

В этом случае достаточно установить крошечный дроссель между каждым вызовом go для писателя (например, threadDelay 100), чтобы исправить проблему. Это дает читателям достаточно времени, чтобы все блокировалось между последовательными записями и таким образом устраняло ожидание. Однако я думаю, что было бы интересной проблемой для улучшения поведения планировщика времени выполнения, чтобы справляться с такими ситуациями.

Ответ 3

Добавляя к тому, что сказал Нил, ваш код также имеет утечку пространства (заметен с меньшим n): После исправления очевидной проблемы наращивания кортежа установив строчные строчки, мне остался следующий профиль: То, что происходит здесь, я думаю, состоит в том, что основной поток записывает данные в общий TChan быстрее, чем рабочие потоки могут читать (TChan, как Chan, неограничен). Поэтому рабочие потоки проводят большую часть своего времени, перерабатывая свои соответствующие транзакции STM, в то время как основной поток занят заполнением еще большего количества данных в канал; это объясняет, почему ваша программа зависает.