[m-dev.] STM rewrite

[Chris King]

On Wed, Nov 9, 2011 at 9:54 PM, Peter Ross <pro at missioncriticalit.com> wrote:
> I'm curious that you have low level C code as well as a mercury
> implementation, does this mean that STM performance is much better
> under the C grades?

Yes, by an order of magnitude.  The primary bottleneck in commit-time
STM is the global lock which is held during transaction validation and
commit.  Mercury's concurrency primitives are simply much too slow --
the fastest is thread.semaphore, which uses a mutex and a condition
variable or context switch, when merely a spinlock suffices.

I based the C portions of my module on the existing runtime
implementation (most notably the blocking mechanism for the low-level
C grades).

> I much prefer retry_on_fail that peter wang suggested, may_block has
> me thinking about blocking I/O so I really couldn't work out what it
> was doing.

Makes sense.

> Also as a complete newbie to STM code it would be helpful to expand
> the explanation of the following points, as they are not so clear to
> me.
>
> * retry() is not needed; Mercury already has a failure mechanism

In STM as popularized by Haskell, retry() aborts the currently
executing transaction, causing it to block until one of the variables
read in the transaction is updated by another thread, at which point
the transaction is rescheduled.  It's a very clever means of adding
blocking to STM which reuses much of the underlying machinery.

While playing around with STM in Mercury, I discovered that most of my
retry() calls were in response to some predicate failing (e.g.
checking if a queue is empty).  Since failure is otherwise meaningless
in an STM block (due to the use of the IO state), it makes sense to
usurp failure as the means of signaling a retry.

> * nested logs are not needed; Mercury already has backtrackable unique
> modes (mostly_unique)

Nested logs are used to implement or_else (see below), which requires
that transactions be partially (but not fully) aborted in the event of
a retry.  This is exactly the behavior exhibited by mostly_unique
values in the event of failure in Mercury.  In fact the STM log is a
perfect example of a mostly_unique value since it's backtrackable IO.

> * or_else is not needed; Mercury already has if/then/else

Haskell also introduced the or_else construct, which atomically tries
a "backup" transaction if a given transaction would retry.  This is
exactly what if/else does if the condition of the if fails.

> * use of builtin failure allows determinism analysis to double as
> wait-freedom check

STM transactions only block (and thus potentially deadlock) if they
call retry().  If we use failure-as-retry, then we can guarantee that
a set of transactions don't deadlock (i.e. they are wait-free) if none
of them can fail, which Mercury can detect.

(Note there is of course always the potential for livelock in the
event of scheduler strangeness.)

> Great job.

Thank you!

- Chris
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------