Oh, I can't yet use alternative gc that obviates GIL then? Or am I totally confused and pypy still uses GIL for other reasons, e.g. globals dict safety? On 22 December 2010 19:49, Benjamin Peterson wrote:

2010/12/22 Dima Tisnek :

...

Hi,

Somehow I'm getting exactly same performance in threaded and non-threaded code (I would expect at least some speedup), Is threading not there in this pypy release in practice or am I missing some argument to pypy?

PyPy has a GIL if that's what you mean.

-- Regards, Benjamin

On Wed, Dec 22, 2010 at 7:05 PM, Benjamin Peterson wrote:

2010/12/22 Dima Tisnek :

...

Oh, I can't yet use alternative gc that obviates GIL then?

Or am I totally confused and pypy still uses GIL for other reasons, e.g. globals dict safety?

All of the above.

On the topic of parallel dict safety... I've not played around with parallel dictionaries at all, but I've heard that treaps can be parallelized nicely, and they can be (and have been) set up to look much like a python dictionary. I admit, I coded one and put it at http://stromberg.dnsalias.org/~strombrg/treap/ - however, the implementation is not (yet?) suitable for parallel use. It's coded in such a way that it'll work as pure python or cython, depending on which of two m4 symbols you define. I've used the pure python version on pypy. Treaps tend to make just about everything O(log(n)), have good average performance, and are not as even performers as red-black trees (that is, they give a higher standard deviation, and a better average performance than red-black trees). And they don't play that nicely with locality of reference (caches) - things are intentionally randomized. But if you throw enough cores at them, they might still be a win compared to a big hash table with a big lock wrapped around it.

(dan) random binary trees: O(log2(n)) is 7.2 for builtins, though the constant factor for locks, etc, might make it worthwhile (paolo) non blocking hash maps: memory barriers can be quite costly too different options will have to be implemented and tested when we get there, speaking on which, is there a test dict load? does anyone have some profiling data, what portion of runtime is spent reading and writing attributes and globals anyways? while we are on the subject, is there a plan to provide different levels of sparseness for different levels of name lookup? for example globals vs builtins, first needs to be quite sparce so that builtins show through well, second hardly, because there's nowhere else to look if builtins don't have the name. then the tradeoff could be more dynamic, that is frequently accessed dicts could be e.g. more sparse and rarely accessed more compact? (obviousely more sparse is not always better, e.g. in terms of cpu cache) of course "frequently accessed" is not as easy as frequently ran code, e.g. here "class A: ...; while 1: A().func()", func lookup occurs in different objects, yet it is same logical operation. come to think of it, is there any point in polymorphic dicts, e.g. attribute access could be imeplemented as a near-perfect compact hash map if attribute names change rarely, while regular dict()s are expected to change keys often. Anyhow, back to parallel interpretation, Is there an issue or page that tracks what's needed for parallel interpretation? so far mentioned: gc, dict, c api Btw, I think that jit is more important at the moment, but time comes when jit juice has been mostly squeezed out ;-) d. On 23 December 2010 07:31, Paolo Giarrusso wrote:

On Thu, Dec 23, 2010 at 06:58, Dan Stromberg wrote:

...

On Wed, Dec 22, 2010 at 7:05 PM, Benjamin Peterson wrote:

...

2010/12/22 Dima Tisnek :

...

Oh, I can't yet use alternative gc that obviates GIL then?

Or am I totally confused and pypy still uses GIL for other reasons, e.g. globals dict safety?

All of the above.

On the topic of parallel dict safety...  I've not played around with parallel dictionaries at all, but I've heard that treaps can be parallelized nicely, and they can be (and have been) set up to look much like a python dictionary.  I admit, I coded one and put it at http://stromberg.dnsalias.org/~strombrg/treap/ - however, the implementation is not (yet?) suitable for parallel use.

It's coded in such a way that it'll work as pure python or cython, depending on which of two m4 symbols you define.  I've used the pure python version on pypy.

Treaps tend to make just about everything O(log(n)), have good average performance, and are not as even performers as red-black trees (that is, they give a higher standard deviation, and a better average performance than red-black trees).  And they don't play that nicely with locality of reference (caches) - things are intentionally randomized.  But if you throw enough cores at them, they might still be a win compared to a big hash table with a big lock wrapped around it.

That might be interesting; however, the state of the art includes many concurrent hash map alternatives which are way smarter than "a lock wrapped around". Java >=1.5 has one, by Doug Lea*. An even better (and more complex) one, by Cliff Click*, used in production on >500 cores, and presented to JavaOne, can be found by googling:

nonblockinghashmap Cliff Click

A C implementation can be found at: http://code.google.com/p/nbds/

Link found through this blog post of Cliff Click: http://www.azulsystems.com/blog/cliff-click/2008-11-13-some-source-forge-thr...

However, I don't think you can code them in nowadays Python, because it offers neither a Java-equivalent volatile attribute nor compare-and-swap nor memory barriers, and these structures can't be implemented with plain locks.

Best regards

* Doug Lea wrote the memory allocator used on Linux, is behind the 1.5 java.util.concurrent package, and much more. Cliff Click is a high-performance JVM hacker. -- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/ _______________________________________________ pypy-dev@codespeak.net http://codespeak.net/mailman/listinfo/pypy-dev

On 12/27/2010 07:00 AM, Dima Tisnek wrote:

(dan) random binary trees: O(log2(n)) is 7.2 for builtins, though the constant factor for locks, etc, might make it worthwhile

(paolo) non blocking hash maps: memory barriers can be quite costly too

different options will have to be implemented and tested when we get there, speaking on which, is there a test dict load? does anyone have some profiling data, what portion of runtime is spent reading and writing attributes and globals anyways?

while we are on the subject, is there a plan to provide different levels of sparseness for different levels of name lookup? for example globals vs builtins, first needs to be quite sparce so that builtins show through well, second hardly, because there's nowhere else to look if builtins don't have the name. then the tradeoff could be more dynamic, that is frequently accessed dicts could be e.g. more sparse and rarely accessed more compact? (obviousely more sparse is not always better, e.g. in terms of cpu cache) of course "frequently accessed" is not as easy as frequently ran code, e.g. here "class A: ...; while 1: A().func()", func lookup occurs in different objects, yet it is same logical operation.

come to think of it, is there any point in polymorphic dicts, e.g. attribute access could be imeplemented as a near-perfect compact hash map if attribute names change rarely, while regular dict()s are expected to change keys often.

All these thoughts go into the wrong direction, imo. The JIT removes nearly all dictionary accesses to global dicts, instance and class dicts. Even without the JIT, purely interpreting things, there are caches that bypass most dict lookups. The only case where improving dicts would help is for user-defined dictionaries, i.e. when you write dicts with curly braces. that is basically very hard, because the usage patterns vary widely and a lot of work would be necessary to find common uses. Cheers, Carl Friedrich

On Mon, Dec 27, 2010 at 09:31, Carl Friedrich Bolz wrote:

On 12/27/2010 07:00 AM, Dima Tisnek wrote:

...

(dan) random binary trees: O(log2(n)) is 7.2 for builtins, though the constant factor for locks, etc, might make it worthwhile

(paolo) non blocking hash maps: memory barriers can be quite costly too

different options will have to be implemented and tested when we get there, speaking on which, is there a test dict load? does anyone have some profiling data, what portion of runtime is spent reading and writing attributes and globals anyways?

while we are on the subject, is there a plan to provide different levels of sparseness for different levels of name lookup? for example globals vs builtins, first needs to be quite sparce so that builtins show through well, second hardly, because there's nowhere else to look if builtins don't have the name. then the tradeoff could be more dynamic, that is frequently accessed dicts could be e.g. more sparse and rarely accessed more compact? (obviousely more sparse is not always better, e.g. in terms of cpu cache) of course "frequently accessed" is not as easy as frequently ran code, e.g. here "class A: ...; while 1: A().func()", func lookup occurs in different objects, yet it is same logical operation.

come to think of it, is there any point in polymorphic dicts, e.g. attribute access could be imeplemented as a near-perfect compact hash map if attribute names change rarely, while regular dict()s are expected to change keys often.

All these thoughts go into the wrong direction, imo. The JIT removes nearly all dictionary accesses to global dicts, instance and class dicts. Even without the JIT, purely interpreting things, there are caches that bypass most dict lookups.

That's very interesting. However, aren't such caches also hash maps in the end (unless you do inline caching in your interpreter, like in Ruby 1.9)? I remember reading so in PyPy's docs; moreover, that's a standard optimization for method lookup. Sharing such caches between different interpreter threads would be potentially useful, if that implied no expensive synchronization for readers - which is possible for instance on x86 (read barriers are for free), by using persistent data structures. Writes to such caches should (hopefully) be rare enough to make the extra synchronization not too expensive, however this needs benchmarking. Best regards -- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/

On Mon, Dec 27, 2010 at 07:00, Dima Tisnek wrote:

(dan) random binary trees: O(log2(n)) is 7.2 for builtins, though the constant factor for locks, etc, might make it worthwhile

"7.2"? What is that? Do you mean 7.2=log2(no. of builtins)?

(paolo) non blocking hash maps: memory barriers can be quite costly too

Well, you just _cannot_ avoid them, whatever is your fancy data structure. You can only move most of the cost (or all of it) to write operations - which is helpful if reads are most common, a case which you discuss in your mail. == Why memory barriers are required (in more detail) == If you use persistent data structures, also called copy-on-write or purely functional (and that's the most obvious way to use a tree in a parallel setting), the whole synchronization problem is reduced to exchanging a pointer (to the root of the tree) between a writer and a reader thread. Let's consider this in the Java memory model (the state of the art). In this model the writer thread has to use an expensive StoreLoad barrier, i.e. mfence on x86 [1], costing more or less as much as a cache miss, while the reader needs just a cheap Load* barrier (for free on x86, cheap on other processor). If you don't use a volatile field, there is very little guarantee about what your program means, and it is almost always buggy; the equivalent in the new C++ memory model (which is otherwise very similar) gives completely undefined semantics (and even crashes are possible in practice, for instance if the reader thread sees a not-fully-initialized object because of the race and invokes a virtual method on it). [1] http://g.oswego.edu/dl/jmm/cookbook.html == Other stuff ==

different options will have to be implemented and tested when we get there, speaking on which, is there a test dict load? does anyone have some profiling data, what portion of runtime is spent reading and writing attributes and globals anyways?

I'd be interested as well in such data.

Anyhow, back to parallel interpretation, Is there an issue or page that tracks what's needed for parallel interpretation? so far  mentioned: gc, dict, c api

Btw, I think that jit is more important at the moment, but time comes when jit juice has been mostly squeezed out ;-)

-- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/

On Mon, Dec 27, 2010 at 19:54, Dima Tisnek wrote:

what do you think of liburcu? lttng.org/urcu

I've studied RCU in the Linux kernel (from which URCU derives) and thought for a long time of using it for this problem. In short, once you have GC, RCU (as in the Linux kernel) becomes (almost) trivial, because RCU is almost entirely about how to delay freeing objects. The RCU-GC connection is also mentioned by Documentation/RCU/RTFP.txt in the Linux sources. So, you need to just read about persistent data structures, and remember that persistence is not the point - data structures which are just almost persistent can also be OK, if you get them right. If you replace a value in a dictionary, for instance, you don't necessarily need to keep the old version around, as long as you the value fits in a memory word so that it can be atomically replaced. http://hackerboss.com/copy-on-write-101-part-2-putting-it-to-use/ Speaking of libraries, you might want to look at this for the atomic primitives you'll need: www.hpl.hp.com/research/linux/atomic_ops/ I'm more used to the primitives of the Linux kernel, I remember I didn't fully like that library, but IIRC it was a matter of taste - the library is from Hans Boehm, which makes it trustworthy.

p.s. if/when I get around to profiling pypy, which is something I want to do, I'll be sure to share the results here.

Great, thanks!

d.

On 27 December 2010 10:57, Paolo Giarrusso wrote:

...

On Mon, Dec 27, 2010 at 07:00, Dima Tisnek wrote:

...

(dan) random binary trees: O(log2(n)) is 7.2 for builtins, though the constant factor for locks, etc, might make it worthwhile

"7.2"? What is that? Do you mean 7.2=log2(no. of builtins)?

...

(paolo) non blocking hash maps: memory barriers can be quite costly too

Well, you just _cannot_ avoid them, whatever is your fancy data structure. You can only move most of the cost (or all of it) to write operations - which is helpful if reads are most common, a case which you discuss in your mail.

== Why memory barriers are required (in more detail) == If you use persistent data structures, also called copy-on-write or purely functional (and that's the most obvious way to use a tree in a parallel setting), the whole synchronization problem is reduced to exchanging a pointer (to the root of the tree) between a writer and a reader thread. Let's consider this in the Java memory model (the state of the art). In this model the writer thread has to use an expensive StoreLoad barrier, i.e. mfence on x86 [1], costing more or less as much as a cache miss, while the reader needs just a cheap Load* barrier (for free on x86, cheap on other processor). If you don't use a volatile field, there is very little guarantee about what your program means, and it is almost always buggy; the equivalent in the new C++ memory model (which is otherwise very similar) gives completely undefined semantics (and even crashes are possible in practice, for instance if the reader thread sees a not-fully-initialized object because of the race and invokes a virtual method on it).

[1] http://g.oswego.edu/dl/jmm/cookbook.html

== Other stuff ==

...

different options will have to be implemented and tested when we get there, speaking on which, is there a test dict load? does anyone have some profiling data, what portion of runtime is spent reading and writing attributes and globals anyways?

I'd be interested as well in such data.

...

Anyhow, back to parallel interpretation, Is there an issue or page that tracks what's needed for parallel interpretation? so far  mentioned: gc, dict, c api

...

Btw, I think that jit is more important at the moment, but time comes when jit juice has been mostly squeezed out ;-)

-- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/

-- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/

On Tue, Dec 28, 2010 at 02:47, Dima Tisnek wrote:

Thanks for the RTFP pointer, the Triplett ref, hash tab via rt is really interesting!

I think I'll have to read it again and again to get all out of it...

Ah, I remember that! Never found enough time to read up that... also I remember that I didn't like it, at the time, because it seemed to give a new name to existing design practice in the RCU community. I didn't realize that even if the article just described existing work, the generalization alone might be an important contribution.

This brings me to a new question: how much is pypy python memory model allowed to diverge from that of cpython?

In fact, Jython and IronPython already have different memory models: code.google.com/p/unladen-swallow/wiki/MemoryModel But the most important answer is that to avoid reinventing the wheel, one needs to know the state of the art, i.e. the work by Sarita Adve, Jeremy Manson, William Pugh and Hans Boehm on memory models for Java and C++. The simplest introduction I know of comes in this blog post by Jeremy Manson: http://jeremymanson.blogspot.com/2008/11/what-volatile-means-in-java.html As a matter of fact, this work is unsurprisingly often totally ignored in many discussions about Python's memory model. I'm not surprised because it's complex stuff, and understanding it doesn't matter for today's Python programming. The key concept of these models is that _properly synchronized_ programs get "sequential consistent" semantics: the programs behaves as if all memory operations were interleaved in a total order on a single coherent memory, without reorderings due to cache, compiler optimizations and so on. Sequential consistency is the key property of what you call "GIL-based monotonic world". Exactly as you suggested for dictionaries, but more in general, programs which are not properly synchronized (which exhibit so-called data races) are more-or-less left on their own. On this topic, the Java and C++ models are different, and that leaves a design space open, but one which is already somewhat smaller, and which doesn't affect the semantics of properly synchronized programs. Java tries to define the semantics of data races, C++ just gives up. * Unlike C++ and like Java, it is probably important to guarantee that programs with data races (not properly synchronized memory accesses) don't crash the interpreter or corrupt native memory. You don't want native code in the interpreter to crash or to loop if the programmer forgets synchronization - simply because that's very difficult to debug, short of running a debugger on the interpreter itself (or fixing the code without a debugger at all). It is not clear, though, if one should give specific semantics to programs with data races, other than ensure the interpreter doesn't crash: basically it looks too complex. For whoever understands the rest of the Java Memory Model, this blog post explains the semantics they use to model this. http://jeremymanson.blogspot.com/2007/08/causality-and-java-memory-model.htm... * Another difference between Java and C++ is about security guarantees: it is crucial in Java that untrusted code cannot read sensitive data (e.g., a password) managed by trusted code, not even through a data race. Some kinds of behavior would allow "out-of-thin-air values", which in practice might be such sensitive data, if memory is zeroed by the memory allocator but one thread still sees the old value. I believe the most up-to-date introduction, with a useful bibliography, is by S. Adve and H. Boehm [1]. Then you will probably want to read [2] and [3] about C++ and Java. Through Google Scholar, you should find you copies of all of this on CiteseerX. [1] Sarita V. Adve and Hans-J. Boehm. 2010. Memory models: a case for rethinking parallel languages and hardware. Communications of the ACM. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.4288 [2] Hans-J. Boehm and Sarita V. Adve. 2008. Foundations of the C++ concurrency memory model. PLDI '08 [3] Jeremy Manson, William Pugh, and Sarita V. Adve. 2005. The Java memory model. POPL '05.

For example, dict lookups, etc, could be relativistic in the absense of explicit synchronization, that is, dict updates are not quaranteed to propagate [fast] until [some] therad acquires a lock [or something].

Talking about dictionaries restricts the scope unnecessarily. You want to relax these requirement for memory operations in general.

Would this be a worthwhile departure from GIL-based monotonic world?

Years of research agree the answer is yes, no doubt. Otherwise several fundamental optimizations become impossible - including the usage of memory caches. To make a simple example, releasing a lock requires flushing pending writes (i.e. a cache miss, ~100 cycles nowadays). Implementing sequential consistency (what you term "monotonic world") means doing that after _each_ memory write. If you read Adve et Boehm [1], they'll elaborate more on the topic.

That is thread-safe code, that uses locks or some other mechanism [known to pypy] would see operations timely and in order, while code that doesn't synchronize its operations may see somewhat outdated shared state, as if threads executed in slightly different global order.

Yes. However, the programmer can't and shouldn't synchronize, say, field lookup, so those dictionaries (and only those) need to be thread-safe - Jython uses a ConcurrentHashMap for this purpose, even too that's too thread-safe (there needs to be no thread-safety guarantee on the values of fields).

About profiling, how do I distinguish between attribute vs globals vs builtins lookups in the profile?

Others can surely answer better, since I don't know the code; I guess I'd add a "type" field to the dictionary to store such information, or maybe to the call sites, depending on what's easier to annotate; but I also guess this naive solution could require lots of work.

d.

On 27 December 2010 12:50, Paolo Giarrusso wrote:

...

On Mon, Dec 27, 2010 at 19:54, Dima Tisnek wrote:

...

what do you think of liburcu? lttng.org/urcu

I've studied RCU in the Linux kernel (from which URCU derives) and thought for a long time of using it for this problem. In short, once you have GC, RCU (as in the Linux kernel) becomes (almost) trivial, because RCU is almost entirely about how to delay freeing objects. The RCU-GC connection is also mentioned by Documentation/RCU/RTFP.txt in the Linux sources.

So, you need to just read about persistent data structures, and remember that persistence is not the point - data structures which are just almost persistent can also be OK, if you get them right. If you replace a value in a dictionary, for instance, you don't necessarily need to keep the old version around, as long as you the value fits in a memory word so that it can be atomically replaced. http://hackerboss.com/copy-on-write-101-part-2-putting-it-to-use/

Speaking of libraries, you might want to look at this for the atomic primitives you'll need: www.hpl.hp.com/research/linux/atomic_ops/ I'm more used to the primitives of the Linux kernel, I remember I didn't fully like that library, but IIRC it was a matter of taste - the library is from Hans Boehm, which makes it trustworthy.

...

p.s. if/when I get around to profiling pypy, which is something I want to do, I'll be sure to share the results here.

Great, thanks!

...

d.

On 27 December 2010 10:57, Paolo Giarrusso wrote:

...

On Mon, Dec 27, 2010 at 07:00, Dima Tisnek wrote:

...

(dan) random binary trees: O(log2(n)) is 7.2 for builtins, though the constant factor for locks, etc, might make it worthwhile

"7.2"? What is that? Do you mean 7.2=log2(no. of builtins)?

...

(paolo) non blocking hash maps: memory barriers can be quite costly too

Well, you just _cannot_ avoid them, whatever is your fancy data structure. You can only move most of the cost (or all of it) to write operations - which is helpful if reads are most common, a case which you discuss in your mail.

== Why memory barriers are required (in more detail) == If you use persistent data structures, also called copy-on-write or purely functional (and that's the most obvious way to use a tree in a parallel setting), the whole synchronization problem is reduced to exchanging a pointer (to the root of the tree) between a writer and a reader thread. Let's consider this in the Java memory model (the state of the art). In this model the writer thread has to use an expensive StoreLoad barrier, i.e. mfence on x86 [1], costing more or less as much as a cache miss, while the reader needs just a cheap Load* barrier (for free on x86, cheap on other processor). If you don't use a volatile field, there is very little guarantee about what your program means, and it is almost always buggy; the equivalent in the new C++ memory model (which is otherwise very similar) gives completely undefined semantics (and even crashes are possible in practice, for instance if the reader thread sees a not-fully-initialized object because of the race and invokes a virtual method on it).

[1] http://g.oswego.edu/dl/jmm/cookbook.html

== Other stuff ==

...

different options will have to be implemented and tested when we get there, speaking on which, is there a test dict load? does anyone have some profiling data, what portion of runtime is spent reading and writing attributes and globals anyways?

I'd be interested as well in such data.

...

Anyhow, back to parallel interpretation, Is there an issue or page that tracks what's needed for parallel interpretation? so far  mentioned: gc, dict, c api

...

Btw, I think that jit is more important at the moment, but time comes when jit juice has been mostly squeezed out ;-)

-- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/

-- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/

-- Paolo Giarrusso - Ph.D. Student http://www.informatik.uni-marburg.de/~pgiarrusso/