How do you implement Software Transactional Memory?

Question

In terms of actual low level atomic instructions and memory fences (I assume they're used), how do you implement STM? The part that's mysterious to me is that given some arbitrary chunk of code, you need a way to go back afterward and determine if the values used in each step were valid. How do you do that, and how do you do it efficiently? This would also seem to suggest that just like any other 'locking' solution you want to keep your critical sections as small as possible (to decrease the probability of a conflict), am I right? Also, can STM simply detect "another thread entered this area while the computation was executing, therefore the computation is invalid" or can it actually detect whether clobbered values were used (and thus by luck sometimes two threads may execute the same critical section simultaneously without need for rollback)?

Answer 1

If you are going with .NET framework,

You can check out this experimental

• .NET 4.0 STM.Net
  
• .NET rocks podcast on STM.Net: Dana Groff and Yossi Levanoni Talk STM

Answer 2

GHC's STM implementation is described in section six of:

Composable Memory Transactions. Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP'05: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, Illinois, June 2005

And section five of:

Transactional memory with data invariants. Tim Harris, Simon Peyton-Jones. March 2006 TRANSACT '06

Answer 3

I suggest you watch this presentation: http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

In the second half it explains how to update values without leaving them in an undefined state. For example - if you have a tree that you want to update in STM-style you don't change the previous version at all. Let's say that tree is a pointer to the root of the tree. The only thing you create is the nodes that changed (but they can refer to nodes in the original snapshot of the tree.

Then you do a compare-and-swap on the tree pointer. If it succeeded, then everyone will now see your new tree and the old one can be garbage-collected. If it hasn't, then you repeat the process and the tree you just constructed is garbage collected.

The big idea is that you don't need to detect if anyone else changed the tree until you actually swap the new and old values, so there are no "conflicts" or "clobbered values" from the typical multithreaded programming.

Answer 4

The simplest answer is "it depends". There are tons of radically different implementations working in pretty much any way imaginable.

The part that's mysterious to me is that given some arbitrary chunk of code, you need a way to go back afterward and determine if the values used in each step were valid. How do you do that, and how do you do it efficiently?

One solution is to use versioning. Every time an object is modified, its version number is updated. While the transaction is running, you validate each accessed object's version, and when the transaction commits, you verify that the objects are still valid. This validation can be a simple integer comparison (if transaction_start_version >= object_version, the object is valid), so it can be done fairly efficiently.

This would also seem to suggest that just like any other 'locking' solution you want to keep your critical sections as small as possible (to decrease the probability of a conflict), am I right?

Very likely. I think a few implementations have gone the route of assuming/requiring everything to be a transaction, but yes, in most implementations, transactions are specially marked chunks of code, and the longer a transaction runs, the larger the chance of a conflict that may cause transactions to roll back.

Also, can STM simply detect "another thread entered this area while the computation was executing, therefore the computation is invalid" or can it actually detect whether clobbered values were used (and thus by luck sometimes two threads may execute the same critical section simultaneously without need for rollback)?

The latter. Keep in mind that the idea in TM is to protect data, rather than code.

Different code paths may access the same variable in different transactions. This has to be detected by the TM system. There's no real notion of "this area", since that refers to code, rather than data. The TM system doesn't care what code is executing, it tracks what data is being modified. In that way, it differs entirely from critical sections (which protect code, rather than data)