On Thu, Dec 23, 2010 at 06:58, Dan Stromberg <[email protected]> wrote: > On Wed, Dec 22, 2010 at 7:05 PM, Benjamin Peterson <[email protected]> > wrote: >> 2010/12/22 Dima Tisnek <[email protected]>: >>> 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-threads-nbhm 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/ _______________________________________________ [email protected] http://codespeak.net/mailman/listinfo/pypy-dev
