New subject: What is the mutator?

6 Aug 2009

      ...
Message: 1
Date: Thu, 6 Aug 2009 00:38:08 -0700
From: Jason Dusek 
Subject: What is the mutator?
To: glasgow-haskell-users@haskell.org
Message-ID:
  <42784f260908060038h53d7cc0dy9f80e43f269a2faf@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 
picture...

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.

Cheers,
Jost

Re: What is the mutator?

Jost Berthold

Jason Dusek

Malcolm Wallace

Jason Dusek

Simon Marlow

tags

participants (4)