Lockless algorithms in python (Nothing to do with GIL)

[Ryan Kelly]

On Mon, 2010-06-28 at 19:45 -0700, sturlamolden wrote:
> > > 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.

Very interesting idea.  Will it work if accessed through ctypes?

   ticker = ctypes.c_int.in_dll(ctypes.pythonapi,"_Py_Ticker")
   ticker.value = 0x7fffffff

Or does ctypes muck with the GIL in a way that would break this idea?


  Ryan


-- 
Ryan Kelly
http://www.rfk.id.au  |  This message is digitally signed. Please visit
ryan at rfk.id.au        |  http://www.rfk.id.au/ramblings/gpg/ for details

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://mail.python.org/pipermail/python-list/attachments/20100629/4ef6d18b/attachment-0001.sig>