Lockless algorithms in python (Nothing to do with GIL)

[sturlamolden]

> > Many lockless algorithms that I have looked at thusfar require a
> > "Compare and Swap" operation. Does python have an equivalent to this?
> > Is python high level enough that it has something better than this or
> > it simply doesn't need it?

Python does have a GIL, and contrary to the title, this has a lot to
do with the GIL. Specifically, any set of operations protected by the
GIL are atomic in the CPython interpreter.

We can therefore get global synchronization 'for free', allowing 'lock
free' data structures that avoid using threading.Lock, and replaces it
with, well, nothing. :)

How to do it (it takes tiny amounts of C or Cython):

Take at look at page 14:

   http://www.dabeaz.com/python/UnderstandingGIL.pdf

The critical part is the variable _Py_Ticker in Python's source file
ceval.c, which is declared volatile int. As it is not declared static
it is a global variable, and we can actually manipulate its value from
a C extension:

   extern volatile int _Py_Ticker; // evil!!!

Now imagine temporarily setting _Py_Ticker to some ridiculous high
value like 0x7fffffff. That locks out all other threads, practically
forever, until we restore _Py_Ticker back to it's original value.

What this gives us is global synchronization for free! The GIL is
there anyway, so it adds no additional overhead.

By messing with _Py_Ticker we can force blocks of Python code to
become atomic in the interpreter. With this hack we can therefore
create data structures that are lock free relative to the CPython
interpreter. It is evil, but very cheap compared to using
threading.Lock. In fact it has exactly zero overhead: the GIL is there
anyway, and it is already acquired!

The safest placement of a _Py_Ticker hack is in a context manager. We
have to make sure it gets restored to a sane value, even in presence
of an exception.

Enjoy :)



P.S. If you get smart and think sys.setcheckinterval(sys.maxint) would
do the trick, you are actually not that smart. It will lock our own
thread out with a Poisson rate of 1./sys.getcheckinterval(). Thus we
have to attack _Py_Ticker from C.

P.P.S. And when we have taken control over the GIL, don't do anything
that might release it from C (like reading from a file). We cannot
afford to loose it :)