Initial Forays into Transactional Memory Programming Models

re: Initial Forays into Transactional Memory Programming Models

barrkel — Sat, 01 Nov 2008 03:27:40 GMT

You seem to have assumed away the basic problems of STM. How are developers supposed to decide what atomic{} needs to be wrapped around, and how are they going to be any better off than using lock{} as a result (modulo deadlocks, which are pretty trivial to fix given the stack traces)?

re: Initial Forays into Transactional Memory Programming Models

Dave Detlefs — Sun, 02 Nov 2008 09:13:46 GMT

This isn't just the basic problem of STM -- it's the basic problem of programming: what are the invariants that hold on data, and where do they hold? Like locks, "atomic" needs to be wrapped around any region of code that accesses shared data, either a read access where we depend on getting an invariant-consistent view of multiple variables, or a write access where we temporarily violate (but then re-establish) invariants across shared variables. I'm sorry we don't really know how to make this easier (but then I don't think anyone does.)

I do think you sell the advantages of TM over lock-based programming a little short. In my experience, maintaining lock orders in large programs can get *very* complicated. And in a lot of other situations you have to invent total orders on objects in order to have a lock order. (I have a set of bank accounts, each protected by a distinct lock, and I want to do a transfer from account A to account B -- which one do I lock first?) And there's another problem associated with locking that goes away with transactions: keeping track of what lock protects what data? That problem goes away with transactions, since you don't name locks explicitly.

So programming with TM is still like programming with locks in many ways -- *but* without a lot of the complications.

re: Initial Forays into Transactional Memory Programming Models

yossi.levanoni — Tue, 04 Nov 2008 04:03:52 GMT

Hello Barrkel,

It was my intention to elaborate on what we perceive as the advantages of TM only after we have described what TM is about to the less knowledgeable reader. So I wasn’t assuming this away as much as I was as saving it for later... You’re kind of jumping ahead of me.

Having said that, I agree with the points Dave lists and we will elaborate on these and others. I’ll just list some additional buckets of value associated with TM and leave it at that for now: scalability through optimistic concurrency control, enhanced atomicity correctness (one of the points we are apparently in disagreement about) and enhanced reliability through failure atomicity. Not all advantages hold equally well in different embodiments of the technology.

(Of course we’ll also have a hard look at the limitations of the technology, not only the benefits.)

re: Initial Forays into Transactional Memory Programming Models

Dmitriy V'jukov — Thu, 06 Nov 2008 15:33:22 GMT

Re: "We will explore these options in future blog posts but as a quick tip of the hat I would mention the work that our Intel colleagues have been doing on irrevocable actions [4]"

Must some link be here?

re: Initial Forays into Transactional Memory Programming Models

Dmitriy V'jukov — Thu, 06 Nov 2008 16:53:40 GMT

I think that first thing one have to say wrt advantages of TM over locking it that 80% of lock-based code is not susceptible to dead-locks in any way shape or form. If code holds at most one lock at a time... well, what's the problem?

Yes, there is 20% (or less) of involved situations, like classical example with bank accounts. And there are 2 time-proved simple solutions: ordered locking and hierarchical locking. Example with bank accounts can be solved trivially with ordered locking. Also it's possible to not hold read-locks, if we will allow more than 2 versions of object to coexist and writers will be just atomically replacing object with new version.

If above doesn't help, or just gets too complicated, only here TM comes into play with it's non-susceptibility to dead-locks (live-locks aside for a moment). In involved situation TM can help indeed. But what's the problem with concurrent queue?

Regarding lock-based queues and "scalability through optimistic concurrency control". Well, all STM systems I've seen to date a kind of trying to bring the whole system to it's knees by hardly saturating coherence interconnects at the first opportunity. All those global timestamps, global lists of in-flight transactions, global descriptor tables etc. Yeah, there is theoretical possibility that "transaction on this end of the queue can run concurrently with transaction on that end of the queue, because they work on different data". Will it take place? I mean real parallel work and real scalability, i.e. no modifications of global state, no reading of global state, only local processing.

Especially taking into account that most current STM implementations are lock-based. I.e. if thread inside of transaction will be descheduled or will be waiting for HDD access (10 ms)... Doesn't look superior to lock-based solutions... Just another set of caveats :)

re: Initial Forays into Transactional Memory Programming Models

Dmitriy V'jukov — Thu, 06 Nov 2008 17:01:35 GMT

Btw, I've described some of my thoughts about how it's probably possible to make STM really scalable (or at least get it close to performance of fine-grained locking) here:

http://software.intel.com/en-us/forums/whatif-alpha-software/topic/60873/reply/64582/

and here:

http://software.intel.com/en-us/forums/whatif-alpha-software/topic/61536/

re: Initial Forays into Transactional Memory Programming Models

Dmitriy V'jukov — Thu, 06 Nov 2008 17:55:24 GMT

The main idea behind 'transactional contexts', which I've described in the links above, it that the only thing thread have to do in order to execute transaction on the object is to acquire single mutex *local* to the object. I.e. no instrumented accesses, no read/write set maintenance, no RAW conflict resolution, no quiescence for privatization-safety, no accesses to global state, no mutations of global state, no readset validation, no retries etc etc.

It's a kind of safe reduction of full-fledged STM back to fine-grained locking.

Btw, managed environment provides interesting possibilities for 'transactional contexts'. For example, 'transactional context' can be associated with object at run-time based on some heuristics. Or 'transactional context' (physically no more than rw-mutex) can be somehow combined with 'SyncBlk index' hidden field of managed object (so no static space overhead).

re: Initial Forays into Transactional Memory Programming Models

Dmitriy V'jukov — Thu, 06 Nov 2008 18:09:51 GMT

Here is another interesting moment regarding semantics and features STM can provide - partial commits.

Assume we are iterating over lengthy linked-list, probably doing some processing for every item, or just searching for some node. Further assume we don't need total global atomicity/consistency wrt whole list (otherwise probably it will be 100% livelock), we need only local atomicity/consistency. I.e., for example, when we are processing node, we definitely don't want to process already removed node; but we don't require that no nodes was inserted into beginning of the list.

With locks we can do following. Lock node, process node, lock next node, unlock current node, process next node, lock next after next node and so on.

But we can mimic it with "atomic {}" syntax, because per-node transactions are overlapping!

re: Initial Forays into Transactional Memory Programming Models

yossi.levanoni — Sun, 09 Nov 2008 04:31:18 GMT

Dmitriy,

Thanks for pointing the broken citation for the Intel irrevocable actions work---I fixed it.

You raise some good points in your comments.

On the deadlock question, I would agree that many lock uses are "leaf locks" and are not susceptible to deadlocks. Many of these locks are also just there in order to do lazy-initialization, and this is something that we'll be helping developers with using all sorts of LazyInit classes. Still one has to wonder what fraction of these 80% (let's just take this number at face value for the sake of discussion) over time become non-leaf locks and whether the developer who is modifying the code is aware of the previous leaf-level assumptions. It takes just a small fraction of such mistakes to create bugs that are extremely costly to fix, if they are not caught on time. Regarding the rest 20% that are more complicated, some of them are "trivial" as you say but many are not at all so, and I'm taking a note to talk about this more.

Your comment on whether scalability is really possible in a real implementation, where you express skepticism about whether the system introduces its own scalability bottlenecks, when the application doesn't have any such bottlenecks, is also a good one. One concept that we use to evaluate the quality of implementations is *parallelism preservation* i.e. whether the system scales as a whole when the application access pattern indicate that such scaling is possible. Many implementations, for example TL2, are not parallelism preserving, since they contain contention on a global counter. With higher core counts this serialization effect is definitely visible. The Bartok STM is implemented using an algorithm that is extremely scalable and is to the best of my knowledge as close at you can get to true parallelism preservation. Published results indicate indeed very good scalability and our internal experiments confirm this.

Your observations on "transactional contexts" (I think maybe "data capsules" are a better term :-) remind me of a class of interesting work combining static and dynamic lock assignment based on data accessibility. Two interesting papers on this are:

Enforcing isolation and ordering in STM (from Intel research)

http://portal.acm.org/citation.cfm?id=1250734.1250744

Inferring Locks for Atomic Sections (from Microsoft research)

http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=1354

Most of these approaches require full program analysis and the ability to preclude aliasing of the data that is to be protected, which is sometimes not extremely practical, although the Intel paper explains how you can work with "incremental whole program analysis" that needs to re-JIT code once invariants are broken due to the loading of new code. Having said that, we're sure that there are a *ton* of optimizations of this nature that are possible and this is one of the reasons why we are still optimistic regarding the sequential performance cost of software TM...

Your last comment raises the question of whether it will be possible to do with TM things like hand-over-hand locking, prune things out of your transactional state etc. Some STM's that are out there allow you to do such things, at the cost of divulging a lot of implementation details. It's certainly possible, but we hope that such "tricks" will not be necessary in the common cases where people would want to use "atomic" blocks.

Thanks for all the feedback!

re: Initial Forays into Transactional Memory Programming Models

Joe Cromwell — Sun, 30 Nov 2008 07:59:48 GMT

Very intriguing... I wonder how transactions in C# interface with low level system code written in C++? Say I have some utilities I wrote in C++ that are called from C#. Today I use locks in C# to avoid problems. What would be the means to do the same in atomic world? Would I need to change my C++ code?