[tlug] STM, the Silver Bullet, and the Foot

[Curt Sampson <cjs@example.com>]

On 2008-11-17 12:45 +0900 (Mon), Edward Middleton wrote:

> Stephen J. Turnbull wrote:
> > Seriously, after
> > the discussion with Curt re: STM in Haskell, I think this one could
> > happen soonish, and it seems like a solution is on the horizon.
> 
> I don't know,  It doesn't look like the silver bullet[1], and possible
> not very applicable to a kernel[2].   Though there is a Linux kernel
> supporting HTM[3].  Now all we need is hardware support ;)
> 
> 1. http://portal.acm.org/citation.cfm?doid2=1400214.1400228
> 2. http://blogs.sun.com/bmc/entry/concurrency_s_shysters

Actually, my paper copy of CACM arrived a couple of days ago, and just
yesterday evening (well, now a week ago, as this incomplete message
has been languishing) I picked it up, looked through the table of
contents, and got pretty excited by the article referenced above,
entitled "Software Transactional Memory: Why is it Only a Research Toy?"

(Incidently, unusually for papers appearing in ACM publications,
this appears available for free download, along with a related
ACM Queue article that appeared in a shortened version in
the same issue: <http://doi2.acm.org/1454456.1454462>. Also,
<http://x86vmm.blogspot.com/2008/11/cantrill-and-bonwick-get-all-concurrent.html>
is relevant.

(And while we're on the topic of being able to access
ACM articles, my membership doesn't let me get to
<http://portal.acm.org/citation.cfm?doid=1366230.1366241>, "The
limits of software transactional memory (STM): dissecting Haskell STM
applications on a many-core environment"; if anybody can get me a copy,
I'd be very appreciative.)

Anyway, back to the topic: I was excited because, after all, to whack
STM down in such a major way is, for me, an incredibly interesting
research result, even if it happens to destroy a little pet theory I
rather like.

Unfortunately, the article suffers from the some of the seemingly
typical CACM quality issues that I've seen since I started receiving
it in September. The illegible graphics done by their "award-winning"
graphics team I can excuse; perhaps the editors had just never read
Tuft. (The graphs in this article where zero threads get just slightly
less work done than one thread are a particularly charming example.)
But it beggars the imagination to know that the ACM appears to be an
organization intent on celebrating the anniversary of LISP by still
refusing to include in their undergraduate CS curriculum recommendations
a requirement for any experience at all in a functional programming
language.

But it may be that I've seen an unrepresentative sample. After all,
the ACM did originally publish the Harris, Simons (both of them),
et al. "Composable memory transactions" paper in the PPoPP 2005
proceedings. (This is the famous "Beautiful Concurrency" paper published
in O'Reilly's 2007 _Beautiful Code_.) While searching for it, I
discovered that they'd republished it in the August 2008 CACM, and from
a quick read of a few pages it appears that there's a fair amount of
other great stuff in that issue. (Alex E. Bell's comment that, "even
the most savvy must occasionally liken themselves to the infamous Neo
in the film The Matrix and gyrate wildly to avoid being stricken by the
many silver bullets whizzing by" was one of the many high points in a
particularly enjoyable opinion piece.)

So, much as it pains me (not to mention making this off-topic for a
list of this sort), let's set ranting aside for a few moments, and look
at the substance of the provocatively titled article referenced as [1]
above, and how it relates to the previous Haskell STM discussion.

The first point that struck me, and probably the most important one for
the purposes of this discussion, is that this article is really all
about STM in C and similar languages.

As it turns out, neither transactional memory (the paper mentions
hardware TM and hardware-assisted TM, though it's not the focus) nor
software transactional memory is a new thing. The paper references
articles on this particular topic dating as early as 1993, and a search
of the ACM on-line publication archives for "software transactional
memory" brings up 275 results dating back to 1994. Adding "Haskell"
to the search reduces the result count to 51 dating back to the 2005
"Composable Memory Transactions" paper; clearly this is not some new
Haskell thing.

And the problems with STM that they bring up appear to be very good
ones--or, rather, very bad ones, if you're an STM fan. I won't get
into the details, since you can get them all from the paper, but
having written a reasonable amount of multi-threaded lock-using code
myself, and looking at the issues they describe, STM seems to me
to be far from a silver bullet. The arguments that STM's semantics
are muddled by interaction with non-transactional code and data
accessed within transactions, that programmers annotating what data
are transactional and not is difficult and error-prone, that without
significant annotations one introduces large access overheads for memory
accesses that need not be transactional, all of this rings very true to
me.

And, while I'm not going to buy the idea that Bryan Cantrill
("Concurrency's Shysters", [2] above), though a very, very smart guy*
is all-so-prescient--it appears to me to be a classic case of 20/20
hindsight when he implies that he guessed that SMP kernels would scale
well beyond 8 CPUs--I'll admit I learned a lot from that ACM Queue
article, despite some of my reservations with the general thrust of it.
(I recommend everybody read the second half of it, just in case you
happen to become a programmer one day.)

    * His response to David Miller notwithstanding:
    <http://cryptnet.net/mirrors/texts/kissedagirl.html>. And by the
    way, I should get extra credit, as a NetBSD Sparc guy (at the time),
    for bringing up David Miller at all, much less on a Linux list. :-)

So, given all this, why is this Curt guy still raving about STM?

Well, the truth is, I'm not.

I'd understood this up to now more clearly in other areas relating to
Haskell and parallelism, but the same thing applies here. STM works in
Haskell in a way it doesn't work in other languages not because it's
STM, but because it's done in Haskell.

The key point here, and I don't know if I can explain it adequately
in a (relatively) short message in this environment, is that Haskell
is pure by default. This means that, for any particular function, it
doesn't matter when you call it (before or after another function) or
how many times you call it (never--if you don't happen to use the result
for something else, or a hundred times), the side effects are the same:
none.

To put it in more concrete terms, if I say in Haskell 'foo x y', which
is the same as 'foo(x(),y())' or '(foo (x) (y))' in your C-ish or
LISP-ish language of choice, the functions x() and y() may never be
called, or may be called multiple times (though they won't be with a
good compiler such as ghc), and it makes no difference. This is just
the standard thing Haskell, or any other pure language.

This differs significantly from modern LISP-like languages where when
you say '(foo (a) (b))', and 'foo' happens to be 'and', it's specified
that '(a)' must be evaluated before '(b)', and '(b)' must not evaluated
if '(a)' evaluates to false. (Is 'foo' a macro with special evaluation
order, as above? Or just a regular function where both '(a)' and '(b)'
will be evaluated first. You'll have to remind me.)

Of course, we do need to do I/O, and other things that have side
effects in some sort of world (even it be the limited world of, say, a
transactional model), and these things need to have their sequence of
execution specified. That, among many other things, is for what we use
monads. As it turns out, the exact same mechanism that lets us separate
impure code doing IO from side-effect-free pure code and order the IO
actions appropriately is exactly suited for the parallel case of STM.

So what do we get from this? Well, we know that programmer annotations
of what's transactional and what's not are difficult and unreliable.
That's where Haskell's type system comes in: just as with the IO
monad, it enforces the separation of these things and type-checks the
"annotations." We also know that it's dangerous and error-prone to mix
abortable transactions and things with side-effects; again, the type
system deals with this, forcing you to declare what's STM, what has
side effects, and deal with mixing the two. And of course the "pure by
default" model of Haskell leads you to generally not mixing them.

In the end, a lot of the problems with STM described in the article seem
to me entirely parallel to the problems with lock-based systems, and
from that point of view, it really doesn't seem to offer much advantage
over locking. The problems are easy to fix only by throwing away
performance (declaring all variables to be STM variables is tantmount
to using one big lock for all program data). The big difference here is
that safe STM is expressable, in a way that locks aren't, in Haskell's
type system, and as with many other things where we use type systems,
and this eliminates many categories of programmer errors, increases
runtime efficiency, and allows easy composition of separately developed
bits of code.

The advantage lies in Haskell, not in STM.

On 2008-11-17 11:01 +0900 (Mon), Stephen J. Turnbull wrote:

> The fact that even so nobody but SPJ really understands that stuff....

Actually, I'd proffer the opinion that SPJ is far from a guru when it
comes to STM, it's just that he's a master at finding abstractions that
work in sufficiently powerful languages. 

On 2008-11-17 13:32 +0900 (Mon), Stephen J. Turnbull wrote:

> My point is simply that STM is an examples that suggests that people
> are starting to get a handle on "what really is going on here", and my
> bet is that within a couple of years that will result in a solution
> that deserves to go into kernels, even if its not universally
> applicable.

Well, to summarize, my thought on the matter is that when it comes to
kernels, at least those not written in Haskell or something similar,
locking is likely to reign for quite some time simply because it's
better understood. So I guess, in a way, I agree with the original paper
after all.

Thoughts welcome, of course.

cjs
-- 
Curt Sampson       <cjs@example.com>        +81 90 7737 2974   
Mobile sites and software consulting: http://www.starling-software.com