Software Transactional Memory in GO.

[Tomer]

Hi,

I've been checking on GO today This "toy" language sounds interesting.
Does anyone know if there is a STM implementation in GO?

If not, do you think it's a good idea to try and write one in GO? (As
it might replace locks in the future).
I might consider giving it a try.

Are there atomic operations like Compare and Swap in GO? (Using locks
to implement a STM is a bad idea).

Thanks,

Tomer.

[Pete Wilson]

It's an interesting idea, but I *think* that current STM architectures
(even HTM and hybrid) are limited to doing away with the need to
acquire locks by replacing lock-protected code sections with
transactions which either complete or rollback invisibly. And locks,
of course, protect shared entities.

A key tenet of go is that you seek to avoid 'shared but locked'
entities. Preferably, you give a (collection of) entities to a
'goroutine' ("thread") or a collection of such and send it (them)
messages asking it(them) to do stuff on your behalf. It can indeed
give you permission to play with the entity, but preferably your
design is more 'object oriented' in that the goodies are played with
by an owner. (Apologies for gross oversimplifications)

Thus, I'd avoid thinking of STM, *except* if you can come up with a
nice model for doing 'transactional messaging'; this would be very
nice, as it could en principe extend to I/O (which suggests it's umm,
hard).

A sorta version of this *has* been done (in a discrete event
simulation universe, "Time machine", I think, from many years ago).
Send messages speculatively; every message is timestamped; you've
broken speculation if you receive a message from your past; unroll
through antimessages.

-- Pete

[Rowan Davies]

There's no STM implementation for Go, as far as I know. STM doesn't
fit so well with message passing channels, which Go adopts as another
quite good alternative to locks. When used well they can avoid the
compositionality issues with locks, and have less of a performance
cost compared to STM - but STM arguably scales better to complicated
situations in terms of the ease of avoiding deadlocks and the like.

To implement STM for Go, you'd have to choose whether transactions
would include all non-IO effects - including updating ordinary Go
variables and messaging - or whether you'd limit the transactional
effects to just a special new mutable reference datatype/class. The
first would require significant support from the compiler, like
Intel's STM for C++. The latter could be easy to implement in a
library, but I think it'd be very hard to use effectively with things
like message passing and the Go memory model without compiler support.

Transactional messaging does sound interesting - and I could imagine
you could implement such a thing by implementing something like the Go
runtime via an STM compiler like Intel's. But, it wouldn't really be
Go anymore - you'd have to modify the memory model significantly to be
transactional.

Still, interesting to consider.

- Rowan

[roger peppe]

2010/1/4 Rowan Davies <rd1...@gmail.com>:

> There's no STM implementation for Go, as far as I know.  STM doesn't
> fit so well with message passing channels, which Go adopts as another
> quite good alternative to locks.  When used well they can avoid the
> compositionality issues with locks, and have less of a performance
> cost compared to STM - but STM arguably scales better to complicated
> situations in terms of the ease of avoiding deadlocks and the like.

i started writing a reply to this, but it became a little long,
so i made a blog post of it:

http://rogpeppe.wordpress.com/2010/01/04/select-functions-for-go/

[Tomer]

Thanks everyone for the replies.

I guess Google Go developers decided to use message passing instead of
STM.
I wonder what were their reasons.

Perhaps I'll give it a try and do a toy STM library for Go on my spare
time.
Who knows it might convice Google Go developers to add STM support.

Tomer.

[Johann Höchtl]

> I guess Google Go developers decided to use message passing instead of
> STM.
> I wonder what were their reasons.
>

I can of course not speak for the golang core developers, but I quite
some distinctions on the applicability of STM and message passing.

With message passing you can easily create massively distributed
server systems on completely heterogenous hardware, typically seen on
hosting farms AKA clouds. Thus it is a very good mechanism for
distributed computing and with an optimised GC (per hardware-thread GC
that keeps data local to the thread) can reasonably perform on SMP
machines to speed up parallel tasks.

STM on the other hand buys little on heterogenous systems, where
comunicating servers are opaque distributed, possibly over
continents ;=) NUMA architecture helps, but adds complexity. OTOH STM
is much faster to coordinate tight parallel tasks on SMP.

That's my understanding from the Haskell world at last ...

Johann

[Pete Wilson]

Tomer

I'm surprised that you should ask why the Go developers chose message
passing than STM.

I can think of several important reasons.

The first is that message-passing scales. You can build big systems
with message-passing.

The second is that message-passing gives you some control over how
your system works - STM does all kinds of things behind your back
involving unknown runtime costs.

The third is STM (in practise) generally implies cache-coherent shared
memory. This is not a robust MP solution (one cache coherency error
and who knows how many processors suddenly have corrupt caches?), and
doesn't scale (implicit communication traffic on the interconnect will
in general be much more than the data exchanged in message-passing.

The fourth is that if resources are not infinite, it's a Good Idea to
be able to control what's eating your system resources. See the
'second' point above.

The fifth is that while transactions are a Good Idea in principle, to
use transactions as a basis for one's system architecture, you have to
do *everything* as a transaction. I/O, network traffic,.... People
just don't do that, so you end up with a horrid clash of models.

Make any sense?

STM's fascinating, and is (was?) fashionable. But I dunno whether it
makes any more sense than programming everything in Prolog (why
Prolog? you *do* remember when the Japanese Fifth-Generation computing
systems were going to wipe out the West's computer/software/IT
businesses and replace them with something entirely new, don't you?
Fads are so... repetitive)

Have fun! Transactional emssages really *would* be a neat thing,
incidentally...

-- Pete

[Anupam Kapoor]

Pete Wilson <pete@kivadesigngroupe> wrote:
,----

| > I'm surprised that you should ask why the Go developers chose message
| > passing than STM.
| >
| > I can think of several important reasons.

`----
some more fodder (if you have not read this before) :
http://queue.acm.org/detail.cfm?id=1454466

fundamentally communicating (to paraphrase pete), by sharing state does
not scale, as compared to communicating by sending messages...

kind regards
anupam

[R D]

Definitely some interesting ideas.  (Although I'm not sure I agree that STM isn't as expressive as channels - emulating channels with STM is much easier than the reverse.)

I guess in Go the intention is that any time you want to do a select, you should make a channel that you can select on - using channels in interfaces rather than methods seems to be emphasized, and broadly I like this.  To allow a select in a situation like the one you gave, the obvious thing to try is an extra channel to receive the sequence of values, with a new go routine that loops, reading from r.C and sending on this channel.  But, as you pointed out this buffers one element.

Maybe one solution is to consider how to avoid this buffering.  I think in Go such buffering will generally be awkward whenever trying to compose programs from pieces that communicate using synchronous channels, so maybe there's a broader issue here.  One standard solution is to use a second channel for the sender to wait on after each send, but it's not so nice to require a separate read throughout the senders code, and I can't see a way to encapsulate this back into a single synchronous channel for the sender to use.  It'd be nice if this could be done.

- Rowan