Transactional memory in a real world

Transactional memory in a real world | Coded Style

Transactional memory in a real world | Coded Style — Fri, 02 Jan 2009 22:47:26 GMT

PingBack from http://www.codedstyle.com/transactional-memory-in-a-real-world/

re: Transactional memory in a real world

Alex Baldassin — Fri, 09 Jan 2009 03:44:53 GMT

I have two comments. The first one is about I/O calls from inside transactions. It is not my main focus of work but at first sight it seems that they shouldn't be allowed since we are performing transactions on memory (that's why it's called transactional memory, after all). Even if you consider that most I/O operations are buffered, the problem still persists.

My second comment is actually a question. Have any of you read the experiences related by a group from IBM about STM ("STM: why is it only a research toy?" ACM Queue)? I talked to one of the authors (Siddhartha) in a recent conference and he looked quite skeptical about the future of both HTM and STM. Although this post discusses some related issues, how do you guys see the future of STM in more general terms? Or in other words, have you found an application domain where STM really seems promising in terms of programmability and/or performance?

-Alex.

re: Transactional memory in a real world

Sasha Dadiomov — Fri, 09 Jan 2009 22:26:25 GMT

Hello Alex,

Let me answer the first of you questions (about I/O); we will answer the second one separately.

Yes, in the academic settings transactional memory is usually associated with memory only. But it does not seem to be sufficient in the practical applications of TM: in many real scenarios, memory actions go along with logging, communication, database operations, and so on. Not always you can easily separate memory changes from these actions; we also think that in many cases you actually don't want to separate them at all. Failure atomicity of the combined memory / non-memory operation may be very desirable reliability feature - it makes error processing much more straightforward. For instance, if your program controls some real process or the game, it probably has some model description of the process in memory, and it probably wants to keep the description in sync with the reality. It would mean that sending control signal to the process and reflecting it in a memory should be parts of the same transaction.

Thanks, Sasha

re: Transactional memory in a real world

Alex Baldassin — Sat, 10 Jan 2009 04:31:55 GMT

Sasha, I do agree that it's not realistic to forbid I/O operations from occurring transactionally.

The problem with I/O operations (or side-effects in general) is that they don't fit the TM model. And that's because you cannot automatically just rollback their operation if you need to. That's particularly true for inputs. You cannot ask for user input inside a transaction because if it is rolled back the user will notice that.

For output actions you may attempt to defer the operation or create compensation code but it's a bit unclear to me its applicability in the general case. Moreover, it's highly likely that programmers will have to take part in devising compensation code and/or specifying whether the operation should be deferred to commit time. I am afraid programmers would prefer not to use TM at all in that case.

Taking into account the 'programmability' aspect, maybe it's better to execute the transaction in a non-speculative manner. Note that in this case you can still allow other read-only transactions to proceed in parallel.

Regards,

-Alex.

re: Transactional memory in a real world

Kimo Crossman — Mon, 12 Jan 2009 00:25:25 GMT

Interesting post on STM and mutability (functional vs imperative) and why new languages are needed as we move to 100 core scenarios.

http://enfranchisedmind.com/blog/2009/01/02/the-problem-with-stm-your-languages-still-suck/

re: Transactional memory in a real world

Sasha Dadiomov — Tue, 13 Jan 2009 19:37:14 GMT

Hello Alex,

Let me try to answer your latest comment... yes, if one takes TM idea to the extreme and seeks to use it indiscriminately all over the program, assuming that it just “magically” solves all sharing problems, eliminating any need for special considerations – it will probably not work well today... so if that is what you meant, I agree. But I meant a different situation: the user who has a clear understanding of a shared state elements in his/her design, and remembers it while writing the code. This kind of user will avoid unnecessary side effects; but in those (relatively rare) cases when he/she does want to have side-effecting operations inside of the atomic block (one example can be desire for failure atomicity), we hope to make it possible. In some cases it will just work, for those I/O operations that are already transactional – e.g. database like SQL Server, or messaging system like MSMQ – these can directly participate in system transactions, integrated with TM. In other cases, the developer may use an easy-to-use tool for enveloping his/her I/O in the transactional resource manager, or just defer/compensate I/O via TM-provided API. Clearly it does not make all cases easy; but we hope that most of them will be.

Non-speculative mode is another way to allow I/O, but it severely restricts scalability and seems to be the last line of defense... And I agree that input does not fit the TM model; but we think pure "output" scenarios can fit usefully.

Thanks, Sasha

Discoveries This Week 01/16/2009

Rick Minerich's Development Wonderland — Fri, 16 Jan 2009 19:26:39 GMT

This week’s theme is functional programming.  Included are discussions on Software Transactional

re: Transactional memory in a real world

Andrew Dinn — Wed, 21 Jan 2009 14:25:22 GMT

Nice post Sasha. You are right that the tool chain needs to keep up with the programming paradigm. As Danny Bobrow used to say, you have to be able to debug at the same level of abstraction at which you program.

But the bigger implication is that the programmer has to keep up with the paradigm too i.e. has to learn mentally juggle the different views of what the various parallel threads in the program are seeing. Locks avoid this issue, albeit at great cost, by introducing locally sequential regions. If you want the performance benefits of not imposing this sequencing the you have to pay the price of being able to think parallel.

Having been involved in implementation of both a HTM runtime and a conventional transaction service I tend to disagree with your view that STM and conventional hih level transactions (HTX) transactions need to be integrated. Firstly, I think this would be impractical without a fully transactional infrastructure through the whole runtime environment. But even given that I am not sure that it is desirable.

Implementing an HTX in a transaction service (including also the the thin layer which implements the client/participant component of the TX in a distributed service) requires making permanent various details of the ongoing transaction state (that's the D part of ACID). If those changes cannot be made permanent because they are subject to completion of an STM transaction (STX) allied to the HTX then you need to have some way of retaining this HTX state beyond a system crash. So, the transaction service itself needs to perform actions which have effect outside of the STX allowing it to recover the HTX in a new STX ceated when the system restarts. This also applies to implementations of participants such as databases, transactional web services etc

That's not to say that the transaction service cannot make good use of STM to implement itself. It's just that forcing every HTX to correspond 1-1 with a specific STX will hamstring the HTX implementation.

re: Transactional memory in a real world

Sasha Dadiomov — Mon, 26 Jan 2009 19:44:55 GMT

Hi Andrew, thanks for the post. Let me make myself more clear about what I meant for system transactions integration.

I never meant that EACH system transaction will make ALL memory operations in its scope atomic – this would be a bad idea. But I believe there will be enough cases when the developer wants that, and expresses it by explicitly by requesting a combined “system + STM transaction”, or nesting these two; the example could be maintaining reliable memory cache of some persistent state. To integrate STM with system transactions correctly, we need to make sure that on retries caused by the memory collisions every resource manager is rolled back (it surely knows how to do it because it participates in the 2-phase commit protocol). On the contrary, failure of any other resource manager is final and no retry is attempted (of course, everything is rolled back, including memory).

Developer will get ACID property for all relevant resources, though only “AI” for memory (D” has no sense for memory). All this is possible because all transactional resources can be rolled back. The benefit – developer gets failure atomicity across bigger set of resources, and avoids combinatory error processing. The application code may become shorter, cleaner, and more reliable, as it did with the advent of database transactions.

re: Transactional memory in a real world

Ihar Bury — Sun, 29 Mar 2009 17:30:48 GMT

I was thinking about parallel nested transactions. They seem for me a fundamental feature that allows really deep parallelism that is not controlled from a single method of code. That allows one atomic calculation invoke code that is parallelized itself further abstracting from the atomicity and parallelism of the calling code.

However, the behavior of parallel nested transactions discussed in the http://www.cs.rochester.edu/meetings/TRANSACT07/papers/agrawal.pdf article seems strange to me.

1 cilk void foo() { atomic { b++;... } }

2 cilk void bar() { atomic { ...,b++ } }

3 cilk void proc() {

4 atomic { // transaction X

5 b++;

6 spawn foo(); // transaction Y1

7 spawn bar(); // transaction Y2

8 b++;

9 sync;

10 }

11 }

"When Y2 increments b, there is a conflict with Y1, which is

running in parallel with Y2 and modifies the same variable

b. Since Y2 is nested inside X, however, Y2 does not conflict

with X, even though X also modifies b."

Why do we want "b++" at line 8 to execute in parallel with "b++" at line 2? Isn't the result of such execution unpredictable and hardly useful? For me it seems much more natural to write the code like

1 cilk void foo() { b++;... }

2 cilk void bar() {...,b++ }

3 cilk void proc() {

4 atomic { // transaction X

5 b++;

6 spawn foo(); // transaction Y1

7 spawn bar(); // transaction Y2

8 b++;

9 sync;

10 }

11 }

and have it automatically working as

1 cilk void foo() { atomic { b++;... } }

2 cilk void bar() { atomic { ...,b++ } }

3 cilk void proc() {

4 atomic { // transaction X

5 b++;

6 spawn foo(); // transaction Y1

atomic {

7 spawn bar(); // transaction Y2

atomic {

8 b++;

}

9 sync;

10 }

11 }

Thus treating spawn as an execution fork that automatically starts 2 nested parallel transactions -- one in the parent thread and one in the child thread.