[Haskell-cafe] Re: Benchmarking and Garbage Collection

[Simon Marlow]

On 05/03/2010 13:45, Neil Brown wrote:
> Simon Marlow wrote:
>>> import Control.Concurrent
>>> import Control.Concurrent.CML
>>> import Control.Monad
>>>
>>> main :: IO ()
>>> main = do let numChoices = 2
>>> cs <- replicateM numChoices channel
>>> mapM_ forkIO [replicateM_ (100000 `div` numChoices) $ sync $ transmit
>>> c () | c <- cs]
>>> replicateM_ 100000 $ sync $ choose [receive c (const True) | c <- cs]
>>
>> Good grief. Can I get a copy of this program? It might be something
>> simple that we can fix. Just having lots of threads shouldn't be a
>> performance problem per se, we have benchmarks that create millions of
>> threads without any problems.
> That's all the code you need, along with the cml package from Hackage.
> Put the above few lines into GoodGrief.hs (the reply has munged the
> indentation slightly), and do:
>
> cabal install cml
> ghc --make -threaded GoodGrief.hs
> ./GoodGrief +RTS -s
>
> That got me the listed results on GHC 6.12.1 (I did use -threaded but
> not -N as I was on a single-core machine; I believe the same problem
> occurs without -threaded). The problem is in the CML library that the
> above code uses.

Yes, I see what the problem is.  Removing a thread from the queue 
attached to an MVar is a O(n) operation, and in this case you have 
thousands of threads attached to MVars and the system wants to clean 
them all up before exiting, hence things go O(n^2).  Threads only need 
to be removed from the queue when

  - they are the target of throwTo from another thread

  - the system is shutting down, and deleting threads

  - the thread is unreachable and needs to be woken up to be sent
    the BlockedIndefinitelyOnMVar exception (this is probably why
    you sometimes get the 60s GC just after your benchmark has
    finished, but before shutdown).

So as it happens Simon PJ and I were discussing some changes yesterday 
that will eventually make removing a thread from a queue an O(1) 
operation.  Hopefully 6.14.1 will be better in this regard.

Cheers,
	Simon