performance - Mal rendimiento/bloqueo con STM

haskell concurrency

Question

Estoy escribiendo un programa donde una gran cantidad de agentes escuchan los eventos y reaccionan ante ellos. Como Control.Concurrent.Chan.dupChan está en desuso, decidí usar TChan como se anunciaba.

El rendimiento de TChan es mucho peor de lo que esperaba. Tengo el siguiente programa que ilustra el problema:

{-# 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

Cuando se compile (-O) y ejecute el programa primero se mostrará algo como esto:

./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) ...

Y luego, en algún momento, dejará de escribir cualquier cosa, mientras siga consumiendo el 100% de la CPU.

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

Con -trabajo, el bloqueo es aún más rápido y se produce solo después de unas pocas líneas. También consumirá cualquier número de núcleos disponibles a través de RTS ''-N flag.

Además, el rendimiento parece bastante bajo: solo se procesan unos 100 eventos por segundo.

¿Es esto un error en STM o estoy malinterpretando algo acerca de la semántica de STM?

Answer 1

Además de lo que dijo Neil, su código también tiene una fuga de espacio (notable con una n más pequeña): Después de solucionar el problema obvio de acumulación de tuplas al hacerlas tuplas , me quedé con el siguiente perfil: Lo que sucede aquí, creo, es que el hilo principal es escribir datos en el TChan compartido más rápido de lo que los hilos del trabajador pueden leerlo ( TChan , como Chan , no tiene límites). Por lo tanto, los subprocesos de trabajo pasan la mayor parte del tiempo ejecutando sus respectivas transacciones STM, mientras que el subproceso principal está ocupado introduciendo aún más datos en el canal; Esto explica por qué su programa se cuelga.

Answer 2

El programa va a funcionar bastante mal. Usted está generando 10,000 hilos, todos los cuales harán cola esperando a que se escriba una única TVar. Así que una vez que todos estén yendo, puede que esto suceda:

1. Cada uno de los 10,000 hilos intenta leer desde el canal, lo encuentra vacío y se agrega a la cola de espera para el TVar subyacente. Por lo tanto, tendrá 10,000 eventos de cola y 10,000 procesos en la cola de espera para el TVar.
2. Algo está escrito en el canal. Esto pondrá en cola cada uno de los 10,000 hilos y los volverá a poner en la cola de ejecución (esto puede ser O (N) u O (1), dependiendo de cómo esté escrito el RTS).
3. Cada uno de los 10,000 hilos debe procesar el elemento para ver si está interesado en él, y la mayoría no lo estará.

Entonces cada ítem causará el procesamiento O (10,000). Si ve 100 eventos por segundo, eso significa que cada hilo requiere aproximadamente 1 microsegundo para despertarse, leer un par de TVars, escribir en uno y volver a hacer una cola. Eso no parece tan irrazonable. Sin embargo, no entiendo por qué el programa se detendría por completo.

En general, desecharía este diseño y lo reemplazaría de la siguiente manera:

Haga que un solo hilo lea el canal del evento, que mantiene un mapa desde las coordenadas al canal receptor interesado. El único hilo puede seleccionar el (los) receptor (es) del mapa en tiempo O (registro N) (mucho mejor que O (N), y con un factor constante mucho menor involucrado), y enviar el evento solo al receptor interesado . Por lo tanto, solo realiza una o dos comunicaciones a la parte interesada, en lugar de 10.000 comunicaciones para todos. Una forma basada en listas de la idea está escrita en CHP en la sección 5.4 de este documento: http://chplib.files.wordpress.com/2011/05/chp.pdf

Answer 3

Este es un gran caso de prueba! Creo que en realidad has creado una instancia rara de Livelock / inanición genuina. Podemos probar esto compilando con -eventlog y ejecutando con -vst o compilando con -debug y ejecutando con -Ds . Vemos que incluso cuando el programa se "cuelga", el tiempo de ejecución aún funciona como un loco, saltando entre hilos bloqueados.

La razón de alto nivel es que tienes un escritor (rápido) y muchos lectores (rápidos). Los lectores y el escritor necesitan acceder al mismo tvar que representa el final de la cola. Digamos que un hilo no determinista es exitoso y todos los demás fallan cuando esto sucede. Ahora, a medida que aumentamos el número de subprocesos en disputa a 100 * 100, entonces la probabilidad de que el lector progrese rápidamente va hacia cero. Mientras tanto, el escritor, de hecho, tarda más tiempo en acceder a ese tvar que los lectores, por lo que eso empeora las cosas.

En este caso, basta con un pequeño acelerador entre cada invocación de go para el escritor (por ejemplo, threadDelay 100 ) para solucionar el problema. Le da a los lectores el tiempo suficiente para bloquear todo entre escrituras sucesivas, y así elimina el bloqueo vital. Sin embargo, creo que sería un problema interesante mejorar el comportamiento del programador de tiempo de ejecución para hacer frente a situaciones como esta.