Is this a bug in multithreading code?
Wed, 23 Apr 2003 21:54:56 +0100
> 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
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
Alastair Reid firstname.lastname@example.org
Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/