What is the mutator?

Jost Berthold berthold at Mathematik.Uni-Marburg.de
Thu Aug 6 13:37:51 EDT 2009

> Message: 1
> Date: Thu, 6 Aug 2009 00:38:08 -0700
> From: Jason Dusek <jason.dusek at gmail.com>
> Subject: What is the mutator?
> To: glasgow-haskell-users at haskell.org
> Message-ID:
> 	<42784f260908060038h53d7cc0dy9f80e43f269a2faf at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>   I've been reading a little about GC latency and have run
>   across statements like this:
>     One solution to the GC synchronisation problem would be to
>     implement a concurrent garbage collector. Typically,
>     however, concurrent GC adds some overhead to the mutator,
>     since it must synchronise with the collector.some thunks are
>     never “black-holed”, so giving a potential performance win.
>     Unfortunately, in the parallel setting, it substantially
>     enlarges the time window in which two or more duplicate
>     threads might evaluate the same think, and thus
>      -- Comparing and Optimising Parallel Haskell Implementations
>         for Multicore Machines
>   What is the mutator?

Hi Jason,

as Malcolm already said, the "mutator" in this text is the/a  thread
evaluating some Haskell expression. Just to add some more details to the 

In general, a Haskell expression is a computation represented as a graph 
in the heap. Haskell evaluates lazily and does not have to fully 
evaluate every part of it for the program to finish. Unevaluated parts 
are "thunks". As soon as one of potentially several concurrent (mutator) 
threads starts to evaluate a thunk, it is replaced by a blackhole, which 
keeps other threads out of it until the node in the graph is evaluated 
(say, to a list cons (:), with probably unevaluated head and tail). Then 
the blackhole is updated with the new value. Other threads block on the 
blackhole in the meantime (so not necessarily an exception in the case 
of concurrent mutator threads) and are woken up by the update.

The passage you quote above is about two separate aspects:

1. Garbage collection and mutator running concurrently: while they 
usually do, they do not _have_ to exclude each other, but not doing so 
means that the objects they are treating have to be locked.

2. About "Blackholing": in the sequential evaluation (where hitting a 
blackhole indeed means to have a loop), some better performance can be 
gained by not blackholing a thunk immediately, so this was done in GHC 
earlier. However, it increases the chance for 2 mutator threads to 
evaluate the same thunk (double work), and we got better performance by 
blackholing immediately.


More information about the Glasgow-haskell-users mailing list