[pypy-dev] 1.4.1 threading

[Dan Stromberg]

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.