tag:blogger.com,1999:blog-5135517.post9221475601658748797..comments2023-11-05T03:54:44.710-08:00Comments on Making it stick.: Misguided: The Road Not To Be TravelledPatrick Loganhttp://www.blogger.com/profile/02088461489050417591noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-5135517.post-88050358430015596182009-10-22T13:13:35.082-07:002009-10-22T13:13:35.082-07:00Afaics, STM does not solve the algorithm problem f...Afaics, STM does not solve the algorithm problem for massively parallel games any way:<br /><br />http://lambda-the-ultimate.org/node/2048#comment-51596shelbyhttps://www.blogger.com/profile/04192118408905938326noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-43703708546550290202008-07-04T02:05:00.000-07:002008-07-04T02:05:00.000-07:00Oh, yeah. I remember this convoluted post of mine....Oh, yeah. I remember this convoluted post of mine.<BR/><BR/>"They are different abstractions, each with different advantages and disadvantages."<BR/><BR/>Of course they are. Then the issue is how do they stack up against each other.<BR/><BR/>"The bit that amuses me most here is that you are treating the Actor model and the STM model as if they are in competition."<BR/><BR/>That's how I've seen it presented, so I would suggest I am responding to that.<BR/><BR/>"The truth of the matter is that Erlang has STM implemented on top of Actors (Mnesia), while Clojure has Actors implemented on top of STM."<BR/><BR/>No. Mnesia is a database in the traditional sense that the shared data is outside of the address space of the process/thread/vm runtime. STM is transactional over some or all of the address space of the process/thread/vm. Having programmed for a number of years with a multi-user STM (in particular, Gemstone Smaltalk and Gemstone Java), I prefer Erlang's shared-nothing message passing + Mnesia database combination.Patrick Loganhttps://www.blogger.com/profile/02088461489050417591noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-8462810181125284142008-07-03T23:18:00.000-07:002008-07-03T23:18:00.000-07:00The bit that amuses me most here is that you are t...The bit that amuses me most here is that you are treating the Actor model and the STM model as if they are in competition.<BR/><BR/>The truth of the matter is that Erlang has STM implemented on top of Actors (Mnesia), while Clojure has Actors implemented on top of STM.<BR/><BR/>They are different abstractions, each with different advantages and disadvantages.Anonymoushttps://www.blogger.com/profile/07555989787959778978noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-75888464044663219582007-09-16T05:33:00.000-07:002007-09-16T05:33:00.000-07:00Thanks for the nice post!Thanks for the nice post!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5135517.post-49758241411149272752007-02-13T07:45:00.000-08:002007-02-13T07:45:00.000-08:00STM (at least as normally proposed) is shared-stat...STM (at least as normally proposed) is shared-state, optimistic transactions. Its <A HREF="http://www.eros-os.org/pipermail/e-lang/2007-February/011873.html" REL="nofollow">complexity and performance problems</A> come from the shared state and the optimistic scheduling, not the transactions. It's possible to support transactions in a shared-nothing model, and that still provides the same (actually better) composability.David Hopwoodhttps://www.blogger.com/profile/06228059623703767101noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-75054637994570917302007-02-09T13:11:00.000-08:002007-02-09T13:11:00.000-08:00I just wanted to chime in because this is a rare p...I just wanted to chime in because this is a rare position to hear articulated, and I agree. I'm deeply uncomfortable with the universal push toward STM. It's very similar to the universal push toward GC (which I will refrain from criticizing here). Real programs spend much of their time performing non-transactional updates to local variables and doing IO. STM does not help them. Rather, it introduces a whole family of abstractions, complexity and cost and imposes it all over the language and runtime design. This cost is real cognitive load that every programmer and implementor must pay for.<BR/><BR/>Moreover, in the few cases where some form of transactional behavior <I>is</I> desired, there's no reason to believe a generic STM implementation from a programming language will provide the sort of transaction your problem domain demands. It may not write to stable storage, it may have incorrect scope or priority rules, it may lack auditing or logging that you want, and it may have undesirable policy wrt. resource starvation.<BR/><BR/>I'm all for process isolation. Message passing and STM both demand that. It's true that any generic message passing service may similarly fail to meet problem-domain needs and does impose its own implementation and language-design costs. But my gut feeling is that the transaction abstractions will be more complicated to understand, more expensive to implement and more often useless in the field than the messaging abstractions.Anonymoushttps://www.blogger.com/profile/16102413207713374088noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-59722249840719587622007-02-08T13:43:00.000-08:002007-02-08T13:43:00.000-08:00Having written several implementations of both STM...Having written several implementations of both STM and various message-passing-based concurrency models for Ruby lately, I'm a lot less sunny on STM than I used to be even a few weeks ago.<BR/><BR/>I was having fun implementing STM until I realized that I was able to implement the Actor model correctly in a few hours, versus several weeks for getting the fiddly aspects of STM down.<BR/><BR/>The biggest immediate problem for STM is starvation -- a large transaction can just keep retrying, and I'm not sure there is a way to address that without breaking composability. ...and composability is the whole raison d'etre of STM in the first place.MenTaLguYhttps://www.blogger.com/profile/12206115951900114525noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-49955518240142284102007-02-07T20:51:00.000-08:002007-02-07T20:51:00.000-08:00"Suppose you have a bank server with clients happi..."Suppose you have a bank server with clients happily communicating deposits and withdrawals to it, and everything is working. How do clients implement a transfer between accounts safely?"<BR/><BR/>In practice banking systems do this with asynchronous messaging and post-hoc reconciliation. STM doesn't help because:<BR/><BR/>(a) account information must be persistent<BR/><BR/>(b) banks must store audit trails and coordinate different in-bank business processes so distributed transactions are needed to coordinate the different systems<BR/><BR/>(c) clients must be able to transfer money between different banks and the systems involved cannot be coupled as tightly as ACID transactions allow.Nat Prycehttps://www.blogger.com/profile/14593335423887511402noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-46863210117933043012007-02-07T16:48:00.000-08:002007-02-07T16:48:00.000-08:00I think STM has some very attractive aspects, most...I think STM has some very attractive aspects, most notably efficiency and composability. I see it as a better replacement for other low-level concurrency constructs, but not for large scale systems.<br /><br />I admit not to have any hands-on experience with STM (though I do have a fair amount of experience with Erlang-style concurrency), but I have a few concerns about it.<br /><br />The first concern is that I'm not sure how much the composability of STM will scale. If layers upon layers of transactions are built, I fear some dependencies between layers might start surfacing at upper levels, causing surprising conflicts. It could become hard to get it right. I can see misguided programmers starting to sprinkle their code with 'atomic' statements ("just in case"), a bit like one would do with 'yield' statements in a non-preemptive concurrent system. Also, 'atomic' statements could be forgotten, causing nasty bugs (Haskell neatly avoids that problem, though).<br /><br />But my main concern with it is that after all, STM is still shared-state concurrency. It mixes together the control flows of programs in ways that can be hard to visualize and comprehend. Erlang doesn't have that problem, because every "connection point" of a process with the exterior is obvious and well-defined. I also don't think STM is well adapted to distributed programming.<br /><br />For low-level programming, I think STM could be very useful. But in the end, it seems to only solve a small part of the problem, and it doesn't really help with the actual design of concurrent systems.Guillaume Germainhttps://www.blogger.com/profile/15075505822262756677noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-55361929463752480912007-02-07T16:35:00.000-08:002007-02-07T16:35:00.000-08:00your grievances seem to be much more with distribu...your grievances seem to be much more with distributed systems than STM in particular.<br /><br />the one thing i really like about STM is that good implementations are exactly like ZFS, copy on update. instead of simply obliterating old state, STM simply forks out new states. currently, any place where data over time is relevant requires user implementation to store history, which usually means debugging tools and printf(). to me, history is just a series of transactional states, and being able to lookup old states seems like second nature. i would really like to see more Saga like transactions available in the mainstream.<br /><br />ubiquotous computing is, almost explicitly, the art of comptuing in distributed shared state. thats my own personal chief interest. if you've got magic bullets for this, the world is always buying.rektidehttps://www.blogger.com/profile/03381475657715288786noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-24727151955044086402007-02-07T16:33:00.000-08:002007-02-07T16:33:00.000-08:00your grievances seem to be much more with distribu...your grievances seem to be much more with distributed systems than STM in particular.<br /><br />the one thing i really like about STM is that good implementations are exactly like ZFS, copy on update. instead of simply obliterating old state, STM simply forks out new states. currently, any place where data over time is relevant requires user implementation to store history, which usually means debugging tools and printf(). to me, history is just a series of transactional states, and being able to lookup old states seems like second nature. i would really like to see more Saga like transactions available in the mainstream.rektidehttps://www.blogger.com/profile/03381475657715288786noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-23112323253302966722007-02-07T15:23:00.000-08:002007-02-07T15:23:00.000-08:00Cale, I actually think we are in agreement.
The t...Cale, I actually think we are in agreement.<br /><br />The thing is, in a functional language like Haskell, the STM semantics are both easily abstracted away and useful because almost everything else about the physical machine has also been abstract away, including the CPU.<br /><br />In imperative languages, the CPU isn't abstracted away like it is in Haskell. This is often a good thing at it allows us to better predict and optimize performance bottlenecks. However, shared state threading now voids our traditional abstractions and assumptions about the data we are operating on. To take advantage of it, we have to tread very carefully and be sure to NOT do lots of things we can otherwise take for granted.<br /><br />I don't see that adding STM to conventional imperative languages will improve the situation significantly, if at all. For declarative languages, like Haskell however it is a win because it fits well with the language model (same thing with SQL).Damienhttps://www.blogger.com/profile/07299732457242903370noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-24156194811114938422007-02-07T14:43:00.000-08:002007-02-07T14:43:00.000-08:00I have to admit, I have a horrible gut feeling abo...I have to admit, I have a horrible gut feeling about STM. I really don't like it. It's one of those wrinkles in a carpet things. It seems to have smoothed out a wrinkle but all it's done is push the wrinkle somewhere you can't easily see it. It makes for good looking publications but I have major doubts about how it will work in practice. But as I say, this is just a gut feeling, and it'll take longer for me to articulate exactly why I think there are problems. But it's nice to know that there are other people in the world having issues with STM.sigfpehttps://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-49793865965814589322007-02-07T14:27:00.000-08:002007-02-07T14:27:00.000-08:00Transaction memory is another hack bolted on to al...<i>Transaction memory is another hack bolted on to all the previous concurrency hacks, and somehow it's going to make all the other concurrency hacks to work reliably. Yeah right.</i><br /><br />I don't get this remark at all. How is it "bolted-on"? Perhaps the compiler will implement transactions in terms of locks and condition variables, perhaps it won't.<br /><br />In order to work properly, a software transactional memory system essentially has to control what things may occur in transactions. In particular, anything with side effects cannot occur within a transaction, because those could not be rolled back should the rest of the transaction fail. (Provisions could be made for queuing side-effecting computations for when a transaction completes, but that is inessential, and could be written in terms of the core functionality.)<br /><br />This is not something which you can just "bolt-on" to existing systems, unless you have very good static control over side effects in your language. For the time being, that restricts you to one of a handful of languages, Haskell being the foremost of those. Even in Haskell, STM isn't just a library, because there are provisions to be made in the garbage collector for things to work properly.<br /><br />The major advantage of STM as a system is that it gives you certain guarantees about composability of already working systems. It's not magical, it doesn't always ensure that things will play nicely together, but it <i>does</i> give you far more guarantees about the correctness of compositions than previous systems have. (And in analysis, decomposing code into subsystems, the correctness of which will guarantee the correctness of the system as a whole via the guarantees.)<br /><br />Please read the paper <a href="http://research.microsoft.com/~simonpj/papers/stm/stm.pdf"><i>Composable Memory Transactions</i></a> from <a href="http://research.microsoft.com/~simonpj/papers/stm/index.htm">here</a>. The <i>Beautiful Concurrency</i> article there is also a good introduction. Neither article assumes that you know all that much about Haskell, but <i>Beautiful Concurrency</i> is probably gentler if you don't.<br /><br />That being said, if you understand the additional compositionality guarantees, what exactly is it that you find lacking? Limiting shared state is obviously good -- there's nothing in this system which prevents that. However, it's a system for cleanly sharing any state which should be shared. Other forms of communication, including those in Erlang still have this problem to deal with.<br /><br />Suppose you have a bank server with clients happily communicating deposits and withdrawals to it, and everything is working. How do clients implement a transfer between accounts safely? You have to be really careful, because a client which observes the accounts involved in the transfer in between the withdrawal from one and deposit into the other will observe the money in neither location, or worse, in both locations. You would have to go back to the bank server code and write your own ad-hoc transaction mechanics for this, or implement a middle-man process which handles forming the transactions and ordering the communication to the original server, or worse still, you'd end up with some sort of mess of a system of locks.<br /><br />STM is at some basic level about bundling working thread communications together such that they occur as-if-atomically with regard to the rest of the system. They might not actually occur atomically, it just has to behave as if they do.<br /><br />Consider the "orElse" operation. It joins two transactions such that if the first succeeds, it gets to commit, and if it retries, then the second is attempted. If the second succeeds, it commits, and if it retries, the entire transaction retries. For a transaction to retry means that it behaves as if nothing has actually happened, and it's attempted at a later time, generally after one of the inputs it had read has been updated. In this way, arbitrarily many options may be tried in turn.<br /><br />Also, if an exception is thrown, the transaction it occurred within behaves as if it never happened, and the exception bubbles upward in a sane fashion until it is caught. There's no scrambling to replace all the locks that were taken before throwing the exception, up to where it will eventually be caught, like you'd get in a lock-based system.<br /><br />Anyway, this is getting long and I probably can't do as good of a job of it as the paper can, so everyone please check it out before writing more gibberish about transactional memory.Cale Gibbardhttps://www.blogger.com/profile/02239068589033148700noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-28726566669980856302007-02-07T14:17:00.000-08:002007-02-07T14:17:00.000-08:00The interaction between distributed (and therefore...The interaction between distributed (and therefore concurrent) activities involves two things: data transfer and coordination. Synchronisation to avoid race conditions is just one form of coordination. Systems also need to coordinate activities that don't share data. Message-passing covers all forms of coordination. Does software transactional memory support coordination? Or must that be supported by other primitives, such as semaphores or monitor condition variables?Nat Prycehttps://www.blogger.com/profile/14593335423887511402noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-15983323470859227722007-02-07T11:04:00.000-08:002007-02-07T11:04:00.000-08:00I read the same article and it just frightened me....I read the same article and it just frightened me. All that magic hidden under the covers, bleuch.<br /><br />It's deadly shine'y because at the surface it appears like it just makes all the concurrency stuff such as locks "go away" in line with many a programmers desire to ignore such details. Couple that with the familiarity most have with transactions and you're looking at premium car-wax, retina burning shine'y.<br /><br />I don't even want to imagine debugging one of these systems. You're going to be confronted with some strange behaviors due to transaction conflict or whatever and because it's all supposed to be done by magic under the covers wading in there to understand what's broken will be a nightmare. It'll make debugging from Java thread-dumps look like a holiday.<br /><br />Dan<br />http://www.dancres.orgPetrolHeadhttps://www.blogger.com/profile/06404572533828179184noreply@blogger.comtag:blogger.com,1999:blog-5135517.post-52795276003737216862007-02-07T10:12:00.000-08:002007-02-07T10:12:00.000-08:00I *completely* agree.
Shared state threading is a...I *completely* agree.<br /><br />Shared state threading is a hack built on to existing languages. A useful and fairly efficient one, but a hack nonetheless. And like raw pointers and unprotected memory, it's hard to justify it's use for most programming tasks. Compared to languages like Erlang, it's nearly impossible to justify it on efficiency or performance concerns.<br /><br />Transaction memory is another hack bolted on to all the previous concurrency hacks, and somehow it's going to make all the other concurrency hacks to work reliably. Yeah right.Damienhttps://www.blogger.com/profile/07299732457242903370noreply@blogger.com