Is this a bug in multithreading code?

[Alastair Reid]

> Hi all, does someone know why this program works
> 
> ------------------------
> import Concurrent
> 
> loopM = sequence_ . repeat
> 
> main = do
>        v <- newMVar 0
>        forkIO (loopM (modifyMVar_ v (return . (1+))))
> --       forkIO (loopM (modifyMVar_ v (return . (1+))))
>        loopM (readMVar v >>= print)
> -------------------------
> 
> but uncommenting the commented line makes the program fail with "stack 
> overflow" ?

There's four interesting pieces of code here:

  M1 = the code in main before the forks
  M2 = the body of the loop at the end of main
  A  = the body of the loop in the first forked thread
  B  = the body of the loop in the second forked thread

One possible execution sequence is:

  M1 A B A B A B A B A B M2 ...

With this, the code in A and B will build a bigger and bigger
suspended computation of the form

  1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 0

and then when M2 runs it will evaluate this computation and update it.
This evaluation requires stack space proportional to the number of As
and Bs.

A more likely execution sequence would have each thread run for a
significant timeslice so you'd see perhaps 10000 A's then 10000 B's
then 10000 M2s.  

  M1 A A A A A A A A A ... A A A A A A B B B B B B B B B B B 
    B B B B B B B ... B B B B B B B B M2 M2 M2 M2 M2 M2 M2 M2 M2 M2 

That first M2 will perform the same evaluation as before (i.e., adding
all those ones together) but, in this more likely scenario, will
require a very, very large stack.


I conjecture that the problem would go away if you added appropriate
uses of seq or $! to your program so that the value stored in the MVar
was always fully evaluated.  I leave writing a function which does
this as an exercise - though not a completely trivial one since both
monads and higher order functions make blindly adding $! everywhere
ineffective.

--
Alastair Reid                 alastair@reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/