tag:blogger.com,1999:blog-3971202189709462152.post7225309560970774590..comments2024-03-11T12:50:02.036+01:00Comments on PyPy Status Blog: Transactional Memory (II)Carl Friedrich Bolz-Tereickhttp://www.blogger.com/profile/00518922641059511014noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3971202189709462152.post-15153890837721992992012-02-27T18:57:35.221+01:002012-02-27T18:57:35.221+01:00Speaking as someone maintaining a large applicatio...Speaking as someone maintaining a large application that uses Twisted, this sounds great.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-66165304544895756652012-02-01T21:39:56.083+01:002012-02-01T21:39:56.083+01:00A link to a group that did the same thing (thanks ...A link to a group that did the same thing (thanks a lot Andrew for this link!):<br /><br />http://research.microsoft.com/en-us/projects/ame/<br /><br />In particular the May 2007 paper (HotOS) nicely summarizes exactly what I'm trying to say, and I think it is clearer than me, if I have to jugde from feedback :-)Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-32311320412352681742012-02-01T19:59:32.540+01:002012-02-01T19:59:32.540+01:00@daniel@Armin, CSP may be built into Go, but IMO t...@daniel<i>@Armin, CSP may be built into Go, but IMO this was a mistake, there is no requirement for it to be a language feature; it fits nicer as library. See [python-csp] for a python library </i><br /><br />I have looked at Python-CSP a long time ago. I recall it being verbose. However I use Stackless Python. And using PyPy's stackless.py, I implemented select() and join patterns. Sometimes I wish I had language support: they cut down on silly mistakes and make the code less verbose for simple cases. However what I have found is that the language can get in the way. For instance, in Go, one has to come up with hacks to do some simple like do a select on an arbitrary number of channels. Perhaps I am wrong but I suspect stuff like select()'s design was influenced by the fact Newsqueak was originally designed to make a windowing system easier to write. So one is monitoring only a handful of channels. In constrast, this is not the way Stackless Python programmes are written.<br /><br />Cheers,<br />AndrewAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-74105586684068577822012-02-01T19:43:36.103+01:002012-02-01T19:43:36.103+01:00@armin: @Anonymous: in the extract you cite I mean...@armin: <i>@Anonymous: in the extract you cite I meant "the two main models in Python". As far as I can tell, Go does concurrency by enforcing all communications to go via channels, so I would classify it as a "special-made" language. This solution might be nice and usable, but it does not really work at all in languages like Python. </i><br /><br />Armin, Stackless Python uses a model that at the API level is very similar to Go. Go borrows from the Bell Labs family of languages (i.e. Newsqueak). The fundamental idea is that message pasing is used to share information between threads/processes/coroutines. In this regard, Go is in the same camp as say, Erlang (although the messaging systems are different).<br /><br /><br />What I think is interesting and workable for Python are efforts in languages like Polyphonic C# (see the paper "Scalable Join Patterns") and Concurrent/Parallel ML, where lock-free libraries and STM techniques are used under the hood to improve the efficiency of the messaging/synchronisation system. In this fashion, the programmer has a conceptually clean concurrency model and still can make the important decisions about how to partition the problem. <br /><br />Cheers,<br />AndrewAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-55579670659747000002012-01-31T18:13:36.789+01:002012-01-31T18:13:36.789+01:00@Gary Robinson: (off-topic:) for this kind of use ...@Gary Robinson: (off-topic:) for this kind of use case, you can use os.fork() after the immutable data is ready. It "kind of works" both in pypy and in cpython, although not really --- in cpython the reference counts are modified, causing the pages to get unshared between processes; and in pypy the garbage collector (GC) has the same effect, so far. It could be solved in pypy by more tweaks the GC.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-57045347794731037752012-01-24T11:03:51.876+01:002012-01-24T11:03:51.876+01:00@Charles: Indeed, I am suggesting VM-wide STM, wit...@Charles: Indeed, I am suggesting VM-wide STM, with the resulting transactional overhead for every read and write. I actually got such a VM yesterday (with no GC): it seems to be about 10x slower on a single thread.<br /><br />Note that even 10x slower is a plus if it scales to dozens of processors. But of course, a better point of view is that some years ago the regular pypy *was* 10x slower than CPython. It was a lot of efforts but we managed to make it only 1.5-2x slower. And this is all without counting the JIT. If STM bogs down to a generally-not-triggered read barrier before every read, then the performance impact could be well under 2x.<br /><br />Please note also that I don't care about Java-like performance where even loosing 10% of performance would be a disaster. If we end up with a pypy-tm that is 2x slower than a regular pypy, I would be quite happy, and I believe that there is a non-negligible fraction of the Python users that would be, too.<br /><br />On granularity: for now I'm going with the idea that the granularity is defined "naturally" in the source program as the amount of work done every time some central dispatch loop calls some code. There might be several dispatch loops in total, too. This is true in the cases I can think of: typical Twisted or Stackless programs, pypy's "translate.py", the richards benchmark, etc.<br /><br />Please look at http://paste.pocoo.org/show/539822/ for an example of what I'm talking about. It's a diff against the standard <a href="https://bitbucket.org/pypy/pypy/raw/default/pypy/translator/goal/richards.py" rel="nofollow">richards.py</a>: it is a pure Python user program in which I added calls to the new 'transaction' module. At this level there is no hint of Transactional Memory.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-11451044528332602662012-01-24T05:22:00.884+01:002012-01-24T05:22:00.884+01:00The devil's in the details.
I'm not sure ...The devil's in the details.<br /><br />I'm not sure I buy your conclusions here. STM is not a panacea for solving concurrency issues, and it has some key limitations that limit its general applicability.<br /><br />On what granularity do you plan to have transactions? How do you know? Perhaps the VM will have enough knowledge of a given thread's activities to limit transactional overhead to only those structures in memory that are shared, but there still needs to be some indirection in case another thread hops in and starts making changes.<br /><br />Where do transactions start and end? In STMs I know, the in-transaction overhead for reading and writing data is *much* higher, since it needs to know if someone else has committed a transaction first and be able to roll back.<br /><br />Perhaps this is all intended to be hidden, and you never actually have "threads" that the user can see. But if you're going to parallelize, you'll have threads *somewhere* that are going to contend for resources. If they're going to contend for resources, even in an STM, they're going to have to check for contention, register their interest, and then you're back to the indirection overhead.<br /><br />Perhaps I'm not understand what your end goal is. You can't simply turn the world into a series of transactions unless you want every read and write to have transaction overhead or you have some clear way of limiting transaction overhead to only where it's needed. You cite Erlang...but Erlang deals with immutable objects, and there's far less need for anything like an STM. Others have mentioned Clojure...but again, Clojure is mostly immutable structures, and transactional overhead is limited to Refs, where you'll make single coarse-grained reads and writes.<br /><br />Am I missing the point? Are you not suggesting VM-wide STM, with the resulting transactional overhead for every read and write?headiushttps://www.blogger.com/profile/15717357218364947795noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-34848910710691353592012-01-18T11:06:01.492+01:002012-01-18T11:06:01.492+01:00I also see no reason for Thread local memory.
I l...I also see no reason for Thread local memory.<br /><br />I like the idea of thinking about TM in the same line as GC. When you have GC the changes to the language is that you don't need to write free/dealloc. <br /><br />Having TM would mean that you don't have to write acquire_GILAnonymoushttps://www.blogger.com/profile/13558027109535076027noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-24874601857365016772012-01-16T13:55:58.961+01:002012-01-16T13:55:58.961+01:00@notme: yes, a web server or anything can use this...@notme: yes, a web server or anything can use this instead of using threads. It's of course missing a convincing select() or poll() version for that.<br /><br />The details haven't been thought out; right now an exception interrupts everything. In an STM model it's unclear if concurrent transactions should still be allowed to complete or not. Anyway the point is that exceptions should not really occur because precisely they interrupt everything --- you would typically add instead in every transaction code like "try: .. except: traceback.print_exc()".<br /><br />Thread local storage: what would be the point?Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-41226177878963980352012-01-16T13:11:41.330+01:002012-01-16T13:11:41.330+01:00@Armin: That transaction code looks very simple. ...@Armin: That transaction code looks very simple. It seems trivial to implement a map/mapReduce style function on top of your transaction module.<br /><br />It is a very similar API to worker pool APIs which many thread using programs use. The main difference is that you combine the join() in the run method. It seems that a threaded web server for example could use this? What would happen if each incoming request comes in, and is put into the transaction (and say the 10th request has an error)? Would it be better to use multiple transactions?<br /><br />Have you thought how thread local storage would work?René Dudfieldhttps://www.blogger.com/profile/17762358075557755436noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-64286864350327529392012-01-16T11:08:46.467+01:002012-01-16T11:08:46.467+01:00Update: please look at the tiny transaction module...Update: please look at the tiny transaction module I wrote as an example. The idea is to have the same interface as this module, but implemented differently. By making use of transactional memory internally, it should be possible to safely run on multiple CPUs while keeping the very same programmer interface.<br /><br />https://bitbucket.org/arigo/arigo/raw/default/hack/stm/transactionmodule/Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-19307698905667574862012-01-15T09:56:39.633+01:002012-01-15T09:56:39.633+01:00When Armin gets this excited I'd fasten my sea...When Armin gets this excited I'd fasten my seatbelt and put my goggles on.<br /><br />Thank you for letting me be an (otherwise mostly silent) observer.<br /><br />Please keep shifting boundaries!<br /><br />- EricEric van Riet Paaphttps://www.blogger.com/profile/04007960162946588987noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-14849279103385536712012-01-15T09:03:05.617+01:002012-01-15T09:03:05.617+01:00Your idea could work for other easy to inject into...Your idea could work for other easy to inject into points, such as loops, and comprehensions. Especially with much of the work in pypy already done for identifying information about loops.<br /><br />How does this compare to grand central dispatch and blocks? http://en.wikipedia.org/wiki/Grand_Central_Dispatch<br /><br />Events are a very good way to model concurrency, and are widely used. It is a great place to dispatch concurrency into parallelism.<br /><br />Closures/blocks provide a fairly decent way to get some of the protection of STM - and in many programs give you the 80% solution. For code that plays nicely and avoids mutable, or global data - this works. Luckily, a lot of event based code is already written in this way. As you say, they are "generally mostly independent".<br /><br />Making the bad cases a quick fail, like in JavaScript worker threads could be an ok option. As soon as someone tries to access global data(do a system call, access the DOM, or access data outside the closure even), the program would fail there. Then you could fix those cases, or "add non-determinism" as you say. I think I'd prefer fail fast here, rather than have to detect these problems, and have them silently pass by.<br /><br />You still have scheduling problems, and trying to figure out task size. As well, this does not solve lots of other problems. However, it is cool that it could be applied automatically, and probably 'safely'.<br /><br />Another random thought... you could probably mark chunks of code as 'pure' as your run through them, and if they do a system call or mutate global data mark them as 'unpure' and don't try them again.<br /><br />I very much look forward to reading your results as you implement more.René Dudfieldhttps://www.blogger.com/profile/17762358075557755436noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-17072003391428449392012-01-15T08:24:40.099+01:002012-01-15T08:24:40.099+01:00> @Armin, CSP may be built into Go, but IMO thi...> @Armin, CSP may be built into Go, but IMO this was a mistake, there is no requirement for it to be a language feature; it fits nicer as library. See [python-csp] for a python implementation.<br /><br />Stackless (which PyPy enables) supports Go-style channels as well, no?<br /><br />http://www.stackless.com/wiki/ChannelsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-4726262445811895892012-01-14T22:45:56.137+01:002012-01-14T22:45:56.137+01:00The link to the previous blog post is broken. It s...The link to the previous blog post is broken. It should be: http://morepypy.blogspot.com/2011/06/global-interpreter-lock-or-how-to-kill.htmlSimon Weberhttp://plus.google.com/103350848301234480355noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-68454728247067394102012-01-14T22:11:38.768+01:002012-01-14T22:11:38.768+01:00@gasche: I know about Haskell, Clojure and Scala, ...@gasche: I know about Haskell, Clojure and Scala, and I just read the two blog posts you pointed to.<br /><br />I'm not talking about giving explicit TM to the end programmers. I'm instead considering TM as an internal, implementation-only feature. That makes it very similar to GCs.<br /><br />I know the points and issues of traditional TM systems, which are nicely reported by Joe Duffy in "A (brief) retrospective on transactional memory". These are of course perfectly valid issues, but I think they do not apply (or "not that much") in the particular context I'm talking about. For example, this includes the large sections about nested transactions, and about consistency between the transactional and non-transactional worlds (Weak or Strong Atomicity, The Privatization Problem). Even "Where is the Killer App?" is obvious in this case: any existing Twisted App is potentially a Killer App.<br /><br />Sorry for not including references to papers. I must admit I don't know any paper that describes a similar use case for TM.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-23827848340884494172012-01-14T21:27:36.388+01:002012-01-14T21:27:36.388+01:00@Armin, CSP may be built into Go, but IMO this was...@Armin, CSP may be built into Go, but IMO this was a mistake, there is no requirement for it to be a language feature; it fits nicer as library. See [python-csp] for a python implementation.<br /><br />[python-csp] http://code.google.com/p/python-csp/wiki/TutorialDaniel Waterworthhttps://www.blogger.com/profile/04591470870683677596noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-50892211392410700342012-01-14T20:27:27.451+01:002012-01-14T20:27:27.451+01:00@Anonymous: in the extract you cite I meant "...@Anonymous: in the extract you cite I meant "the two main models in Python". As far as I can tell, Go does concurrency by enforcing all communications to go via channels, so I would classify it as a "special-made" language. This solution might be nice and usable, but it does not really work at all in languages like Python.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-81523312986769611602012-01-14T17:57:36.111+01:002012-01-14T17:57:36.111+01:00One major use-case for multithreading involves a l...One major use-case for multithreading involves a large, unchanging data structure which many threads access. I.e., the data structure is loaded by a parent task, then not modified again; a number of threads are then spawned to use it for calculations.<br /><br />In CPython, the GIL makes this impossible if only because the reference counters need to be protected. With Cython in threads, however, you can turn off the GIL and do some work on C-style data structures.<br /><br />I'm wondering whether the STM PyPy effort could have a very useful, and very early, benefit: simply enabling an unchanging data structure to be accessed by a number of processors via the kinds of events you describe. There wouldn't be a need for transactions, because the programmer would take responsibility for only sharing unchanging structures between simultaneously-executing events. <br /><br />But it seems like the basic requirements for this kind of facility might be met in in early stage of STM development. And a solution that allowed multiple processors to access large, unchanging structures would be very useful in certain applications. I know I have one in mind that I'm looking at CPython/Cython for, but I'd rather see if I could get the performance I need from PyPy.<br /><br />Just thought it was worth mentioning.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-60887529325827396802012-01-14T17:50:26.747+01:002012-01-14T17:50:26.747+01:00If you go that road, you will certainly find out t...If you go that road, you will certainly find out that Transactional Memory is much, much harder to get right than it looks like in today effectful/imperative languages. Sure, it looks wonderful on paper, but if your language doesn't help you control side-effects it will give you a very hard time.<br /><br />Currently, there is satisfying STM support <a href="http://www.haskell.org/haskellwiki/Software_transactional_memory" rel="nofollow">in Haskell</a> (because of its tight type-based control of side-effects) <a href="http://clojure.org/refs" rel="nofollow">and Clojure</a> (beacuse of its tight control on mutability), and it might be getting <a href="http://nbronson.github.com/scala-stm/index.html" rel="nofollow">into Scala</a>.<br /><br />I doubt Python can easily get such control, at least without an important reorganization of idiomatic practices and frameworks, that go beyond the "let's be event-driven" decision. Which makes your "this is going to work magically" story a bit hard to believe.<br /><br />There has been intense research on this topic for some decades now, and several attempts at getting it to work in current mainstream languages have mostly failed.<br /><br />See for example this long retrospective of the STM.NET effort at Microsoft Research, by Joe Duffy:<br /> <a href="http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetrospectiveOnTransactionalMemory.aspx" rel="nofollow">A (brief) retrospective on transactional memory</a><br />or this shorter blog post by Brian Hurt:<br /> <a href="http://enfranchisedmind.com/blog/posts/the-problem-with-stm-your-languages-still-suck/" rel="nofollow">The problem with STM: your languages still suck</a>.<br /><br />I was a bit disappointed that you didn't cite any of the relevant literature in your post. It made me suspicious of "reiventing the wheel"...gaschenoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-14772863921933437172012-01-14T16:38:43.283+01:002012-01-14T16:38:43.283+01:00> These two models --- threads or events --- ar...> These two models --- threads or events --- are the two main models we have right now.<br /><br />Where does Go-style concurrency fit in?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-13189867618626936002012-01-14T16:17:02.952+01:002012-01-14T16:17:02.952+01:00Great article, great solution to a big problem...
...Great article, great solution to a big problem...<br /><br />I am really looking forward to this :-) <br /><br />As an experiment I have developed Pyworks, which makes objects concurrent and methods asynchronious. But it makes little sense to do performance test on an multicore CPU because of the GIL.<br /><br />The code for Pyworks can be found at https://bitbucket.org/raindog/pyworksAnonymoushttps://www.blogger.com/profile/13558027109535076027noreply@blogger.com