[pypy-dev] 1.4.1 threading

[Paolo Giarrusso]

On Thu, Dec 23, 2010 at 06:58, Dan Stromberg <drsalists at gmail.com> wrote:
> On Wed, Dec 22, 2010 at 7:05 PM, Benjamin Peterson <benjamin at python.org> wrote:
>> 2010/12/22 Dima Tisnek <dimaqq at gmail.com>:
>>> 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/