[m-dev.] STM rewrite

[Peter Ross]

On Thu, Nov 10, 2011 at 2:26 PM, Chris King <colanderman at gmail.com> wrote:
> 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.)
>
I would suggest adding the above explanations to your stm code.

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------