6 ms·

PyPy - We need Software Transactional Memory

135 points by j4mie 15y ago

codedivine 15y ago
STM sounds all nice, yet there are few implementations of STM currently that give better performance than a good serial implementation.
- exDM69 15y ago
  I hope you have sources and/or benchmarks to support your claims. Bashing a promising future technology without any backing is not constructive.
  - wynand 15y ago
    codedivine has a point and it's even admitted in this posting: "we expect the initial performance to be abysmally bad (maybe 10x slower); however, with successive improvements to the locking mechanism, to the global program transformation inserting the locks, to the garbage collector (GC), and to the Just-in-Time (JIT) compiler, we believe that it should be possible to get a roughly reasonable performance (up to maybe 2x slower)." It will likely be difficult to beat expertly written code using explicit locks. But most people aren't experts in concurrency and will either get it wrong or have slow implementations. And if transactional memory catches on, we may even see some hardware assistance in future CPUs. (S)TM is definitely worth exploring more and even a 2x slower implementation (as envisioned by the PyPy team) could cover most concurrency needs, which will make it a success in most people's eyes.
    - kbd 15y ago
      Do they mean 2x slower than CPython or 2x slower than PyPy? If they wind up with something 2x slower than current PyPy (which is much faster than CPython in many cases), that'll still be a version of Python much faster than CPython that doesn't have the limitations of the GIL and can thread across cores, and that'll be a huge win.
  - codedivine 15y ago
    One good read is: http://queue.acm.org/detail.cfm?id=1454466 http://queue.acm.org/detail.cfm?id=1454466 "Software Transactional Memory: Why Is It Only a Research Toy?" by Cascaval et al. I think transactional memory systems with at least some hardware support are potentially more interesting.
    - exDM69 15y ago
      Some of the problems addressed in the papar can be solved with compiler enforceable constraints such as is done in Haskell's type system. What comes to the performance, the benchmarks in the paper range from no speedup at all with 8 cores to having 1.5x perf increase with 2 cores to 4x increase with 8 cores. To me, that definately sounds like something worth researching.
      - scott_s 15y ago
        The point of that paper is that they have been researching it, quite extensively. But the performance results have often been disappointing, and the semantics of nested transactions can be surprisingly complex. At what point do you start looking into other things?
- masklinn 15y ago
  There's the same issue with normal locks: any synchronization primitive is going to incur overhead. That is, in fact, one of the defense heralded by some in the Python community against the "GIL should Go" mobthink.
  - scott_s 15y ago
    I think you misunderstood codedivine. His point was not that applications that use STM and make use of a single thread are slower than sequential implementations of the same application. We expect the parallel implementation's single threaded performance to suffer by a percentage or two (or ten...) because it has to do more hardware-level atomic operations. codedivine's point was that it is often the case that applications implemented with STM that use multiple threads often perform worse than the sequential version. See the excellent ACM Queue article he links to in a sibling comment.
    - masklinn 15y ago
      > I think you misunderstood codedivine. His point was not that applications that use STM and make use of a single thread are slower than sequential implementations of the same application. And the experience has been exactly the same in locks-based GIL-removal tests in Python: David Beazley recently "unearthed" and tested a GIL-removal patch from the 1.4 days[0]... > To test threads, I wrote a small sample that subdivided the work across two worker threads is an embarrassingly parallel manner (note: this code is a little wonky due to the fact that Python-1.4 doesn't implement thread joining--meaning that you have to do it yourself with the included binary-semaphore lock). > [...] > If you run this code with the GIL, the execution time is about 2.5 seconds or approximately 1.3 times slower than the single-threaded version (1.9 seconds). Using the GIL-less Python, the execution time is 18.5 seconds or approximately 1.45 times slower than the single-threaded version (12.7 seconds). Just to emphasize, the GIL-less Python running with two-threads is running more than 7 times slower than the version with a GIL. [0] http://dabeaz.blogspot.com/2011/08/inside-look-at-gil-removal-patch-of.html http://dabeaz.blogspot.com/2011/08/inside-look-at-gil-remova...
      - 15y ago
- cabacon 15y ago
  Then again, hardware transactional memory may be arriving: http://www.eetimes.com/electronics-news/4218914/IBM-plants-transactional-memory-in-CPU http://www.eetimes.com/electronics-news/4218914/IBM-plants-t...
  - pjscott 15y ago
    Note that it's currently limited to transactions will fairly small read and write sets, but this is not an inherent limitation of hardware transactional memory, and it can be used as part of a hardware/software hybrid system to accelerate small transactions. I'm pretty excited. The chip modifications here are really small and cheap, so I think we may start seeing this in more mainstream server chips in a few years.
chalst 15y ago
Does this proposal entail writing Python code without mutation of non-local state? Isn't this harder in Python than in Haskell or Ocaml?
- masklinn 15y ago
  > Does this proposal entail writing Python code without mutation of non-local state? Pypy using STM should not change the semantics of the Python language or require alterations to code which does not rely on implementation details (code which relies on the GIL for its thread-safety may have to be fixed, it already has to be fixed for Jython compatibility). > Isn't this harder in Python than in Haskell or Ocaml? I'd expect STM to be much harder in imperative languages than in functional languages indeed. In fact, I don't think I've heard of a successful STM implementation in imperative languages yet. On the other hand, I think most tentatives so far have been with STM as a library applied explicitly, and you run into issues of (mutable) objects "crossing" the transaction barrier in imperative languages, issue which "does not" happen in Haskell (there are ways to subvert the type system, but then you're on your own. In normal uses, I think objects under STM live in a different monad, and therefore can't be freely mixed with objects living outside of it) (I believe this issue would happen in OCaml, so on that front OCaml would be little better than imperative languages). This issue should not exist if all of the code runs under STM (ignoring explicit hooks to do so built into the system), and this should allow for "easy" implementation of explicit memory transactions as well (one of STM's promises is composability, so you should be able to compose multiple bytecode-transactions in a single explicit transaction).
wgren 15y ago
>if [a JVM thread] reads a field of an object, and another thread writes to the same field of the same object, then the program will see either the old value, or the new value, but not something else entirely Nitpick: unless the field in questions is a "long" or "double". In those cases the operation becomes two bytecodes and you can in fact see something else entirely if you are unlucky. At least it used to be like that.
- palish 15y ago
  On 32-bit platforms. On 64-bit, you won't. =)
deleted 15y ago
[deleted]
- masklinn 15y ago
  Have you considered reading the fine article? That issue is covered.
true_religion 15y ago
I'm a little disapointed. PyPy has just recently been becoming a fast attractive alternative to CPython (or Cython compilation). If they go the STM route and spend years hashing out the details only to be 2x as slow as CPython, then that cuts out a huge number of people who would like to practically use PyPy.
- Niedar 15y ago
  I think he might have meant 2x slower than without STM and not 2x slower than CPython. Also from everything I have read you would still have the option to not use STM at all and just use the GIL which would not come with the extra overhead.
- megaman821 15y ago
  I am pretty sure that is 2x slower than PyPy not CPython. So it would basically end up being over 2x faster than CPython.
- DasIch 15y ago
  How would this be ever an issue? You could simply compile PyPy without STM just as you can compile PyPy without the JIT or with a different GC.
alphaBetaGamma 15y ago
Would it be possible to only run the STM code when the program is multi-threaded? This would require the program detecting that it is single or multi threaded (would that be difficult?) and might provide a good trade off: either be single threaded and be fast, or use a lot of threads and be 2-10 times slower than Cython, but without the GIL.
albertzeyer 15y ago
Afaik, all builtin functions are considered to be atomic. Wouldn't it be enough to have a mutex for each object and when such a builtin function is called, all objects which are passed as parameters (including and esp. `self`) are locked?
- lobo_tuerto 15y ago
  Could that probably lead to performance issues?
- exDM69 15y ago
  No, that is not enough. If you want to implement atomicity for operations that touch multiple objects, a simple mutex-per-object approach just won't cut it. If you start holding multiple mutexes at once, there will be deadlocking if they are not locked in a consistent order. Not to mention that if every object has a mutex associated, the performance will be horrible. Even if the mutexes are not contended, there will be so many atomic compare and swap operations that the interprocessor memory bus will simply die. If your solution would work, every method in Java would be synchronized by default.
  - scott_s 15y ago
    I agree with your points on performance, but it's worth noting that they apply to STM as well: if you make the atomic regions too numerous and coarse grain, the compare-and-swap operations will kill performance.
- scott_s 15y ago
  That's essentially what Jython does. He discusses why he does not want to go in that direction in the article.
  - albertzeyer 15y ago
    He says that it would be much work and hard to do manually. But I think you can add such a behavior in an automatic way.
arohner 15y ago
Clojure's STM has several advantages going for it: * Clojure's data structures are purely functional, and built with the STM in mind. Updates and rollbacks to structures are cheap. * Clojure user-level code has always had access to the STM. Because that's the accepted paradigm, There are an order of magnitude fewer assignments in typical clojure code, greatly simplifying the problem. In typical clojure, one function that uses the STM will call 10 pure functions. In typical python, most of those 10 calls will all mutate local state. * Clojure requires all STM activity to happen within the dosync block. In python, that would be like requiring the magic to happen within a "with transaction(): ...". Again, this limits the amount of work that needs to happen. The compiler doesn't need to decide whether or not a random function needs to be a transaction; the user will tell the compiler. * Clojure's STM explicitly only works with functional code. This will likely cause fewer leaky abstractions going forward. PyPy will have to modify all existing data structure classes to work with the new STM, and they won't be able to fix all the library and user code out in the world. Good luck to them, but I suspect bolting STM into an existing language is much harder than designing it from scratch, similar to building in GC.
- exDM69 15y ago
  How does Clojure enforce that there are no side-effects in the transactional code? Is there a macro that "compiles" the transaction somehow? STM in Haskell is very natural, since Haskell already enforces pure code and side-effecting code. STM and STVar work pretty similarly to IO and IORef or ST and TVar.
  - stevelosh 15y ago
    How does Clojure enforce that there are no side-effects in the transactional code? Technically it doesn't. If you have a (println "foo") in a transaction it may be printed multiple times if the transaction gets retried. Clojure does give you an io! macro that you can wrap all your side effects in to manually provide that kind of protection. If you try to use io! inside a transaction you'll get an error at runtime. user=> (defn foo [n] (io! (println n)) n) #'user/foo user=> (defn bar [] (dosync (foo 10))) #'user/bar user=> (bar) java.lang.IllegalStateException: I/O in transaction (NO_SOURCE_FILE:0)
Hoff 15y ago
STM and locks have some interesting clean-up and (as is cited in the article) you really need for it not to crash and not to deadlock or go all priority-inverted on you. Message-passing, on the other hand, doesn't need particular locking and crashes are (somewhat) simpler to deal with. (And most any scheme I've encountered can deadlock, and will usually choose the most inopportune moment to demonstrate this capability.) There's an older blog post here http://enfranchisedmind.com/blog/posts/thoughts-on-parallelism/ http://enfranchisedmind.com/blog/posts/thoughts-on-paralleli... that's worth a read.
joeyespo 15y ago
Microsoft has been doing extensive research with STM, so their work might be worth looking at along the way. A working STM package (STM.NET) was actually shipped with VS2010, where you can type this: Atomic.Do(() => { /* atomic code */ }) Here's some channel 9 videos about their progress, which are in of themselves very interesting: http://channel9.msdn.com/Shows/Going+Deep/Software-Transactional-Memory-The-Current-State-of-the-Art http://channel9.msdn.com/Shows/Going+Deep/Software-Transacti... http://channel9.msdn.com/Blogs/Charles/STMNET-Who-What-Why http://channel9.msdn.com/Blogs/Charles/STMNET-Who-What-Why And here are some research papers published by Tim Harris and the old STM research blog: http://research.microsoft.com/en-us/um/people/tharris/ http://research.microsoft.com/en-us/um/people/tharris/ http://blogs.msdn.com/b/stmteam/archive/2010/05/12/stm-net-devlab-incubation-complete.aspx http://blogs.msdn.com/b/stmteam/archive/2010/05/12/stm-net-d... Fascinating stuff. I'm wary of having it be at the core of Python, but very interested to see where PyPy ends up.
- arethuza 15y ago
  They also have a file system that can enlist in transactions: http://en.wikipedia.org/wiki/Transactional_NTFS http://en.wikipedia.org/wiki/Transactional_NTFS
jerf 15y ago
This may work, this may not, but some nod to the fact that they've read things like http://queue.acm.org/detail.cfm?id=1454466 http://queue.acm.org/detail.cfm?id=1454466 (as linked by codevine before me) and have some plan to address the problems would be nice. So far, attempts to bodge STM on to an imperative language that wasn't built with it in mind has not merely been failure, but radical failure. Immense amount of effort by very smart people, followed by the total unusability and unsalvagability of the resulting code. The fact that only place it has been shown to work is basically Clojure and Haskell needs to be addressed; how are you going to address the apparent fundamental incompatibility between imperative languages and STM? And while you may be able to answer that at the VM level (very tiny transactions implemented between opcodes, basically), I would expect it is absolutely hopeless to allow users access to this. How are you going to address the endless-side-effect replay problem? (Hint: You aren't.) This is a kill-PyPy level of dangerous decision, and I think everyone on that team ought to demand a very good answer to that question before buying into this.
- scott_s 15y ago
  From a PyPy as a practical tool point of view, I agree. From a PyPy as a research project, I'm excited. I'm skeptical of STM as a synchronization solution as well, but I still want us to explore it. If their approach truly is novel, then maybe there's something there.
  - jerf 15y ago
    That's kind of what I mean, some evidence that they've got a novel approach would be nice, because so far the answer is basically "STM doesn't work in code with unrestricted side effects", and personally, I'm pretty satisfied with the amount of due diligence that has been done on that result. Research should build on existing results, not retry the same things over and over.
    - scott_s 15y ago
      My thinking was that most research with STM for imperative codes have used the library approach. Since they will have full control over generated code and how it interacts with the STM, they may have more opportunities to optimize.
bfrog 15y ago
Python will always fail to do any true shared memory concurrency in my mind, so why not go the other route, have concurrency with enforcement of no shared state and instead only allow message passing and selective receive. Thats all the rage these days anyways as its easier to reason about. Better still it matches distributed computing models much better.
aidenn0 15y ago
With this in mind, it is possible to imagine a whole- program transformation that would add locking on every object manipulated in RPython by the interpreter. This would end up in a situation similar to Jython. However, it would not automatically solve the issue of deadlocks, which is avoided in the case of Jython by careful manual placement of the locks. (In fact, being deadlock-free is a global program property that cannot be automatically ensured or verified; any change to Jython can in theory break this property, and thus introduce subtle deadlocks. The same applies to non-atomicity.) This is just not true. It is true for the general case, but not for this specific case. Remember the pithy solution to the dining philosophers (number all the chopsticks and pick up the lowest numbered one first)? I don't know the details of the pypy interpreter, but it does seem that given a byte-code that affects several objects, you could just acquire the locks for the objects as ordered by the objects address. Now the pypy guys are very smart and this is a simple solution, so I'm sure it yields horrible performance, but the fact of the matter is it's not true that "being deadlock-free is a global program property that cannot be automatically ensured" (it is true that it can't be verified, but if you generate all the locking code it can be ensured by strict ordering) and to say otherwise is wrong.
- scott_s 15y ago
  You missed this point: and moreover if you need to have accessed the first object before you can decide that you will need to access the second object That is, he's talking about situations where they don't have full knowledge when entering a critical section which objects will be accessed. Hence, they can't order lock acquisition in such a way to avoid deadlock.
  - aidenn0 15y ago
    I would be extremely surprised if this happened at the byte-code level.
    - regularfry 15y ago
      You should be able to determine the set of objects which might be touched by a section of bytecode such that they need locking. However, the majority of the time that set will vastly over-estimate the number of objects which actually get touched (the problem bytecodes here are, just from inspection, JUMP_IF_{TRUE,FALSE}, EXEC_STMT, IMPORT_STAR, BUILD_CLASS, {STORE,DELETE}_GLOBAL, probably a few more I can't be bothered to think through right now), and a lot of the time will simply be "all the objects in the system." Fundamentally, it doesn't make a difference whether you analyse the python or the bytecode; further, I'm not even sure that RPython is ever converted to bytecode, so it's not entirely relevant here.
albertzeyer 15y ago
After reading this, I thought a bit about other possible solutions. Esp. more like Jython is doing it but in an automatic way. I came up with this: https://github.com/albertz/automatic_object_locking https://github.com/albertz/automatic_object_locking
jamwt 15y ago
We are using Haskell + STM for scaling a major multicore system at Bump, and it's been exceedingly awesome thus far. However, STM happens to suit Haskell's type system-enforced purity particularly well; it's hard to see this being anything but a monumental undertaking in a language like Python.
surrealize 15y ago
There's a great, very detailed retrospective on Microsoft's STM implementation efforts here: http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetrospectiveOnTransactionalMemory.aspx http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetros...

135 points by j4mie 15y ago

STM sounds all nice, yet there are few implementations of STM currently that give better performance than a good serial implementation.

exDM69 15y ago
I hope you have sources and/or benchmarks to support your claims. Bashing a promising future technology without any backing is not constructive.
- wynand 15y ago
  codedivine has a point and it's even admitted in this posting: "we expect the initial performance to be abysmally bad (maybe 10x slower); however, with successive improvements to the locking mechanism, to the global program transformation inserting the locks, to the garbage collector (GC), and to the Just-in-Time (JIT) compiler, we believe that it should be possible to get a roughly reasonable performance (up to maybe 2x slower)." It will likely be difficult to beat expertly written code using explicit locks. But most people aren't experts in concurrency and will either get it wrong or have slow implementations. And if transactional memory catches on, we may even see some hardware assistance in future CPUs. (S)TM is definitely worth exploring more and even a 2x slower implementation (as envisioned by the PyPy team) could cover most concurrency needs, which will make it a success in most people's eyes.
  - kbd 15y ago
    Do they mean 2x slower than CPython or 2x slower than PyPy? If they wind up with something 2x slower than current PyPy (which is much faster than CPython in many cases), that'll still be a version of Python much faster than CPython that doesn't have the limitations of the GIL and can thread across cores, and that'll be a huge win.
- codedivine 15y ago
  One good read is: http://queue.acm.org/detail.cfm?id=1454466 http://queue.acm.org/detail.cfm?id=1454466 "Software Transactional Memory: Why Is It Only a Research Toy?" by Cascaval et al. I think transactional memory systems with at least some hardware support are potentially more interesting.
  - exDM69 15y ago
    Some of the problems addressed in the papar can be solved with compiler enforceable constraints such as is done in Haskell's type system. What comes to the performance, the benchmarks in the paper range from no speedup at all with 8 cores to having 1.5x perf increase with 2 cores to 4x increase with 8 cores. To me, that definately sounds like something worth researching.
    - scott_s 15y ago
      The point of that paper is that they have been researching it, quite extensively. But the performance results have often been disappointing, and the semantics of nested transactions can be surprisingly complex. At what point do you start looking into other things?
masklinn 15y ago
There's the same issue with normal locks: any synchronization primitive is going to incur overhead. That is, in fact, one of the defense heralded by some in the Python community against the "GIL should Go" mobthink.
- scott_s 15y ago
  I think you misunderstood codedivine. His point was not that applications that use STM and make use of a single thread are slower than sequential implementations of the same application. We expect the parallel implementation's single threaded performance to suffer by a percentage or two (or ten...) because it has to do more hardware-level atomic operations. codedivine's point was that it is often the case that applications implemented with STM that use multiple threads often perform worse than the sequential version. See the excellent ACM Queue article he links to in a sibling comment.
  - masklinn 15y ago
    > I think you misunderstood codedivine. His point was not that applications that use STM and make use of a single thread are slower than sequential implementations of the same application. And the experience has been exactly the same in locks-based GIL-removal tests in Python: David Beazley recently "unearthed" and tested a GIL-removal patch from the 1.4 days[0]... > To test threads, I wrote a small sample that subdivided the work across two worker threads is an embarrassingly parallel manner (note: this code is a little wonky due to the fact that Python-1.4 doesn't implement thread joining--meaning that you have to do it yourself with the included binary-semaphore lock). > [...] > If you run this code with the GIL, the execution time is about 2.5 seconds or approximately 1.3 times slower than the single-threaded version (1.9 seconds). Using the GIL-less Python, the execution time is 18.5 seconds or approximately 1.45 times slower than the single-threaded version (12.7 seconds). Just to emphasize, the GIL-less Python running with two-threads is running more than 7 times slower than the version with a GIL. [0] http://dabeaz.blogspot.com/2011/08/inside-look-at-gil-removal-patch-of.html http://dabeaz.blogspot.com/2011/08/inside-look-at-gil-remova...
    - 15y ago
cabacon 15y ago
Then again, hardware transactional memory may be arriving: http://www.eetimes.com/electronics-news/4218914/IBM-plants-transactional-memory-in-CPU http://www.eetimes.com/electronics-news/4218914/IBM-plants-t...
- pjscott 15y ago
  Note that it's currently limited to transactions will fairly small read and write sets, but this is not an inherent limitation of hardware transactional memory, and it can be used as part of a hardware/software hybrid system to accelerate small transactions. I'm pretty excited. The chip modifications here are really small and cheap, so I think we may start seeing this in more mainstream server chips in a few years.

chalst 15y ago

Does this proposal entail writing Python code without mutation of non-local state? Isn't this harder in Python than in Haskell or Ocaml?

masklinn 15y ago
> Does this proposal entail writing Python code without mutation of non-local state? Pypy using STM should not change the semantics of the Python language or require alterations to code which does not rely on implementation details (code which relies on the GIL for its thread-safety may have to be fixed, it already has to be fixed for Jython compatibility). > Isn't this harder in Python than in Haskell or Ocaml? I'd expect STM to be much harder in imperative languages than in functional languages indeed. In fact, I don't think I've heard of a successful STM implementation in imperative languages yet. On the other hand, I think most tentatives so far have been with STM as a library applied explicitly, and you run into issues of (mutable) objects "crossing" the transaction barrier in imperative languages, issue which "does not" happen in Haskell (there are ways to subvert the type system, but then you're on your own. In normal uses, I think objects under STM live in a different monad, and therefore can't be freely mixed with objects living outside of it) (I believe this issue would happen in OCaml, so on that front OCaml would be little better than imperative languages). This issue should not exist if all of the code runs under STM (ignoring explicit hooks to do so built into the system), and this should allow for "easy" implementation of explicit memory transactions as well (one of STM's promises is composability, so you should be able to compose multiple bytecode-transactions in a single explicit transaction).

wgren 15y ago

>if [a JVM thread] reads a field of an object, and another thread writes to the same field of the same object, then the program will see either the old value, or the new value, but not something else entirely Nitpick: unless the field in questions is a "long" or "double". In those cases the operation becomes two bytecodes and you can in fact see something else entirely if you are unlucky. At least it used to be like that.

palish 15y ago
On 32-bit platforms. On 64-bit, you won't. =)

deleted 15y ago

[deleted]

masklinn 15y ago
Have you considered reading the fine article? That issue is covered.

true_religion 15y ago

I'm a little disapointed. PyPy has just recently been becoming a fast attractive alternative to CPython (or Cython compilation). If they go the STM route and spend years hashing out the details only to be 2x as slow as CPython, then that cuts out a huge number of people who would like to practically use PyPy.

Niedar 15y ago
I think he might have meant 2x slower than without STM and not 2x slower than CPython. Also from everything I have read you would still have the option to not use STM at all and just use the GIL which would not come with the extra overhead.
megaman821 15y ago
I am pretty sure that is 2x slower than PyPy not CPython. So it would basically end up being over 2x faster than CPython.
DasIch 15y ago
How would this be ever an issue? You could simply compile PyPy without STM just as you can compile PyPy without the JIT or with a different GC.

alphaBetaGamma 15y ago

Would it be possible to only run the STM code when the program is multi-threaded? This would require the program detecting that it is single or multi threaded (would that be difficult?) and might provide a good trade off: either be single threaded and be fast, or use a lot of threads and be 2-10 times slower than Cython, but without the GIL.

albertzeyer 15y ago

Afaik, all builtin functions are considered to be atomic. Wouldn't it be enough to have a mutex for each object and when such a builtin function is called, all objects which are passed as parameters (including and esp. `self`) are locked?

lobo_tuerto 15y ago
Could that probably lead to performance issues?
exDM69 15y ago
No, that is not enough. If you want to implement atomicity for operations that touch multiple objects, a simple mutex-per-object approach just won't cut it. If you start holding multiple mutexes at once, there will be deadlocking if they are not locked in a consistent order. Not to mention that if every object has a mutex associated, the performance will be horrible. Even if the mutexes are not contended, there will be so many atomic compare and swap operations that the interprocessor memory bus will simply die. If your solution would work, every method in Java would be synchronized by default.
- scott_s 15y ago
  I agree with your points on performance, but it's worth noting that they apply to STM as well: if you make the atomic regions too numerous and coarse grain, the compare-and-swap operations will kill performance.
scott_s 15y ago
That's essentially what Jython does. He discusses why he does not want to go in that direction in the article.
- albertzeyer 15y ago
  He says that it would be much work and hard to do manually. But I think you can add such a behavior in an automatic way.

arohner 15y ago

Clojure's STM has several advantages going for it: * Clojure's data structures are purely functional, and built with the STM in mind. Updates and rollbacks to structures are cheap. * Clojure user-level code has always had access to the STM. Because that's the accepted paradigm, There are an order of magnitude fewer assignments in typical clojure code, greatly simplifying the problem. In typical clojure, one function that uses the STM will call 10 pure functions. In typical python, most of those 10 calls will all mutate local state. * Clojure requires all STM activity to happen within the dosync block. In python, that would be like requiring the magic to happen within a "with transaction(): ...". Again, this limits the amount of work that needs to happen. The compiler doesn't need to decide whether or not a random function needs to be a transaction; the user will tell the compiler. * Clojure's STM explicitly only works with functional code. This will likely cause fewer leaky abstractions going forward. PyPy will have to modify all existing data structure classes to work with the new STM, and they won't be able to fix all the library and user code out in the world. Good luck to them, but I suspect bolting STM into an existing language is much harder than designing it from scratch, similar to building in GC.

exDM69 15y ago
How does Clojure enforce that there are no side-effects in the transactional code? Is there a macro that "compiles" the transaction somehow? STM in Haskell is very natural, since Haskell already enforces pure code and side-effecting code. STM and STVar work pretty similarly to IO and IORef or ST and TVar.
- stevelosh 15y ago
  How does Clojure enforce that there are no side-effects in the transactional code? Technically it doesn't. If you have a (println "foo") in a transaction it may be printed multiple times if the transaction gets retried. Clojure does give you an io! macro that you can wrap all your side effects in to manually provide that kind of protection. If you try to use io! inside a transaction you'll get an error at runtime. user=> (defn foo [n] (io! (println n)) n) #'user/foo user=> (defn bar [] (dosync (foo 10))) #'user/bar user=> (bar) java.lang.IllegalStateException: I/O in transaction (NO_SOURCE_FILE:0)

Hoff 15y ago

STM and locks have some interesting clean-up and (as is cited in the article) you really need for it not to crash and not to deadlock or go all priority-inverted on you. Message-passing, on the other hand, doesn't need particular locking and crashes are (somewhat) simpler to deal with. (And most any scheme I've encountered can deadlock, and will usually choose the most inopportune moment to demonstrate this capability.) There's an older blog post here http://enfranchisedmind.com/blog/posts/thoughts-on-parallelism/ http://enfranchisedmind.com/blog/posts/thoughts-on-paralleli... that's worth a read.

joeyespo 15y ago

Microsoft has been doing extensive research with STM, so their work might be worth looking at along the way. A working STM package (STM.NET) was actually shipped with VS2010, where you can type this: Atomic.Do(() => { /* atomic code */ }) Here's some channel 9 videos about their progress, which are in of themselves very interesting: http://channel9.msdn.com/Shows/Going+Deep/Software-Transactional-Memory-The-Current-State-of-the-Art http://channel9.msdn.com/Shows/Going+Deep/Software-Transacti... http://channel9.msdn.com/Blogs/Charles/STMNET-Who-What-Why http://channel9.msdn.com/Blogs/Charles/STMNET-Who-What-Why And here are some research papers published by Tim Harris and the old STM research blog: http://research.microsoft.com/en-us/um/people/tharris/ http://research.microsoft.com/en-us/um/people/tharris/ http://blogs.msdn.com/b/stmteam/archive/2010/05/12/stm-net-devlab-incubation-complete.aspx http://blogs.msdn.com/b/stmteam/archive/2010/05/12/stm-net-d... Fascinating stuff. I'm wary of having it be at the core of Python, but very interested to see where PyPy ends up.

arethuza 15y ago
They also have a file system that can enlist in transactions: http://en.wikipedia.org/wiki/Transactional_NTFS http://en.wikipedia.org/wiki/Transactional_NTFS

jerf 15y ago

This may work, this may not, but some nod to the fact that they've read things like http://queue.acm.org/detail.cfm?id=1454466 http://queue.acm.org/detail.cfm?id=1454466 (as linked by codevine before me) and have some plan to address the problems would be nice. So far, attempts to bodge STM on to an imperative language that wasn't built with it in mind has not merely been failure, but radical failure. Immense amount of effort by very smart people, followed by the total unusability and unsalvagability of the resulting code. The fact that only place it has been shown to work is basically Clojure and Haskell needs to be addressed; how are you going to address the apparent fundamental incompatibility between imperative languages and STM? And while you may be able to answer that at the VM level (very tiny transactions implemented between opcodes, basically), I would expect it is absolutely hopeless to allow users access to this. How are you going to address the endless-side-effect replay problem? (Hint: You aren't.) This is a kill-PyPy level of dangerous decision, and I think everyone on that team ought to demand a very good answer to that question before buying into this.

scott_s 15y ago
From a PyPy as a practical tool point of view, I agree. From a PyPy as a research project, I'm excited. I'm skeptical of STM as a synchronization solution as well, but I still want us to explore it. If their approach truly is novel, then maybe there's something there.
- jerf 15y ago
  That's kind of what I mean, some evidence that they've got a novel approach would be nice, because so far the answer is basically "STM doesn't work in code with unrestricted side effects", and personally, I'm pretty satisfied with the amount of due diligence that has been done on that result. Research should build on existing results, not retry the same things over and over.
  - scott_s 15y ago
    My thinking was that most research with STM for imperative codes have used the library approach. Since they will have full control over generated code and how it interacts with the STM, they may have more opportunities to optimize.

bfrog 15y ago

Python will always fail to do any true shared memory concurrency in my mind, so why not go the other route, have concurrency with enforcement of no shared state and instead only allow message passing and selective receive. Thats all the rage these days anyways as its easier to reason about. Better still it matches distributed computing models much better.

aidenn0 15y ago

With this in mind, it is possible to imagine a whole- program transformation that would add locking on every object manipulated in RPython by the interpreter. This would end up in a situation similar to Jython. However, it would not automatically solve the issue of deadlocks, which is avoided in the case of Jython by careful manual placement of the locks. (In fact, being deadlock-free is a global program property that cannot be automatically ensured or verified; any change to Jython can in theory break this property, and thus introduce subtle deadlocks. The same applies to non-atomicity.) This is just not true. It is true for the general case, but not for this specific case. Remember the pithy solution to the dining philosophers (number all the chopsticks and pick up the lowest numbered one first)? I don't know the details of the pypy interpreter, but it does seem that given a byte-code that affects several objects, you could just acquire the locks for the objects as ordered by the objects address. Now the pypy guys are very smart and this is a simple solution, so I'm sure it yields horrible performance, but the fact of the matter is it's not true that "being deadlock-free is a global program property that cannot be automatically ensured" (it is true that it can't be verified, but if you generate all the locking code it can be ensured by strict ordering) and to say otherwise is wrong.

scott_s 15y ago
You missed this point: and moreover if you need to have accessed the first object before you can decide that you will need to access the second object That is, he's talking about situations where they don't have full knowledge when entering a critical section which objects will be accessed. Hence, they can't order lock acquisition in such a way to avoid deadlock.
- aidenn0 15y ago
  I would be extremely surprised if this happened at the byte-code level.
  - regularfry 15y ago
    You should be able to determine the set of objects which might be touched by a section of bytecode such that they need locking. However, the majority of the time that set will vastly over-estimate the number of objects which actually get touched (the problem bytecodes here are, just from inspection, JUMP_IF_{TRUE,FALSE}, EXEC_STMT, IMPORT_STAR, BUILD_CLASS, {STORE,DELETE}_GLOBAL, probably a few more I can't be bothered to think through right now), and a lot of the time will simply be "all the objects in the system." Fundamentally, it doesn't make a difference whether you analyse the python or the bytecode; further, I'm not even sure that RPython is ever converted to bytecode, so it's not entirely relevant here.

albertzeyer 15y ago

After reading this, I thought a bit about other possible solutions. Esp. more like Jython is doing it but in an automatic way. I came up with this: https://github.com/albertz/automatic_object_locking https://github.com/albertz/automatic_object_locking

jamwt 15y ago

We are using Haskell + STM for scaling a major multicore system at Bump, and it's been exceedingly awesome thus far. However, STM happens to suit Haskell's type system-enforced purity particularly well; it's hard to see this being anything but a monumental undertaking in a language like Python.

surrealize 15y ago

There's a great, very detailed retrospective on Microsoft's STM implementation efforts here: http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetrospectiveOnTransactionalMemory.aspx http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetros...