Papers and presentations about transactional memory in Haskell
Simon Peyton Jones. This is a chapter for the book
"Beautiful code", edited by Greg Wilson, O'Reilly 2007.
The free lunch is over. We have grown used to the idea that our
programs will go faster when we buy a next-generation processor, but
that time has passed. While that next-generation chip will have more
CPUs, each individual CPU will be no faster than the previous year's
model. If we want our program to run faster, we must learn to write
Parallel programs execute in a non-deterministic way, so they are hard
to test, and bugs can be almost impossible to reproduce. If we want
to write parallel programs that work reliably, we must pay particular
attention to beauty. Sadly, parallel program are often less
beautiful than their sequential cousins; in particular they are, as
we shall see, less modular.
In this chapter I describe Software Transactional Memory
(STM), a promising new approach to programming shared-memory parallel
processors. Although still in its infancy, STM seems to support
modular programs in a way that current technology does not. By the
time we are done, I hope you will be as enthusiastic as I am about
STM. It is not a solution to every problem, but it is a beautiful and
inspiring attack on the daunting ramparts of concurrency.
Composable memory transactions
Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy.
ACM Conference on Principles and Practice of Parallel Programming 2005 (PPoPP'05).
Writing concurrent programs is notoriously difficult, and is of
increasing practical importance. A particular source of concern
is that even correctly-implemented concurrency abstractions cannot
be composed together to form larger abstractions. In this paper
we present a new concurrency model, based on transactional memory,
that offers far richer composition. All the usual benefits of transactional memory
are present (e.g. freedom from deadlock), but in addition we describe
new modular forms of blocking and choice that
have been inaccessible in earlier work.
We've updated the original "Composable memory transactions" paper by
fixing a couple of typos in the semantics. More importantly,
it also includes an Appendix that describes a more consistent semantics for
exceptions; this is what we propose to implement in GHC 6.6.
Lock -Free Data Structures using STMs in Haskell
Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, and Satnam Singh.
Eighth International Symposium on Functional and Logic Programming,
April 2006 (FLOPS'06).
This paper explores the feasibility of re-expressing
concurrent algorithms with explicit locks in terms of lock free code
written using Haskell's implementation of Software Transactional
Memory (STM). Preliminary experimental results are presented which
show that for multi-processor systems the simpler lock free
implementations offer competitive or superior performance when
compared to their corresponding the lock based implementations.
Transactional memory with data invariants
Tim Harris and Simon Peyton Jones.
First ACM SIGPLAN Workshop on Languages, Compilers, and
Hardware Support for Transactional Computing (TRANSACT'06),
11 June 2006, Ottawa, Canada.
This paper introduces a mechanism for asserting invariants that are
maintained by a program that uses atomic memory transactions. The
idea is simple: a programmer writes check E where E is an
expression that should be preserved by every atomic update for the
remainder of the program's execution. We have extended STM Haskell to
dynamically evaluate check statements atomically with the user's
updates: the result is that we can identify precisely which update is
the first one to break an invariant.