Transactional Memory - All Comments

re: STM.NET DevLab Incubation Complete

Anton — Wed, 18 Aug 2010 11:21:02 GMT

link to STM Programmer's Guide does not work

re: STM.NET DevLab Incubation Complete

JudahGabriel — Thu, 13 May 2010 04:43:03 GMT

Wow. So STM.NET is retired. Was technical problems the final blow? I remember Joe Duffy describing a <a href="http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetrospectiveOnTransactionalMemory.aspx">fundamental technical problem discovered in the STM bits</a> - is that what put the nail in the coffin?

re: Are we beyond the trough of disillusionment?

Guy Korland — Fri, 31 Jul 2009 07:41:42 GMT

@Torvald is right the programming model is much more important than that performance for most of the programmers. From my experience most of them are not even trying to handle concurrency issue and will not even try to use anything but coarse grained locking.

Saying that on that on the other hand the performance can't be dramatically low even for a single thread.

In Deuce we started to work on this single thread overhead and we expect to reduce it dramatically using very similar to the ways the GC overhead was reduced gradually.

BTW, we used Azul Vega2 (96 threads) and Sun Maramba (128 threads), for the big tests.

re: Are we beyond the trough of disillusionment?

dvyukov — Fri, 31 Jul 2009 01:42:24 GMT

Re: What really matters in the TM vs. locks vs. X debate is the programming interface.

Hmm... I guess single-threading will be a clear winner. No? Why one would want to see on anything else? I think there is something else except programming interface.

re: Are we beyond the trough of disillusionment?

Torvald — Thu, 30 Jul 2009 23:52:57 GMT

What really matters in the TM vs. locks vs. X debate is the programming interface. Atomic blocks don't specify how synchronization is implemented. This makes it a tough problem for the TM library+compiler, but at the same time if offers plenty of flexibility for how the TM+compiler actually implement this. This is an optimization problem that is largely decoupled from the composition of application code. It is a lot harder to optimize with locking (unless the application is trivial), especially if you do not know the workload a priori. It is hard to believe that every application can have built-in tuning for every possible synchronization workload. It is more reasonable to try this for an STM, because you build TM+compiler once and then use it in several applications.

And I think this is what Nir Shavit referred to. STM research doesn't need to care that much about expert programmers (eg, people working on OS kernels such as Solaris') as they can spend a lot of time on their code and are highly qualified. But, locking will be hard for larger teams of average programmers that develop applications with nontrivial synchronization, and that do not want to or cannot spend lots of development time on synchronization.

So, TM is, IMO, mostly about enabling a certain style of programming (atomic blocks for synchronization) that decreases development costs for a average programmers and ordinary applications. I don't see anything wrong with trying to accomplish this. Additionally, we actually do learn a lot about synchronization (unless when we just recycle old DB ideas :), and we do learn more about how failure atomicity and concurrency relate to each other in non-database settings (@Dana: do you remember the discussions at Transact08?).

Some more detailed comments:

The shared counter in time-based TMs is not a scalability problem, because you can use hardware clocks instead (many current machines already have suitable hardware clocks). For details, see

http://se.inf.tu-dresden.de/papers/preprint-riegel2007lsart.pdf

One possible approach to solve the "linked-list problem" is to use multi-level concurrency control, which has been investigated by database researchers long before the TM hype. Transactional Boosting is essentially multi-level concurrency control applied to a TM scenario with fast base objects (custom concurrent algorithms for data structures).

re: Are we beyond the trough of disillusionment?

Marek — Thu, 30 Jul 2009 18:33:28 GMT

> I will note that the Sun TM people are doing interesting

> work on avoiding this scalability bottleneck

Here is the paper describing this work:

http://research.sun.com/scalable/pubs/TRANSACT2009-ScalableSTMAnatomy.pdf

re: STM.NET Released!

Daniel Earwicker — Thu, 30 Jul 2009 16:00:08 GMT

Along with Atomic.Do, would you consider this:

public static T Get<T>(AtomicFunc<T> func)

{

T result = default(T);

try

{

result = func();

}

catch (AtomicMarker) { }

return result;

}

This would be nice and convenient, e.g. instead of (from the STM User Guide):

public bool Validate()

{

bool result = false;

Atomic.Do(()=>

{

result = (m_string1.Equals(m_string2) == false);

});

return result;

}

We'd just say:

public bool Validate()

{

return Atomic.Get(() => m_string1.Equals(m_string2) == false);

}

re: Are we beyond the trough of disillusionment?

dvyukov — Thu, 30 Jul 2009 00:20:07 GMT

Re: ----------------------------------------------------------------

Does STM have a bright future? Dan Grossman at U of Washington makes the analogy with garbage collection, and I think it's a good one: would you have predicted that GC would have a bright future in, say, 1985? Probably not, but it did. It turned out that there was cleverness to be had that people hadn't thought of yet. The same might still be true of software STM techniques.

----------------------------------------------------------------------

I am saying anything about 10-25 years future. I do not care about that. Probably that time STM will backed by HTM so that there will be no problem of instrumentation overheads and read scalability. Or maybe everyone will be using auto-parallelization stuff, so that nobody will care about such things as mutexes, threads and STM.

Arghhh, blog interface becomes too painful, probably we better move to:

http://social.msdn.microsoft.com/Forums/en-US/stmdevlab/threads

re: Are we beyond the trough of disillusionment?

dvyukov — Thu, 30 Jul 2009 00:16:05 GMT

Re:---------------------------------------------------------------------

In a managed world, the application doesn't usually have to do any memory or object lifetime management, and the GC and TM can be made to play together nicely. There are ways to do logging and statistics that do most things thread-locally, and only occasionally synchronize. Reads/modifications of shared data structures are of course shared, but whether they *scale* depends on the data structure. It's possibly to make a hash table scale pretty nicely. A queue is more problematic, by nature of its semantics. But in many circumstances you don't require "precise" queue semantics -- an approximate queue, that gives "roughly FIFO" ordering, may be adequate, and allow better scaling. So yes, sometimes you have to share -- but that doesn't mean you can't scale.

---------------------------------------------------------------------

Ah, you crack me, I can do and done all that stuff - roughly FIFO queues, cache-conscious hash tables, efficient blocking/signaling, zero-overhead rw mutexes, etc (http://groups.google.ru/group/lock-free/topics).

But (1) I would not call that easier that careful fine-grained locking at all, (2) I am not sure as to whether STM is a good tool for that, currently I use low-level atomics with fine-grained fences + a bit OS dependent stuff + a dash of hardware dependent stuff.

re: Are we beyond the trough of disillusionment?

dvyukov — Wed, 29 Jul 2009 23:57:31 GMT

For example, how STM can efficiently handle iteration over lengthy linked-list with concurrent mutations?

Yes, I can redesign the application or use something like AMD ASF's 'release' operation. But doesn't this defeat the whole point of simplicity and productivity? I guess that neither way will be fast and easy.

Btw, I proposed to incorporate 'release' statement (see http://developer.amd.com/assets/45432-ASF_Spec_2.1.pdf) into Intel STM, but they rejected the proposal. In you manual I see you mention 'open nesting' and 'abstract nested transaction' regarding linked list-problem. Are you going to incorporate something which will solve linked-list problem? Btw, does open nesting solve the problem? I'm not sure how...