Joel Reymont wrote:
It seems like the real difference between TChan and the Ch code below is that TChan is, basically, [TVar a] whereas Ch is MVar [a], plus the order is guaranteed for a TChan.
Now why would it matter so much speed-wise?
STM* is usually slower than IO/MVar. STM has to do the transactional record keeping and throws away work (i.e. CPU cycles and speed) when it aborts. The Chameneos benchmark has 4 writers working *very* quickly, so the contention is high. Taking the MVar acts like a mutex to serialize access without throwing away work. The [a] is a LIFO stack; pushing and popping the front element is fast. Also, I suspect the following may be true: If 4 threads block trying to take an MVar, and a 5th thread puts a value in the MVar, then *exactly one* of the 4 blocked threads is woken up and scheduled to run. If 4 threads retry while in STM (e.g. takeTMVar), and a 5th thread commits a change to that TMVar, then *all 4 threads* are woken up and rescheduled. This is what the Apache httpd server folks called the "thundering herd" problem when many processes are blocked waiting on socket 80. If 4000 threads were getting woken up when only 1 was needed, then performance would be poor. Certainly I found 4 writer thread and STM to be much slower for this shootout problem than the Einar's custom MVar channel. Could someone who knows the STM implementation comment on this?
This is the CVS code. newTChanIO is exported but undocumented in GHC 6.4.1. I'm not sure what purpose it serves.
I get tired of writing "do tv <- atomically $ newTVar foo" I bet this is just shorthand: "do tv <- newTVarIO foo" Same for newTChanIO. [ Of course, a type class could be used instead. But that seems tohave been judged overkill ]
-- | 'TChan' is an abstract type representing an unbounded FIFO channel. data TChan a = TChan (TVar (TVarList a)) (TVar (TVarList a))
type TVarList a = TVar (TList a) data TList a = TNil | TCons a (TVarList a)
newTChan :: STM (TChan a) newTChan = do hole <- newTVar TNil read <- newTVar hole write <- newTVar hole return (TChan read write)
newTChanIO :: IO (TChan a) newTChanIO = do hole <- newTVarIO TNil read <- newTVarIO hole write <- newTVarIO hole return (TChan read write)
writeTChan :: TChan a -> a -> STM () writeTChan (TChan _read write) a = do listend <- readTVar write -- listend == TVar pointing to TNil new_listend <- newTVar TNil writeTVar listend (TCons a new_listend) writeTVar write new_listend
readTChan :: TChan a -> STM a readTChan (TChan read _write) = do listhead <- readTVar read head <- readTVar listhead case head of TNil -> retry TCons a tail -> do writeTVar read tail return a
On Jan 3, 2006, at 11:25 AM, Chris Kuklewicz wrote:
The latest Ch code is very very short:
{- Ch : fast unordered channel implementation -} newtype Ch a = Ch (MVar [a], MVar a)
newCh = liftM2 (,) (newMVar []) newEmptyMVar >>= return.Ch
readCh (Ch (w,r)) = takeMVar w >>= \lst -> case lst of (x:xs) -> putMVar w xs >> return x [] -> putMVar w [] >> takeMVar r
writeCh (Ch (w,r)) x = do ok <- tryPutMVar r x -- opportunistic, helps for this problem unless ok $ takeMVar w >>= \lst -> do ok <- tryPutMVar r x -- safe inside take/put putMVar w $ if ok then lst else (x:lst)
It could be used in general purpose code, note the parametric type "a" in "Ch a". It makes absolutely no guarantees about the order of values. That means that the order they are written is unlikely to be the order in which they are read. Writes to the channel are non-blocking and the "MVar [a]" holds some items waiting to be read (in LIFO order).