Re: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications?
Simon Peyton-Jones simo...@microsoft.com writes: In contrast, in a pure functional language there are no reads and writes, so all the pure part has zero overhead. Only when you do readTVar' and 'writeTVar' do you pay the overhead; these are a tiny fraction of all memory accesses. I'm curious if there are any work done on the scalability of STM. Or rather - I expect the answer to be yes, but I'm curious what the results are :-) From my small time experiments, there seems to be a noticeable but liveable overhead to STM, even without collisions. This is to be expected. But there also seem to be scalability issues, and in particular, the time a transaction takes, appears to scale superlinearly (in fact, more than O(n²)) with the number of TVars involved. Is this correct? (This is a killer for TArrays if you naïvely try to do: x - atomically $ (newListArray (0,n-1) [0..n-1] :: STM (TArray Int Int)) and atomically $ unsafeFreeze x Instead, I had to do: x - atomically $ (newArray (0,n-1) 0 :: STM (TArray Int Int)) sequence_ [atomically $ writeArray x i i | i - [0..n-1]] and a - newArray (0,n-1) empty :: IO (IOArray Int Cluster) mapM_ (\i - do v - atomically $ readArray cmap i writeArray a i v) [0..n-1] unsafeFreeze a After doing this, I measure roughly a factor of two between (single-threaded) operations on TArrays and STArrays, which I think is pretty good. Remains to be seen how it scales with multiple threads, though...) -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications?
| Recently we discussed Haskell and especially types in Russian part of | LiveJournal and of course we talk about STM. | | My opponent gave me that link: | http://logicaloptimizer.blogspot.com/2010/06/so-microsofts-experiments-with- | software.html | | It says that performance with STM in Microsoft Research was more than | horrible. I can't resist replying to this. Several things to say: * STM requires runtime logging of every memory read and write. In an imperative language (such as C#), in which the very fabric of computation involves reads and writes, STM is bound to be expensive. [Lots of work has been done to omit redundant logging based on program analysis, but it's still expensive.] In contrast, in a pure functional language there are no reads and writes, so all the pure part has zero overhead. Only when you do 'readTVar' and 'writeTVar' do you pay the overhead; these are a tiny fraction of all memory accesses. So we get a huge win from the fact that Haskell's computational fabric is pure. * When do you need readTVar/writeTVar? Answer, precisely when you are manipulating state shared between threads. If you do a *lot* of this, your program is *bound* to perform badly; data has to be shuffled between processors, caches have to do their thing, etc. The key to high performance in parallel applications is to minimise sharing. If you do that, then you'll (dynamically) have few readTVar/writeTVars, and so regardless of how expensive they are it'll run fast. There are occasional data structures that are (a) necessarily shared and (b) necessarily hot-spots. Then STM is perhaps not the best solution, which is why GHC provides a range of primitives: as well as STM we've kept MVars, and we also have atomicModifyIORef which is even cheaper. Horses for courses. * The GHC STM implementation is simple. It's a direct implementation of our paper Composable Memory Transactions. We could make strong simplifying assumptions. In contrast, the Microsoft .NET project had to tackle a much more challenging set of requirements. In particular, they thought that programmers would *require* to be able to manipulate the same locations both *inside* and *outside* a transaction. It turns out that this simple requirement dramatically complicates the implementation [see multiple papers by Tim Harris on this topic]. Also they wanted nested transactions, and a raft of other complications. Each of these features was strongly motivated, and the MS guys in Redmond are extremely smart, but the result was necessarily complex and, as it turned out, unacceptably slow. Summary: it's simplistic to say STM good or STM bad. For STM to work well you need - very limited side effects in the computational fabric - limited communication between threads - a simple design Then STM can work extremely well. And it does in Haskell. But it's not a silver bullet; concurrency is too complex to be slain with one bullet. Indeed those precise words appear in every talk about STM I have given (eg http://research.microsoft.com/en-us/um/people/simonpj/papers/stm) Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications?
Thank you very much. This is just the answer I needed. 2010/8/8 Alberto G. Corona agocor...@gmail.com: -- Forwarded message -- From: Alberto G. Corona agocor...@gmail.com Date: 2010/8/8 Subject: Re: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications? To: Serguey Zefirov sergu...@gmail.com This first papers is the first that describes the preliminary haskell implementation and the performance data says that STM scales well with the number of CPU cores Blocking does not scale, as expected. http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/lock-free-flops06.pdf In this other study, also for microsoft: Dissecting Transactional Executions in Haskell. The worst performance in the study is from an extreme case example form my package TCache described here. In that example, a set of treads update the same two objects all the time. Since STM is non blocking, all threads tries to perform the task and rollback at the very end if things have been changed by other thread in the meantime. Just like databases. The bad thing is that the more CPU cores are executing the example, the more work being rolled back is done. That is more or less the history. I heard (The Monad Reader -mplementing STM in pure Haskell) about other tentative implementation that do not wait for the end of the atomic task to test the atomicity of the transaction, but instead, any update of a TVar inmediately invalidates (and kill) all atomic transactions that uses that TVar. This could potentially improve the performance a lot. However I don´t know the strategy of the current haskell implementation nor the strasategy of the Microsoft runtime(s) either. Anyway, it is waranteed 100% that 1) the slowest in memory transaction is way faster than the transaction delegated to the fastest external database. 2) in memory transactions with blocking is a nightmare. For me these are enough arguments for STM usage in many ordinary (I mean Web) applications. 2010/8/8 Serguey Zefirov sergu...@gmail.com Recently we discussed Haskell and especially types in Russian part of LiveJournal and of course we talk about STM. My opponent gave me that link: http://logicaloptimizer.blogspot.com/2010/06/so-microsofts-experiments-with-software.html It says that performance with STM in Microsoft Research was more than horrible. I failed to find convincing counter-evidence on the web. Not for Haskell, even for Java/C#/C++. So I asking Haskell-cafe for clarification. Do anyone here have an experience with STM in computing-intensive tasks? Did it help there? What are the possible reasons for STM failure in MR? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications?
My opponent gave me that link: http://logicaloptimizer.blogspot.com/2010/06/so-microsofts-experiments-with-software.html I enjoy the article you linked but I sort of skimmed it because it was a little boring, however its main point seem to be: 1. Ghostbusters. 2. Artificial intelligence is useless [1] 3. Listen to Anders! [2] An interesting sample: Anders Hejlsberg: Well, the best Software Transactional Memory implementations are still sitting at around 200% to 400% and that's even in best cases actually and still with Software Transactional Memory it's still, in a sense, it's still a problem of synchronization and shared state which... Carl Franklin: It's just under the lower level. Anders Hejlsberg: Some would argue it's t h e wrong way to look at the problem in the beginning. We shouldn't have the shared state to begin with. Richard Campbell: Right. Hat guy from xkcd (Enter stage left): But don't you see that Haskell has no shared state. That's exactly why STM is so great for doing concurrency in Haskell! (I maybe edited that a little there.) Ta ta, Johnny [1] Artificial intelligence is pointless http://www.youtube.com/watch?v=nvZBtJ-ncEM [2] The internet audio talkshow http://www.dotnetrocks.com/default.aspx?showNum=541 I found this transcript on google. Server seems to give of fake 404 pages, so have to hotlink :( http://perseus.franklins.net/dotnetrocks_0541_anders_hejlsberg.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications?
2010/8/8 Johnny Morrice sp...@killersmurf.com: My opponent gave me that link: http://logicaloptimizer.blogspot.com/2010/06/so-microsofts-experiments-with-software.html I enjoy the article you linked but I sort of skimmed it because it was a little boring, however its main point seem to be: 1. Ghostbusters. 2. Artificial intelligence is useless [1] 3. Listen to Anders! [2] Anders Hejlsberg: Some would argue it's t h e wrong way to look at the problem in the beginning. We shouldn't have the shared state to begin with. Richard Campbell: Right. Except that we have to write real apps is a real gem of that conversation. ;) Thank you very much for your points. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there any experience using Software Transactional Memory in substantial applications?
On Sun, Aug 8, 2010 at 6:09 PM, Serguey Zefirov sergu...@gmail.com wrote: Except that we have to write real apps is a real gem of that conversation. ;) So this Anders guy bashes functional languages and then says that programmers should be encouraged to write functional code in OO languages? Doesn't make any sense for me. Well, whatever =). Cheers! =) -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
