Lockless algorithms in python (Nothing to do with GIL)

[Ryan Kelly]

On Mon, 2010-06-28 at 18:27 -0700, Zac Burns wrote:
>
>
>         
>         I've managed to avoid locking in some cases by using
>         dict.setdefault() as a kind of atomic test-and-set operation.
>         It's not a full compare-and-swap but you could implement a
>         simple locking scheme using it like this:
>         
>         
>          class PretendLock:
>              def __init__(self):
>                  self.d = dict()
>              def acquire(self):
>                  myid = threading.currentThread().ident
>                  while self.d.setdefault("owner",myid) != myid:
>                      pass
>              def release(self):
>                  del self.d["owner"]
>         
>         
>         This depends on some peculiarities of the CPython
>         implementation that aren't guaranteed by the language spec -
>         namely that thread switches can't happen while executing C
>         code, that dict.setdefault is implemented in C, and that is
>         can calculate the hash of a string key without calling back
>         out to python code.
>
> 
> Thanks Ryan,
> 
> Agreed, I was timing the wrong thing - but largely because I wasn't
> sure what to time against. setdefault certainly seems to be a
> candidate for something to time. Even so, setdefault wins.
> 
> Though, I wouldn't want to use PretendLock in this case... it doesn't
> seem that having the spin loop would justify reducing reducing the
> lock allocation overhead in a no-contention scenario.


Oh totally - nobody reading this should even consider using that
PretendLock class for anything.  It's just an example of how to use
setdefault as a test-and-set kind of operator.


  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/4d07b468/attachment-0001.sig>