README
¶
stm
Package stm provides Software Transactional Memory operations for Go. This is
an alternative to the standard way of writing concurrent code (channels and
mutexes). STM makes it easy to perform arbitrarily complex operations in an
atomic fashion. One of its primary advantages over traditional locking is that
STM transactions are composable, whereas locking functions are not -- the
composition will either deadlock or release the lock between functions (making
it non-atomic).
The stm API tries to mimic that of Haskell's Control.Concurrent.STM, but
this is not entirely possible due to Go's type system; we are forced to use
interface{} and type assertions. Furthermore, Haskell can enforce at compile
time that STM variables are not modified outside the STM monad. This is not
possible in Go, so be especially careful when using pointers in your STM code.
Another significant departure is that stm.Atomically does not return a value.
This shortens transaction code a bit, but I'm not 100% it's the right decision.
(The alternative would be for every transaction function to return an interface{}.)
Unlike Haskell, data in Go is not immutable by default, which means you have to be careful when using STM to manage pointers. If two goroutines have access to the same pointer, it doesn't matter whether they retrieved the pointer atomically; modifying the pointer can still cause a data race. To resolve this, either use immutable data structures, or replace pointers with STM variables. A more concrete example is given below.
It remains to be seen whether this style of concurrency has practical applications in Go. If you find this package useful, please tell me about it!
Examples
Here's some example code that demonstrates how to perform common operations:
// create a shared variable
n := stm.NewVar(3)
// read a variable
var v int
stm.Atomically(func(tx *stm.Tx) {
v = tx.Get(n).(int)
})
// or:
v = stm.AtomicGet(n).(int)
// write to a variable
stm.Atomically(func(tx *stm.Tx) {
tx.Set(n, 12)
})
// or:
stm.AtomicSet(n, 12)
// update a variable
stm.Atomically(func(tx *stm.Tx) {
cur := tx.Get(n).(int)
tx.Set(n, cur-1)
})
// block until a condition is met
stm.Atomically(func(tx *stm.Tx) {
cur := tx.Get(n).(int)
if cur != 0 {
tx.Retry()
}
tx.Set(n, 10)
})
// or:
stm.Atomically(func(tx *stm.Tx) {
cur := tx.Get(n).(int)
tx.Assert(cur == 0)
tx.Set(n, 10)
})
// select among multiple (potentially blocking) transactions
stm.Atomically(stm.Select(
// this function blocks forever, so it will be skipped
func(tx *stm.Tx) { tx.Retry() },
// this function will always succeed without blocking
func(tx *stm.Tx) { tx.Set(n, 10) },
// this function will never run, because the previous
// function succeeded
func(tx *stm.Tx) { tx.Set(n, 11) },
))
// since Select is a normal transaction, if the entire select retries
// (blocks), it will be retried as a whole:
x := 0
stm.Atomically(stm.Select(
// this function will run twice, and succeed the second time
func(tx *stm.Tx) { tx.Assert(x == 1) },
// this function will run once
func(tx *stm.Tx) {
x = 1
tx.Retry()
},
))
// But wait! Transactions are only retried when one of the Vars they read is
// updated. Since x isn't a stm Var, this code will actually block forever --
// but you get the idea.
See example_santa_test.go for a more complex example.
Pointers
Be very careful when managing pointers inside transactions! (This includes slices, maps, channels, and captured variables.) Here's why:
p := stm.NewVar([]byte{1,2,3})
stm.Atomically(func(tx *stm.Tx) {
b := tx.Get(p).([]byte)
b[0] = 7
tx.Set(p, b)
})
This transaction looks innocent enough, but it has a hidden side effect: the modification of b is visible outside the transaction. Instead of modifying pointers directly, prefer to operate on immutable values as much as possible. Following this advice, we can rewrite the transaction to perform a copy:
stm.Atomically(func(tx *stm.Tx) {
b := tx.Get(p).([]byte)
c := make([]byte, len(b))
copy(c, b)
c[0] = 7
tx.Set(p, c)
})
This is less efficient, but it preserves atomicity.
In the same vein, it would be a mistake to do this:
type foo struct {
i int
}
p := stm.NewVar(&foo{i: 2})
stm.Atomically(func(tx *stm.Tx) {
f := tx.Get(p).(*foo)
f.i = 7
tx.Set(p, f)
})
...because setting f.i is a side-effect that escapes the transaction. Here,
the correct approach is to move the Var inside the struct:
type foo struct {
i *stm.Var
}
f := foo{i: stm.NewVar(2)}
stm.Atomically(func(tx *stm.Tx) {
i := tx.Get(f.i).(int)
i = 7
tx.Set(f.i, i)
})
Benchmarks
In synthetic benchmarks, STM seems to have a 1-5x performance penalty compared
to traditional mutex- or channel-based concurrency. However, note that these
benchmarks exhibit a lot of data contention, which is where STM is weakest.
For example, in BenchmarkIncrementSTM, each increment transaction retries an
average of 2.5 times. Less contentious benchmarks are forthcoming.
BenchmarkAtomicGet-4 50000000 26.7 ns/op
BenchmarkAtomicSet-4 20000000 65.7 ns/op
BenchmarkIncrementSTM-4 500 2852492 ns/op
BenchmarkIncrementMutex-4 2000 645122 ns/op
BenchmarkIncrementChannel-4 2000 986317 ns/op
BenchmarkReadVarSTM-4 5000 268726 ns/op
BenchmarkReadVarMutex-4 10000 248479 ns/op
BenchmarkReadVarChannel-4 10000 240086 ns/op
Credits
Package stm was originally created by lukechampine.
Documentation
¶
Overview ¶
Package stm provides Software Transactional Memory operations for Go. This is an alternative to the standard way of writing concurrent code (channels and mutexes). STM makes it easy to perform arbitrarily complex operations in an atomic fashion. One of its primary advantages over traditional locking is that STM transactions are composable, whereas locking functions are not -- the composition will either deadlock or release the lock between functions (making it non-atomic).
To begin, create an STM object that wraps the data you want to access concurrently.
x := stm.NewVar(3)
You can then use the Atomically method to atomically read and/or write the the data. This code atomically decrements x:
stm.Atomically(func(tx *stm.Tx) {
cur := tx.Get(x).(int)
tx.Set(x, cur-1)
})
An important part of STM transactions is retrying. At any point during the transaction, you can call tx.Retry(), which will abort the transaction, but not cancel it entirely. The call to Atomically will block until another call to Atomically finishes, at which point the transaction will be rerun. Specifically, one of the values read by the transaction (via tx.Get) must be updated before the transaction will be rerun. As an example, this code will try to decrement x, but will block as long as x is zero:
stm.Atomically(func(tx *stm.Tx) {
cur := tx.Get(x).(int)
if cur == 0 {
tx.Retry()
}
tx.Set(x, cur-1)
})
Internally, tx.Retry simply calls panic(stm.Retry). Panicking with any other value will cancel the transaction; no values will be changed. However, it is the responsibility of the caller to catch such panics.
Multiple transactions can be composed using Select. If the first transaction calls Retry, the next transaction will be run, and so on. If all of the transactions call Retry, the call will block and the entire selection will be retried. For example, this code implements the "decrement-if-nonzero" transaction above, but for two values. It will first try to decrement x, then y, and block if both values are zero.
func dec(v *stm.Var) {
return func(tx *stm.Tx) {
cur := tx.Get(v).(int)
if cur == 0 {
tx.Retry()
}
tx.Set(v, cur-1)
}
}
// Note that Select does not perform any work itself, but merely
// returns a transaction function.
stm.Atomically(stm.Select(dec(x), dec(y)))
An important caveat: transactions must be idempotent (they should have the same effect every time they are invoked). This is because a transaction may be retried several times before successfully completing, meaning its side effects may execute more than once. This will almost certainly cause incorrect behavior. One common way to get around this is to build up a list of impure operations inside the transaction, and then perform them after the transaction completes.
The stm API tries to mimic that of Haskell's Control.Concurrent.STM, but this is not entirely possible due to Go's type system; we are forced to use interface{} and type assertions. Furthermore, Haskell can enforce at compile time that STM variables are not modified outside the STM monad. This is not possible in Go, so be especially careful when using pointers in your STM code. Remember: modifying a pointer is a side effect!
Index ¶
Constants ¶
const Retry = "retry"
Retry is a sentinel value. When thrown via panic, it indicates that a transaction should be retried.
Variables ¶
This section is empty.
Functions ¶
func AtomicGet ¶
func AtomicGet(v *Var) interface{}
AtomicGet is a helper function that atomically reads a value.
func AtomicSet ¶
func AtomicSet(v *Var, val interface{})
AtomicSet is a helper function that atomically writes a value.
func Atomically ¶
func Atomically(op Operation) interface{}
Atomically executes the atomic function fn.
func WouldBlock ¶ added in v0.2.0
Types ¶
type Operation ¶ added in v0.2.0
type Operation func(*Tx) interface{}
func Compose ¶
Compose is a helper function that composes multiple transactions into a single transaction.
func Select ¶
Select runs the supplied functions in order. Execution stops when a function succeeds without calling Retry. If no functions succeed, the entire selection will be retried.
func VoidOperation ¶ added in v0.2.0
type Tx ¶
type Tx struct {
// contains filtered or unexported fields
}
A Tx represents an atomic transaction.
func (*Tx) Assert ¶
Assert is a helper function that retries a transaction if the condition is not satisfied.
func (*Tx) Retry ¶
func (tx *Tx) Retry()
Retry aborts the transaction and retries it when a Var changes.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
cmd
|
|
|
santa-example
An implementation of the "Santa Claus problem" as defined in 'Beautiful concurrency', found here: http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/beautiful.pdf The problem is given as: Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves.
|
An implementation of the "Santa Claus problem" as defined in 'Beautiful concurrency', found here: http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/beautiful.pdf The problem is given as: Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. |