Re: [Algorithms] Complexity of new hardware

[Sebastian S. <seb...@gm...>]

On Sun, Apr 26, 2009 at 12:50 PM, <ne...@tw...> wrote:

>
> I would like to sound a note of caution on STM. It's quite nice to
> program with -- think of it as threads-and-locks, made good. But I've
> been to many presentations on STM, from prominent researchers in the
> field, and the performance figures have always indicated that it doesn't
> scale. Past about two-four threads contending on a piece of
> transactional memory, the performance usually ends up worse than one
> thread, which is hardly what you want from parallel programming.
>

Well that's kind of unavoidable though. If there is true contention on a
piece of shared data, then no amount of software solutions will help you. So
the name of the game is to reduce unnecessary contention (e.g.
pessimistically excluding something from accessing data). For that reason
avoiding shared data as much as possible is clearly a good idea - but once
you're in the situation that you really do need it, what do you do?

STM competes with locks and condition variables, not threads and messages.
E.g. if you have a game world with 10K objects in it, and each object
touches 5 other objects on average, when it's updated, then *actual*
contention will probably be low, whereas *potential* contention is high, and
that's where STM shines since it enables optimistic concurrency. I.e. the
common case of no actual contention runs quickly, at the cost of some
overhead when you're unlucky and two objects touch the same data. Whereas
with locks you have to lock everything every single time even though it's
unlikely that anything else is using it. For these cases STM does scale well
beyond locks.

I
> think a message-passing model is more promising, and is equally valid in
> Haskell or in C++ (disclaimer: I spend my days doing research into
> message-passing concurrency :-), whereas STM in C++ is not as
> easy and simple as the Haskell version.
>

Sure, message passing is another strategy, but I don't think they're in
competition. STM is for shared state concurrency, which is to be avoided,
but sometimes can't be, message passing offers very little benefit w.r.t.
scalability over locks and condition variables when it comes to truly shared
state (you pretty much end up simulating locks with them, by having some
"server thread" manage access to data, and for transactions you need to
gather up exclusive access somehow, which is essentially the same as "taking
a lock").

Message passing can be very nice for some things, but I think there are
plenty of cases where it doesn't work very well (e.g. the example mentioned
earlier).
Also, I find message passing can get very complicated in some instances, as
it feels a bit like "goto programming", where you have to try to reason
about how these messages flow through several threads - it can get hairy and
"spaghetti-like" where the logic of the program is obscured by the details
of coordination. So while there are problems where multiple sequential
processes communicating through messages fit very nicely, I'd be very
careful about considering them to be the *only* paradigm - we need to be
able to support all the other problems too.



-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862