[Haskell-cafe] Proof of a multi-threaded application

[Ryan Ingram]

If you have multiple agents interacting with some structure and you
want it to look like each of them is accessing it serialized, then STM
is exactly what you want.

The performance is always "in comparison to what"; you will likely get
worse performance than the "best possible" implementation of your
algorithm using locks, but that algorithm may be very difficult to
write.  My intuition is that if you spend put two programmers on a
task, one using STM and one using locks, that the STM solution will
perform better given the same amount of implementation time for any
non-trivial problem.

In addition, you can choose the level of "fine-grained-ness" in STM
just as you can with locks, by choosing what things to make into TVars
and what things to make pure.  For example, this structure:

> type STMMap a = TVar (Map k a)

will have much different performance than

> type STMMap k a = TVar (STMNode a)
> data STMNode a = Tip | Branch !k a (STMMap k a) (STMMap k a)

and either one could be better depending on what you are doing.  The
former is like a "global lock" on the map, whereas the latter is
analgous to "fine-grained" locks.  But writing an algorithm using the
"fine grained locks" version is a lot simpler to get right in STM than
doing so with locks directly.  In addition, STM's "optimistic
concurrency" gives you the equivalent of multiple-reader single-writer
locks for free; writing code with those directly is even more
difficult to get right!

  -- ryan

On Mon, Nov 17, 2008 at 10:35 PM, Ketil Malde <ketil at malde.org> wrote:
> "Tim Docker" <timd at macquarie.com.au> writes:
>
>>> My apologies for side-tracking, but does anybody have performance
>>> numbers for STM? I have an application waiting to be written using
>>> STM, boldly parallelizing where no man has parallelized before, but
>>> if it doesn't make it faster,
>
>> Faster than what?
>
> Faster than an equivalent non-concurrent program.  It'd also be nice
> if performance was comparable lock-based implementation.
>
>> Are you considering using STM just to make otherwise pure code run in
>> parallel on multiple cores?
>
> No, I have a complex structure that must be updated in non-predictable
> ways.  That's what STM is for, no?
>
> -k
> --
> If I haven't seen further, it is by standing in the footprints of giants
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>