[Haskell-cafe] Help with "shootout"

[Chris Kuklewicz]

Bulat Ziganshin wrote:
> Hello Chris,
> 
> Tuesday, January 03, 2006, 12:20:26 AM, you wrote:
> 
> CK>   Einar Kartunen sped up the code using a custom channel implementation.
> CK>    This increased speed by a factor of over 2.  The wiki at
> CK> http://haskell.org/hawiki/ChameneosEntry has the latest version.
> 
> can these channels be used in general-purpose code?

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).  The
"MVar a" allows a reader to block and wait for an empty channel to get
an item.  A small amount of extra speed comes from the writer's
"opportunistic" attempt to not take the w MVar unless it needs to.  But
note that readCh always takes the w MVar, and can ignore the r MVar.
This choice was determined by benchmarking.

Alternative, but slower for this case, functions for readCh and writeCh are

> readCh' (Ch (w,r)) = do
>   mx <- tryTakeMVar r
>   case mx of
>     Just x -> return x
>     Nothing -> takeMVar w >>= \lst -> case lst of (x:xs) -> putMVar w xs >> return x
>                                                   []     -> putMVar w [] >> takeMVar r
> 
> writeCh' (Ch (w,r)) x = takeMVar w >>= \lst -> do 
>     ok <- tryPutMVar r x  -- safe inside take/put
>     putMVar w $ if ok then lst else (x:lst)
> 

But in this instance, using either of these would be slower.  The
balance between readers (one here) and writers (four here) and their
average speed is what determines the optimum readCh/writeCh code.
Different usage would benefit from different choices.

> 
> CK>   This makes me ponder one of the things that Joel was trying to do:
> CK> efficiently pass data to a logging thread.  It may be that a custom
> CK> channel would be helpful for that as well.
> 
> last variant of his code used just MVar-protected direct hPutStr
> operations

My point was more that Haskell allows you to make your own channels and
that it is possible to do better than the provided ones.