Programming in the Age of Concurrency: Software Transactional Memory | Going Deep

staceyw
Before C# there was darkness...

Good stuff. Couple questions:

1) I missed a fundamental idea I think. It sound as if the last writer wins. So if I have an atomic block, I can make changes to state. But another thread can write to the state and commit, but the first atomic block will then rollback. What did I miss?

2) Charles, you had a good question that don't think was fully answered in the vid. Doing async in the block.

atomic()
{
      // Do some stuff
      BeginXXX(
           delegate(int i)
           {
                // Do some stuff in callback.
           }
}

We do some stuff and then kick off an async operation. But then we exit the atomic block right away because the async operation does not block. So the callback is not executed in atomic anymore. And worse yet, the code appears as if it is still executed in the block. What I am missing? Or was the answer just to never do this?

3) How does long running I/O and DB transactions play with this. So in a normal app, I would need both to be atomic. I need the in-memory objects to be atomic and the DB to be atomic in a single transaction. How does this work?

Thanks!

Charles
Welcome Change

Niners, please play with this (the C#/VB.net library may be easier to grasp given that Haskell is purely functional...). Tim and Simon need real world feedback. How would you use atomic blocks in your applications? What scenarios make use of atomic hard for you? See the links in the video post description. Also, please read the Composability paper (you don't have to be a scientist to understand it...)

Play with STM!

C

efortier

Another great one Charles. This is some pretty complex stuff to wrap your head around, and the bit about the garbage collector and all that's required to implement atomic transactions really went way over my head!

But I tell you, I wish I had this technology in the languages I use (C++ and Pascal) RIGHT NOW!

And Haskell is really getting some air time these days Wink

I love C9 videos!

apoc

"1) I missed a fundamental idea I think. It sound as if the last writer wins. So if I have an atomic block, I can make changes to state. But another thread can write to the state and commit, but the first atomic block will then rollback. What did I miss?"

The first one, like all blocks, will check for changes before commit and recalculate if they exist, i think.

efortier

staceyw wrote:
1) I missed a fundamental idea I think. It sound as if the last writer wins. So if I have an atomic block, I can make changes to state. But another thread can write to the state and commit, but the first atomic block will then rollback. What did I miss?

Your understanding sounds on par with mine, except that I don't see why the thread that commits its data wins and the other looses (except for the performance penalty).

If thread A tries to withdraw $100 from an account but there's no money in it, it retries which in effect puts it to sleep.

Then thread B comes along and credits $100 to the same account. Since no other threads are accessing that account, thread B can commit and continue its processing.

Then thread A wakes up since it detects a write to the account's memory and then retries the whole transaction which succeeds since the money is there.

Of course the thread that got into the retry state hits an additional performance penalty, but I think the whole idea of this system is to make things easier, not faster.

That sounds extremely powerful.

When you said the last writer wins, were you talking about performance?

staceyw wrote:
3) How does long running I/O and DB transactions play with this. So in a normal app, I would need both to be atomic. I need the in-memory objects to be atomic and the DB to be atomic in a single transaction. How does this work?

Yeah, there's still a lot of things that are still unknown.

In the debit/credit example, what if the money never gets deposited in the account? Does an atomic transaction has a timeout value? What if an atomic block triggers an external process of some kind by setting a property of an object?

I suppose there's a whole set of guidelines and restrictions we'd have to follow when using atomic blocks. Reading the papers available would surely answer most of the unknowns.

Eric

John Melville-- MD
Equality Through Technology

It seems to me that STM creates new problems with composability. You create two classes of code: atomic methods and non atomic methods.

Nonatomic methods can easily call atomic ones – the compiler could even automatically inject the atomic block if the programmer forgot.

Atomic methods and blocks cannot be allowed to call nonatomic code. The nonatomic code could do I/O or other irrevocable things that would be duplicated when the block had to retry.

This creates the exact problem that the “const” modifier has in C++. Your library writer has to anticipate everything you may want to do inside a transaction and provide you with an atomic version. By liberally making methods atomic, the author seriously limits future versions of the library because making a previously atomic method non-atomic is a breaking change.

In C++ they cop out and let you cast away the “constness” of a variable because there were too many places where the composition, exactly the problem you are trying to fix, didn’t work when you had one class of code that couldn’t call another class of code.

Its worse for STM because you can’t even cop out and say “use this sparingly.” Letting a transaction call nonatomic code creates the very race condition that you are trying to avoid, and makes them worse by running code many times that you have told the programmer to think about as only running once.

I am certain this will not be the first time this problem has come up, especially since you mention statically enforcing it in the compiler. I am just curious to hear what people think about what it will do to composability.

TimHarris

Hi, great questions --

staceyw wrote:
1) I missed a fundamental idea I think. It sound as if the last writer wins. So if I have an atomic block, I can make changes to state. But another thread can write to the state and commit, but the first atomic block will then rollback. What did I miss?

You're right, this is what the implementation in Haskell will do. But there's actually a lot of flexibility for the implementation to do other things -- maybe to guarantee some kind of fairness between threads so that the atomic blocks of one thread don't keep on getting rolled back by the atomic blocks of another, or to hold off the execution of one thread's atomic block because it's really likely to conflict with another (if conflicts are really likely then its best to run the atomic blocks sequentially rather than in parallel).

I think this is one of the nice things about atomic blocks -- the abstraction provided to the programmer is "all this happens atomically", but the implementation can do smarter things to reduce the wasted work caused by atomic blocks being rolled back.

If you want to read more about this aspect of transactional memory, then Michael Scott's group at U Rochester has done a lot of nice work in the area.

staceyw wrote:
2) Charles, you had a good question that don't think was fully answered in the vid. Doing async in the block.

atomic()
{
      // Do some stuff
      BeginXXX(
           delegate(int i)
           {
                // Do some stuff in callback.
           }
}

We do some stuff and then kick off an async operation. But then we exit the atomic block right away because the async operation does not block. So the callback is not executed in atomic anymore. And worse yet, the code appears as if it is still executed in the block. What I am missing? Or was the answer just to never do this?

That's a difficult question! As you say, one answer could be that this should never be done -- in Haskell we have a very clear separation between things that can be done in atomic blocks (like updates to shared memory), and things that can't (like creating new threads).

Another answer could be that the BeginXXX action kicks off the async operation as normal when the atomic block commits, but that the delegate runs in its own transaction when its called.

A third option is that the async actions are kicked off when the atomic block commits, and the delegates then just run normally. This option fits in with one of the ways that we've sometimes explained the semantics of atomic blocks: think of "atomic" as causing the thread entering the block to suspend all of the others in the system and then run in isolation, resuming the other threads when it reaches the end of the block.

As I said though, it's a difficult question; maybe there are better options than these three!

staceyw wrote:
3) How does long running I/O and DB transactions play with this. So in a normal app, I would need both to be atomic. I need the in-memory objects to be atomic and the DB to be atomic in a single transaction. How does this work?

Another great topic Smiley

. At the moment we're looking at adding features to the Haskell implementation to do this kind of thing. Basically it involves doing a two-phase commit that involves the transactional memory and the database -- that means getting the transactional memory and database to both vote that their part of the transaction is OK to commit, and then only doing the commit once both have voted OK. It adds some complexity to the implementation -- after the transactional memory has voted OK then it can't go back on its decision and abort. I did actually look at this kind of technique in an earlier system using transactional memory -- there's a bit about it in a paper "Exceptions and side effects in atomic blocks" linked from my page http://research.microsoft.com/~tharris.

The thing that's really important to remember for atomic blocks, though, is that it must make sense for the block's contents to occur as a single atomic action. For instance, atomic blocks that just perform input or just perform output are OK (e.g. we can buffer up the output until the block commits), but an atomic block that writes something on the screen, waits for a user's interaction, and then continues isn't OK -- that's really two separate actions (one before the user's input, and one after the user's input), rather than a single atomic action.

Tim

Alexis

This looks like fantastic work and a great step forward for solid concurrent programming without the the pain of deadlocks and race conditions.

I have one question, on timing: Say we have a long, slow atomic method A, and a swift method B. The System runs hundreds of B calls sequentially while on a different thread, method A is called. Now if I understand the model correctly, if a B call commits before A is done, A is restarted with the new data. Considering that B calls are run continuously and are always faster than A, will A ever be able to complete? Locking solves that with a ready queue, which keeps track of the next method to have exclusivity. How is that handled in STM?

Andrew Davey
www.aboutcode.net

Excellent video!
I downloaded the C# code and took a quick look.
Good work with the runtime proxy generation. Geez, it must have been painful writing all that emit IL code!

I'll take a look at writing some Nemerle macros to make the syntax nice. I'm thinking macros along the lines of:

foo = atomic(Foo(arg1, arg2))
<==>
foo = XAction.MakeFactory(typeof(Foo)).Create(arg1, arg2) : Foo;
-------------------------
atomic(foo.Bar(x,y,z))
<==>
XAction.Run(XStart(foo.Bar), x, y, z);
--------------------------
retry
<==>
XAction.Retry();
--------------------------
y = attempt { Get1, Get2 } (arg1, arg2)
<==>
y = XAction.Run(XAction.OrElse(new XStart(Get1), new XStart(Get2)), arg1, arg2) : int;

y = attempt {Get1, Get2, Get3} (arg1, arg2)
<==>
y = XAction.Run(XAction.OrElse(XAction.OrElse(new XStart(Get1), XAction.OrElse(new XStart(Get2), new XStart(Get3)))), arg1, arg2) : int;