Comment Feed for Programming in the Age of Concurrency: Software Transactional Memory (Going Deep on Channel 9)

Definition of atomicity of transactions

jseigh — Sun, 26 Nov 2006 13:47:55 GMT

How is atomicity of transactions defined? Basically you define atomicity with respect to other things. Write transations are obviously atomic w.r.t other write transactions, but what about reads? With single reads obviously you can't tell but what if you were traversing a linked list that had concurrent write updates being applied to it for example? On such a traversal, would you see all or none of any write transaction, or would you see parts of write transactions depending on which nodes in the list got updated and where you were in the traversal when the updates happened? Or are there read transactions as well? So before you traverse through the list, you start a read transaction so you get a consistent version of the list. And do you have retries on read transactions or do you use the memory management scheme to keep things consistent?

I had done some investigation is this area myself when I was looking on a couple of occasions at what it would take to make TDB (Trivial DataBase), which is used by Samba, lock-free using RCU for preemptive user threads (or something very much like it). On the second occasion I got around to looking at the actual code and realized that TDB had transactions. So I had to figure out how to do read lock-free transactions. Ultimately, too much work was involved for not very well defined benefits. But bascially when you do this kind of stuff (lock-free), you become aware of the importance of well defined semantics.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 19:26:05 GMT

DAMN! This fourm software mess my post again!!!

ArGH! Let be try one more time!

Here they are the introductory papers I used for my vZOOM coolthreads project...

http://appcore.home.comcast.net/vzoom/

http://appcore.home.comcast.net/vzoom/round-1.pdf

http://appcore.home.comcast.net/vzoom/round-2.pdf

http://appcore.home.comcast.net/vzdoc/atomic/static-init/

This is a major alternative to STM. It outperforms it by orders of magnitude. The video should have mentioned other ways of doing things.

Any thoughts?

-- P.S. this is in regard to the SUN CoolThreads contest:

https://coolthreads.dev.java.net/

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 19:24:56 GMT

Here they are the introductory papers I used for my vZOOM coolthreads project...

http://appcore.home.comcast.net/vzoom/

http://appcore.home.comcast.net/vzoom/round-1.pdf

http://appcore.home.comcast.net/vzoom/round-2.pdf

http://appcore.home.comcast.net/vzdoc/atomic/static-init/

This is a major alternative to STM. It outperforms it by orders of magnitude. The video should have mentioned other ways of doing things.

Any thoughts?

-- P.S. this is in regard to the SUN CoolThreads contest:

https://coolthreads.dev.java.net/

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 18:30:23 GMT

I almost forgot that the video mentions that they have to use Garbage Collector. I have STM that does not depend on a GC at all. Funny… I wonder why Simon and Tim depend on a GC? Its clearly not needed… A lightweight PDR scheme can implement STM…

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 17:58:21 GMT

Can you use STM to efficently solve this problem:

http://appcore.home.comcast.net/vzdoc/atomic/static-init/

Any thoughts?

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 15:18:26 GMT

For the record, I did not call you stupid. I want to know how you would address the Cell SPU with STM, that all...

:^)

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 15:11:58 GMT

“As for me not wanting to learn anything new… Well you wrong. I implemented STM. I know all of the issues. I have to make sure that I let everybody know what’s up, and let them get mislead by the marketing for STM."

ACK...

I meant:

As for me not wanting to learn anything new… Well you wrong. I actually implemented several versions of STM; I know all of the issues. I have to make sure that I let everybody know what’s up, and NOT let them get mislead by the marketing for STM.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 15:06:28 GMT

"Again, if you validate x and y before computing the if statement in A, it can't go wrong. This is not an unavoidable problem."

Okay, well that makes STM doubly expensive. You have to see if you can commit, before you try to commit? What if your validation contains thousands of read transactions? How to address very large shared linked data-structures in STM without livelock and explicit contention management?

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 15:02:51 GMT

Why would you use STM in a game engine? And how would use use STM on the Cell? Perhaps I, or somebody else at comp.programming.theads can help you get a MUCH better design for any engine you may be working on.

"You do know that the founder and technical director (Tim Sweeney)of Epic games (recently released Gears of War for the XBox 360) is a heavy advocate for purely functional programming and STM for games, right? If not, check out "The Next Mainstream Programing Language, A Game Developer's Perspective". But I'm sure you know more than both him and me."

Yeah. Well, if Tim says so... I happen to completely disagree with him. BTW... Sadly, a lot of game programmers are not talented multi-threaded programmers:

http://groups.google.com/group/comp.programming.threads/msg/2c477272953fc5e0

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6fe2dd51631afee5

http://groups.google.com/group/comp.arch/search?hl=en&group=comp.arch&q=games+multi-core&qt_g=1

That’s the sad truth. STM is not going to help them learn how to leverage lock-free programming against their very high-end game engines synchronization needs. I bet Tim doesn’t let his programmers use any Assembly Language either? I doubt it. I also doubt that he would choose a STM based engine, over a lock-free engine that outperforms it by an order of magnitude. He would have to be crazy to do something like that.

IMHO, game programming is all about squeezing all of the horsepower you can out of the architecture. STM prevents this because it will be flooding the cache coherency system with boat loads of unneeded traffic. Humm… Assembly language and game engines… Do they go together? Yes. Big time. Its going to be interesting to see how the gaming industry programs the Cell with STM… Wow. Its basically impossible. How to address the SPU with STM?

As for me not wanting to learn anything new… Well you wrong. I implemented STM. I know all of the issues. I have to make sure that I let everybody know what’s up, and let them get mislead by the marketing for STM.

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 14:45:59 GMT

You use the splendid "you must just be stupid" argument, which is just great. So game engines are not difficult to parallize if you're smart enough, thus using any technology which would make this easier is an admission of stupidity. Well that's just great. Have fun with that.

You do know that the founder and technical director (Tim Sweeney)of Epic games (recently released Gears of War for the XBox 360) is a heavy advocate for purely functional programming and STM for games, right? If not, check out "The Next Mainstream Programing Language, A Game Developer's Perspective". But I'm sure you know more than both him and me.

Also, I'm just going to stop arguing with you right here. I dislike your argumentation style, and you don't seem interested in learning anything new. Though I do think it's funny that you pretend to be an expert on game engines, and then proceed to share your wisdom on the subject to educate poor me in case I ever want to work on games (for the record, I actually work on game engine technology for a living, for the XBox 360).

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 14:37:42 GMT

cristom wrote:
One problem with implementing software transactional memory is that it's possible for a transaction to read inconsistent state (that is, to read a mixture of old and new values written by another transaction). Such a transaction is doomed to abort if it ever tries to commit, but it's possible for inconsistent state to cause a transaction to trigger a fatal exceptional condition such as a segmentation fault or even enter an endless loop, as in the following contrived example from Figure 4 of "Language Support for Lightweight Transactions":
atomic {
    if (x != y) 
        while (true) { }
}
Transaction A
atomic {
    x++;
    y++;
}
Transaction B
Provided x=y initially, neither transaction above alters this invariant, but it's possible transaction A will read x after transaction B updates it but read y before transaction B updates it, causing it to enter an infinite loop. The usual strategy for dealing with this is to intercept any fatal exceptions and periodically check if each transaction is valid; if not, it can be aborted immediately, since it's doomed to fail in any case.

Again, if you validate x and y before computing the if statement in A, it can't go wrong. This is not an unavoidable problem.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 14:28:12 GMT

“E.g. let's say you have a game world, and 10000 game objects that interact with it in complex and data dependent ways (i.e. there is no way to partition the world into lockable regions). Each of these objects interact with about half a dozen of the other objects, and they do so concurrently, and the interactions must be atomic. How do you solve that with lock free data structures? The game world consists of multiple different data structures nested in complex ways (oct-trees, portal cell graphs, BSP trees, etc.). How do you solve it with locks? You really don't, unless you stick a big lock on the entire world, or use some global locking order or something equally detrimental to composability and productivity. STM in this case "Just Works".”

If you don’t know how to write a high-end multi-threaded game engine without using STM, that’s your problem. Game engines HEAVILY benefit from assembly language and other assorted low-level tricks and techniques. Low-overhead lock-free algorithms are a must. STM in a game engine? No way. I want my game to be very fast. STM would prevent the game engine from realizing the full potential of today’s high-and architectures…

BTW, how would STM work on the Cell Processor? I don’t think it’s even possible for STM to even being to make use of the Cells SPU’s. Ha…. You want to program games? Do you know assembly language inside in out? Do you know how to use DMA with the Cells AltiVec SPU to shunt from shared memory to local SPU memory? Do you know the PPC instruction set? Do you know distributed/network programming paradigm for the Cell? What about the XBox 360? Why bog down its PowerPC with all of the coherency traffic generated from the crappy TM?

You want to get into game engines? I suggest posting something overing comp.programming.threads and/or comp.arch. BTW, have you ever programmer the IBM Cell Processor or have you done any lock-free synchronization algorithms that use the PPC instruction set? Do you know the AltiVec instruction set? I have experience with all of these. I would not want you on the design team if alls you have to say to synchronization issues in the game engine is STM… No way no how!

How skilled are you wrt high-end game engine synchronization issues? They are basically the same issues that exist in the fast-pathed part of a database server… Anyway, please follow-ups in comp.programming.threads and/or comp.arch. This forum seems to get too crowed...

Humm…

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 14:15:48 GMT

One problem with implementing software transactional memory is that it's possible for a transaction to read inconsistent state (that is, to read a mixture of old and new values written by another transaction). Such a transaction is doomed to abort if it ever tries to commit, but it's possible for inconsistent state to cause a transaction to trigger a fatal exceptional condition such as a segmentation fault or even enter an endless loop, as in the following contrived example from Figure 4 of "Language Support for Lightweight Transactions":

atomic {
    if (x != y) 
        while (true) { }
}

Transaction A

atomic {
    x++;
    y++;
}

Transaction B

Provided x=y initially, neither transaction above alters this invariant, but it's possible transaction A will read x after transaction B updates it but read y before transaction B updates it, causing it to enter an infinite loop. The usual strategy for dealing with this is to intercept any fatal exceptions and periodically check if each transaction is valid; if not, it can be aborted immediately, since it's doomed to fail in any case.

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 14:11:05 GMT

cristom wrote:
One other MAJOR *point about TM... STM or HTM, my implmentation or not, both "suffer" from a not so well known phenomena:

Inconsistent data can, and will, be accessed in a transactional atomic block! A users algorithm for a transactional based system is based solely inside of an atomic block, e.g.,

atomic { // start transactional atomic block

users_algorithm{
// Access transactional data-structures
}

} // try to commit transactional atomic block

This means that the users algorithm can actually "operate" on inconsistent data... No kidding, not at all... therefore, a users algorithm behavior is basically undefined, whether the programmer likes it or not... Think about it for a minute... If your algorithm is fed with "no-so coherent" data, then your algorithm will be subject to undefined behavior by default...

Wow... The implementations that I have seen have to actually catch any and all fatal exceptions that can, and WILL, arise when a user algorithm is subjected to inconsistent data... Sometimes your algorithm crashes right off the bat and gets intercepted by the STM where the transaction will be aborted, and retried... Sometimes your algorithm will be stuck in an infinite loop (most common problem, IMHO) , inside the atomic block... STM has to watch out for this kind of stuff... IMHO, this is a MAJOR drawback and a down right dangerous aspect of transactional memory... This behavior is inherent in basically any TM implementation; hardware or software...

Need to think some more on this troubling subject... Now you know just some of the reasons why I don't like TM...

Yikes!

:O

* I can't believe I forgot to mention this; totally slipped my mind. Right when I remembered this I went over to Wikipedia to see if anybody bring this fact up; somebody did... IMO, its vital that anybody who thinks about using TM completely understands this particular caveat!

This may be a problem in C, but not in Haskell.
Haskell uses lazy evaluation, i.e. it's demand-driven. Nothing will be computed unless it's needed, and before any of writes are performed or data returned and forced by the caller (which is the only two things that can force evaluation) the accessed transactional variables are checked for consistency.

I.e. if you do something like the following in Haskell:

atomically $ do {
v1 <- readTVar t1;

v2 <- readTVar t2;

writeTVar t3 ( willDivergeIfInconsistent v1 v2 )
}

t1 and t2 will be validated before t3 is written to, and the writing of t3 is the only thing that will force willDivergeIfInconsistent to be evaluated, and at that point v1 and v2 are guaranteed to be valid, thus nothing will ever be evaluated with inconsistent data.
This holds for every atomic computation, even with interleaved reads and writes, since all the data used by a function will be validated before it can be retrieved and thus must be at least consistent enough to execute the call properly.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 13:43:54 GMT

One other MAJOR *point about TM... STM or HTM, my implmentation or not, both "suffer" from a not so well known phenomena:

Inconsistent data can, and will, be accessed in a transactional atomic block! A users algorithm for a transactional based system is based solely inside of an atomic block, e.g.,

atomic { // start transactional atomic block

users_algorithm{
// Access transactional data-structures
}

} // try to commit transactional atomic block

This means that the users algorithm can actually "operate" on inconsistent data... No kidding, not at all... therefore, a users algorithm behavior is basically undefined, whether the programmer likes it or not... Think about it for a minute... If your algorithm is fed with "no-so coherent" data, then your algorithm will be subject to undefined behavior by default...

Wow... The implementations that I have seen have to actually catch any and all fatal exceptions that can, and WILL, arise when a user algorithm is subjected to inconsistent data... Sometimes your algorithm crashes right off the bat and gets intercepted by the STM where the transaction will be aborted, and retried... Sometimes your algorithm will be stuck in an infinite loop (most common problem, IMHO) , inside the atomic block... STM has to watch out for this kind of stuff... IMHO, this is a MAJOR drawback and a down right dangerous aspect of transactional memory... This behavior is inherent in basically any TM implementation; hardware or software...

Need to think some more on this troubling subject... Now you know just some of the reasons why I don't like TM...

Yikes!

* I can't believe I forgot to mention this; totally slipped my mind. Right when I remembered this I went over to Wikipedia to see if anybody bring this fact up; somebody did... IMO, its vital that anybody who thinks about using TM completely understands this particular caveat!

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 13:30:41 GMT

cristom wrote:

ACK!!!

"I am mostly talking about database servers the make heavy use of shared memory for fast-pathing database queries. I can traverse mutable data-structures with atomic operations and/or memory barriers. "

Is suppose to read as:

I am mostly talking about database servers the make heavy use of shared memory for fast-pathing database queries. I can traverse mutable data-structures "WITHOUT" atomic operations and/or memory barriers.

Sorry for any confusion.

Again, what does this prove? Nothing!
"I have this prime number generator written in asm which is much faster than the same algorithm produces when compiled with VC, ergo C is useless."

Again, you point out specific cases where existing technology works well, and conclude that STM is useless. The point here though is that there are plenty of applications which are essentially single threaded because splitting them up in multiple threads is too difficult to be a feasible proposition. It's for these difficult cases, cases where the traditional methods are too difficult to use, that STM will help.

The point is that STM is really nice and elegant for the general case. Your whole argument basically boils down to premature optimization. Use STM, if it's too slow somewhere, and you can find a way to get it faster (most likely by compromising your ability to use this abstraction in a composable way in the future - which may be a completely valid tradeoff) then you are free to do so. Just like you can use inline asm in C where it's needed.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 13:25:28 GMT

"Actually I'm really not. I've posted twice why I don't think this makes sense in an imperative language."

I think we have to agree to disagree on this. I have no problems with using C for creating high-end multi-threaded applications.

"I would recommend you post it and point it in the direction of Simpon Peyton Jones and Tim Harris though. If your implementation really is as good as you say, and it does what the Haskell one does, I'm sure they will be willing to do it your way instead."

Its definitely as good as I say it is, however, it doesn’t have some of the features that Haskell has. You should think of my STM as a “lean-and-mean” minimalist version. I was trying to go for extreme speed in the STM implementation itself, some of the stuff that Haskell uses makes this impossible.

;^(…

Anyway… I will think this over. To patent, or not to patent. I wonder how popular a fairly speedy C/C++ STM alternative to Haskell would actually be. I personally would not even want to use my STM in any of my application infrastructures’. But if most of the programmers go for STM, I could do well by providing a top-notch minimalist alternative in C/C++.

Humm..

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 13:16:24 GMT

ACK!!!

"I am mostly talking about database servers the make heavy use of shared memory for fast-pathing database queries. I can traverse mutable data-structures with atomic operations and/or memory barriers. "

Is suppose to read as:

I am mostly talking about database servers the make heavy use of shared memory for fast-pathing database queries. I can traverse mutable data-structures "WITHOUT" atomic operations and/or memory barriers.

Sorry for any confusion.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 13:12:54 GMT

"And you don't have to. Writing a web server probably doesn't require STM at all."

I am mostly talking about database servers the make heavy use of shared memory for fast-pathing database queries. I can traverse mutable data-structures with atomic operations and/or memory barriers. Again, this is impossible with STM. Using STM would make that fast-path run very slow because of the vast amount of coherency traffic that the TM logic generates.

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 13:12:05 GMT

cristom wrote:

C is fine. You can create STM implementation in C/Assembly.

...

Interested?

Actually I'm really not. I've posted twice why I don't think this makes sense in an imperative language. I would recommend you post it and point it in the direction of Simpon Peyton Jones and Tim Harris though. If your implementation really is as good as you say, and it does what the Haskell one does, I'm sure they will be willing to do it your way instead.

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 13:06:22 GMT

cristom wrote:

I am not willing to sacrifice my server applications performance. Sorry, not sold.

And you don't have to. Writing a web server probably doesn't require STM at all.

The whole point here is, again, that you take some very simple cases say "X is faster than STM in case x, Y is faster than STM in case y" and you ignore all the difficult cases alltogether, or the fact that STM is an easy to use technology which Just Works for both x and y without having to do anything special (again, nobody has claimed that it isn't possible to write multithreaded programs without STM, please try to understand that very important point).

Embarassingly parallel applications (like e.g. a web sever) are not hard to write, and you can get a way with very light weight abstractions that are very fast indeed. But try writing, say, a game engine which scales to hundreds or thousands of threads and you'll understand that a couple of clever lock-free data structures is not a viable solution for parallellizing problems in general.
Again, if you're going to compare against "alternatives", please do so in an intellectually honest way, rather than cherry picking specific examples where there are existing data structures that work well. The whole point here was that with STM it's all of a sudden a reasonable proposition to split something like a game engine up into hundreds and thousands of threads - something which is very difficult to do without something as general and flexible.

Your argument is akin to someone arguing that assembly is better than C because a couple of small programs he's written were faster when written in hand tuned assembly than when compiled with a C compiler. It might be true, but that doesn't mean assembly is a better choice in general. For sufficiently large applications you're not going to be able to do any meassuring of the difference in performance, because only one of the version will actually run properly (the one which sacrifices speed for usability).

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 13:03:39 GMT

C is fine. You can create STM implementation in C/Assembly. Just follow the rules:

http://groups-beta.google.com/group/comp.programming.threads/msg/423df394a0370fa6

Okay… If I had to use STM, I would use it in C, not Haskell. Humm, I have created experimental STM that try to get around some of the overheads. Still not sure I want to Patent it or not. Perhaps I should patent it, and sell it as a much faster alternative to most of the STM implementations’. Humm. A couple of implementations of mine beat Haskell by a wide margin. Indeed.

Okay… If I can’t convince you the STM is not a good solution at all… How would you feel about using a STM algorithm with a pure C interface? I have several solutions. I created them way back when I was experimenting/inventing my vZOOM algorithm. I needed something to test it against. I was very disappointed with every STM implementation out there. So, I invented a couple of new ways to implement STM… I guess if STM is going to be rammed down programmer’s throats, I might as well get the experimental prototypes’ and post them here…

I have 2 STM word-based implementations. One is written is about 75% IA-32 assembly language, and the other is in about 90% SPARC V9 assembly language… The all have C API/ABI. Standard transaction API (e.g., begin, load, store, commit, abort, validate), and they all outperform Haskel.

Interested?

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 12:42:23 GMT

"I really think you're not really trying to see the point here. It also seems that you may have a financial interest in not seeing the point. Which makes arguing with you pretty much a waste of time."

IMHO, STM is a deceptive marking ploy. They never get into the alternatives’. BTW, I mention many different ways to do things. I did not just refer you to my vZOOM algorithm; I also refer you to Joe Seighs RCU+SMR algorithm, and some others. So you wrong again… Unlike the video, I point out all of the caveats, and explain them in detail.

"Look at the video again. They specifically say that skilled programmers can use existing techniques to write correct code - they're not claiming that it's not possible to work around the difficulties of multi threaded programming with existing techniques. The point here, though, is that it is difficult. Your own posts is are a case in point. Why are you so proud of your inventions of various lock-free data structures if it's so easy?"

The complexity can be hidden behind a simple and portable API, that anybody can use. Like the pthreads api. We all know that a particular pthread implementation may be very complex, and may very well use some lock-free algorithms. But, does the average user actually care about this kind of stuff? My point is, again "The complexity can be hidden behind a simple API". Really.

Would there be bugs... Well, maybe; it depends on the implementer. There may be very subtle bugs in your pthread implementation as well...

"Because it isn't very easy, which is the whole reason for why you want STM instead."

No. STM is NOT a good solution if you’re interested in execellent scalability and performance.

"Getting everything right with locks or lock-free programming techniques is difficult - if you're selling software based on this I can understand why you would argue otherwise, but I'm not going to waste my time arguing against a paycheck (everyone whose salary isn't based on pretending it's easy will agree that it's difficult). Not impossible, but difficult. Your argument that it's possible to use other strategies is completely pointless. It's possible to write a full comercial business application using nothing but assembly as well, but is it practical? No not really, and as concurrency becomes more common using the sophisticated and clever lock-free programming techniques will stop being practical as well."

Utter nonsense. The power of lock-free programming techniques will be in demand. Man. Concurrency has been common for a very long time now. Ever heard of RCU? Heck, this stuff, including STM and HTM has been around for the past 25 years at least. Don't try to act like this is something new. Lock-free has been around for ages, and it not going to go out of practice. Its going to be in demand. That is, if you want your application to have excellent scalability and throughput characteristics

"What if I want to read 4 elements, or none at all, from your nice lock free FIFO queue?"

Simple, you use an eventcount.

"What if I want to do that operation on two different FIFOs > (from different vendors), or none at all? What if I want to combine that with some operations of my > own, or do none at all?"

This is example of bad programming practice. Having to force things together is a sign that there is a MUCH better way. The overhead involved with your request is too great. Again, I urge to you to post to comp.programming.theads and comp.arch. Please.
Anyway, you can use the eventcount to add fine-grain ultra low-overhead conditional blocking and coordination of your data with lock-free collections. Too much to post here. The technique deserves its own thread. STM can’t compare with this wrt scalability; its dead in the water. The performance increases of most alternatives to STM are usually an order of magnitude.

"STM composes because you can create new concurrency abstractions from existing ones without having to have access to the source code of the original abstractions."

I am not willing to sacrifice my server applications performance. Sorry, not sold.

Re: Programming in the Age of Concurrency: Software Transactional Memory

sylvan — Sat, 25 Nov 2006 12:42:05 GMT

cristom wrote:

For those who don't follow links, here are some important snippets from some of them:

SNIP!

Okay, this is only slightly less annoying/insulting than outright spam. Clicking links was not the problem, having to deduce your points from multiple related discussions, was. You're not that important to me. I don't care about you enough to read everything you've posted on related subjects and from there figure out where you stand on this issue.

If you have a specific point that has to do with STM, please make it. If you have a specific point to anything someone else posted here, please make it.
If, however, you don't feel like you have time and energy to extend the common courtesy of doing so in a coherent way by formulating it specifically for this discussion, in a way which flows naturally together with the topic of discussion, then please note that posting here is completely volontary.

Also, please note that examples are not proof. Yes there are, as said many times already, cases where STM will be slower than other methods, but listing them is completely irrelevant. The point here is that there are plenty of cases where STM helps out a lot, and is probaby the only practical way of writing software in certain circumstances. E.g. let's say you have a game world, and 10000 game objects that interact with it in complex and data dependent ways (i.e. there is no way to partition the world into lockable regions). Each of these objects interact with about half a dozen of the other objects, and they do so concurrently, and the interactions must be atomic. How do you solve that with lock free data structures? The game world consists of multiple different data structures nested in complex ways (oct-trees, portal cell graphs, BSP trees, etc.). How do you solve it with locks? You really don't, unless you stick a big lock on the entire world, or use some global locking order or something equally detrimental to composability and productivity. STM in this case "Just Works".

Yeah, STM for a FIFO is overkill, but showing how a non-STM implementation of a FIFO is faster than an STM based one does not prove that STM is a waste of time. Again, you're pitting STM up against other approaches only in very simple cases, which proves exactly nothing.

Re: Programming in the Age of Concurrency: Software Transactional Memory

cristom — Sat, 25 Nov 2006 12:16:44 GMT

For those who don't follow links, here are some important snippets from some of them:

> I am wondering where RW locks are appropriate ??

Basically, they work fairly well with "read-mostly" data-structures. If you
don't really care about performance and scalability, then most rw-mutex
implementations should work perfectly fine; however, in some cases they are
definitely not an "optimal solution". For instance, IMHO a rw-mutex would
probably not be an ideal candidate for protecting a "critical shared
collection" than can experience episodic periods of sustained
"moderate-to-heavy write activity". Reader threads that use rw-mutexs to
protect such a container would probably not perform and/or scale very well
at all with regard to adding cpus. One of the reasons why is usually due to
the fact that most rw-mutex implementations force reader threads to use some
rather expensive atomic/membar/blocking methods in order to enforce
synchronization and proper data-coherency among the participating
processors; this is not very cache friendly, not at all. Reader threads
would not really be able to keep the processors "caches primed" and probably
would not experience the full benefits of a modern multi-processor system.
For instance, a reader thread that "frequently" executes a store/load style
membar would constantly be "invalidating and thrashing the cache"; not good
at all! The thread could spend most of its time "waiting" for the
modifications to the "rw-mutexs internal state" to become "fully visible" to
all of processors involved. This process is usually made up of fairly
expensive operation(s) that may involve the overhead of cache snooping
and/or locking the system bus. The overhead involved could actually prevent
reader threads from truly exeuting in parallel; not good.

Therefore, IMHO, a rw-mutex is generally a bad solution for a critical
shared data-structure if the overhead of acquiring and releasing it is
greater than the overhead of "reading the data-structure in a
single-threaded application"...

> is it appropriate when only you don't want 'dirty' reads??

Not really, but yes they do eliminate the possibility of processing "stale
data"; however, as stated above the methods involved are usually expensive.
Fortunately, there is a more advanced class of algorithms out there that do
not tend to add a boatload of extra overhead and can allow reader and writer
threads to execute in parallel. Please note that this behavior alone can be
beneficial to many application designs. For instance, since readers no
longer block writers an existing synchronization design can usually be based
on a "much simpler locking scheme"; however, stale reads can and will occur
in this type of setup. Luckily, one can address stale/dirty reads in a
number of interesting ways:

http://groups.google.com/group/comp.programming.threads/msg/523aa1e77...

Another solution for stale reads involves writer threads making copies of
existing shared data-structures and then atomically swapping them with the
existing ones. A garbage collection scheme can be used to free the "old"
data-structures. This solution does not add overhead to reader threads,
unless, the method of garbage collection used is sub-optimal...

"John Hickin" <http://www.computer.org/portal/site/computer/menuitem.5d61c1d591162e4b0ef1bd108bcd45f3/index.jsp?&pName=computer_level1_article&TheCat=1005&path=computer/homepage/0506&file=cover.xml&xsl=article.xsl&
("The Problem with Threads" - IEEE's Computer magazine article)

> This example is quite good and it explains what I don't like with threads.
> In the real world, 8 of the 10 people in your example will go on to do
> something else. In a multi-threaded world, 8 threads are blocked.

http://groups.google.com/group/comp.programming.threads/msg/a3e38e27d...
( refer to the pseudo-code at the bottom of the msg )

Any thoughts?

> Unless, of
> course, you use some sort of lock-free algorithm. Unless I've missed the
> mark, lock-free is quite avant guard, and not taught at the undergraduate
> level. It may be time for a change there.

Totally agreed:

http://groups.google.com/group/comp.lang.c++.moderated/msg/d07b79e963...

FWIW:

I don't agree with the commonly assertion that lock-free programming is far
to complicate for a "normal" programmer to learn.

I also don't agree with the assertion that threads are vastly too difficulty
and fragile for any programmer to use... The paper the OP linked to seems to
attempt to make this type of assertion.

> Anyway, the article was interesting to read. The author is an IEEE Fellow,
> and you don't get that designation without earning it.

Humm... Did you read the part where is basically says that programmers that
use threads are insane? He points to a "folk saying",

'repeatedly performing the same action and expecting different results
defines a form of insanity'
(paraphrase)

The he says this, again paraphrasing

'if programmers that use threads were not insane, they simply would not be
able to understand any of their programs'

I wonder if he was being serious... Anyway....

Yikes! I guess that I am INSANE!!!!!!!!!
YeeeHaw.... Weeeee.....

;)

I find it amusing that the IEEE Fellow seems to not be able to create a
thread-safe observer pattern... I have several lock-free observer patterns
that can rely on my vZOOM or Joe Seighs RCU-SMR algorithms.

For some reason, I don't think that the author could create a highly
scaleable thread-safe, lock-based or lock-free, observer pattern
implementation if his life depended on it???

(simply EXECELLENT Wheeler posts!!!)

"Chris Thomasson" <http://www.garlic.com/~lynn/

"Chris Thomasson" <http://www.garlic.com/~lynn/subtopic.html#545tech

the trick then was to come up with a mnemonic that matched Charlie'
initials, CAS.

the attempt was then made to get the instruction into the up and
coming 370 architecture. working with ron smith in the pok 370
architecture group (they owned the 370 architecture "red book"), the
response was that 370 didn't need another multiprocessor specific
instruction, that the test and set from 360 was sufficient.

to get compare and swap into the 370 architecture we had to come up
with useage for compare&swap that wasn't multiprocessor specific.
thus was born some number of examples that were applicable to
multi-threaded applications that might be running enabled for
interrupts ... independent of whether the machine was single processor
or multiprocessor.

originally in the 370 principles of operation, the examples were part
of the programming notes that were part of the compare&swap
instruction. in subsequent version of the principle of operations the
examples were moved to a section in the appendix.

also as part of this activity, compare&swap double instruction was
added in addition to compar&swap. that resulted in two instructions
for 370, compare&swap along with compare&swap double ... so the
instruction mnemonics become CS and CDS (instead of CAS ... defeating
the original objective of coming up with instruction name
compare&swap).

total topic drift ... science center was like that ... GML
http://www.garlic.com/~lynn/subtopic.html#sgml

precusor to SGML, HTML, XML, etc ... also invented at the science
center, actually are the first initials of the last name of the three
inventors (and you probably thot it stood for generalized markup
language).

misc. past posts on multiprocessor support and/or compare&swap
instruction
http://www.garlic.com/~lynn/subtopic.html#smp

esa/390 principles of operation appendix for multiprogramming
(i.e. multithread) and multiprocessing
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/A...

cs & cds appendix:
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/A...

bypassing post and wait
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/A...

lock/unlock:
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/A...

free pool manipulation
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/A...

and more recent z/architecture (64-bit) principles of operation
multiprogramming and multiprocessing examples appendix
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9ZR003/A...

note that the above also includes discussion of the newer PLO ...perform lock
operation instruction

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

- conversation with Andy...

http://groups.google.com/group/comp.arch/browse_frm/thread/71f8e0094e353e5/a3ebfe80363a4399?lnk=gst&q=why+do+double+wide+compare+and+swap&rnum=1#a3ebfe80363a4399

"Andy Glew" <http://groups.google.com/group/comp.arch/msg/d40cf092b679169d

Coarse reservation granularity can cause live-lock in LL/SC via. simple
false-sharing. I really do believe that HTM is going to suffer from the same
thing... Multiple processors can live-lock if they keep interfering with the
reservations that track the TM.

Humm... Kind of like the live-lock that is inherent in any obstruction-free
algorithm; they need to use "backoff-and-retry" algorithms to keep up
forward-progress...

Good response post form Intel Architect Andy Glew:

> Humm... Kind of like the live-lock that is inherent in any obstruction-free
> algorithm; they need to use "backoff-and-retry" algorithms to keep up
> forward-progress...

Yeah, I was thinking of correcting my older post to try to get to this.

It is not fundamentally LL/SC vs. CAS and other atomic RMWs.

It is more that LL/SC was originally proposed and implemented via an
"optimistic concurrency" type of address "link", whereas CAS and other
atomic RMWs are traditionally implemented via a "lock" - whether bus
lock, cache lock, or address lock.

If other people try to access the lock while the RMW is in flight they
are stalled or told to go away, come back later. This guarantees
forward progress.

Whereas if other people access the link between the LL and SC, it is
the SC that fails. In the presence of an adversary doing ordinary
stores, the LL/SC might never complete.

But these are just implementation artifacts. E.g. you can implement
CAS or an atomic RMW with LL/SC, whether in user code or microcode -
and such an RMW would have the same forward progress problems as
LL/SC. You can implement a hybrid - try the optimistic concurreny
approach first, and then try the lock approach.

Similarly, you can implement LL/SC by acquiring a lock, guaranteeing
that the SC will finish. But then you need some way of backing out,
protecting yourself against a malicious user who does the LL but never
the SC. E.g. the Intel 860 released such a lock after 32 instructions.

Chris Thomasson wrote:
> "Joe Seigh" <> if your 32-bit applications used DWCAS, then they can be run 64-bit arch
> without changes... Of course there is a caveat...

> A 32-bit application cannot use DWCAS to manipulate a pointer along with
> another contiguous variable...

> struct dosent_work_on_64_bit_s {
> void *a;
> whatever b;
> };

> IMO, the hardware architects' did NOT have lock-free algorithms in mind when
> they decided to put DWCAS in their 32-bit instruction sets. The fact that
> 128-bit CAS is not reliably supported seems to support my opinion...

IBM S370 had double wide compare and swap long before 64 bit support
became an issue.

>>There's a bit of a disconnect here I think.

> Perhaps they are designing the lock-free algorithms for a upcoming processor
> design. Maybe one that has hardware transactional memory... That could be
> the reason they designed KCSS:

They've done a bit on STM (software transactional memory). If they did
come out with hardware based transactional memory it would be after the
fact of 64 bit sparc and wouldn't be generally available. So it would
have to be hidden behind some system or library api with alternate
implementations on non TM platforms. That would limit its applicability.
For example, you couldn't have atomically thread-safe refcounted smart
pointers. Well, not without RCU and/or SMR. If they go with STM to
compliment hw TM, it's only going to work at a lower contention level
if the STM algorihtm is only obstruction-free.

It's a big problem. You can design efficient synchronization mechanisms
that are portable if you ignore Sparc. If you want portability to
Sparc you have to sacrifice performance or functionality.

If Sun has a 64 bit JVM implementation, I wonder what they do for
the AtomicMarkedReference and AtomicStampedReference implementations
for non Sparc platforms. Cripple them so they perform as poorly as
the Sparc implementations?

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

Text taken from:

http://groups.google.com/group/comp.arch/msg/e1e391055c7acecb

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/9c572b709248ae64

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f6399b3b837b0a40

http://groups.google.com/group/comp.arch/msg/1b9e405080e93149

http://groups.google.com/group/comp.arch/msg/bbbc035cf1a8502c

http://groups.google.com/group/comp.arch/msg/11b14c4bda2d5d82

http://groups.google.com/group/comp.arch/msg/9b00fda2752966f9

http://groups.google.com/group/comp.arch/msg/335aeb22fd6fe526

http://groups.google.com/group/comp.arch/msg/1ace9400b1b16cd4

http://groups.google.com/group/comp.arch/msg/995379a16beb3b69
(simply excellent Wheeler post)

and more...

Any thoughts?
;^)