Lockless algorithms in python (Nothing to do with GIL)

[Zac Burns]

>
> Sure, but I think you're timing the wrong thing here.  You would only
> allocate the lock relatively rarely - it's the overhead of *acquiring*
> the lock that's the real problem.
>
>   rfk at durian:~$ python -m timeit -s "from threading import Lock; l =
> Lock()" "l.acquire(); l.release()"
>   1000000 loops, best of 3: 0.378 usec per loop
>
> Compare to one of my favourite dict methods, setdefault:
>
>   rfk at durian:~$ python -m timeit -s "d = dict()"
> "d.setdefault('hello','world')"
>   10000000 loops, best of 3: 0.189 usec per loop
>
>
> In the same ballpark really.
>
>



>
> 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.
>
> Usually, it's not worth it.  The one time I use this regularly is for
> lazy object initialisation, e.g. something like this:
>
>  def get_my_object(key):
>      try:
>         return objects[key]
>      except KeyError:
>         return objects.setdefault(key,create_my_object(key))
>
> If two threads happen to try initialising the object at the same time,
> only one will wind up in the dict and being used; the other will be
> discarded and garbage-collected.
>

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.

Yes, get_my_object is a good trick. I did just that to avoid instantiating
extra locks in one scenario.

--
Zachary Burns
(407)590-4814
Aim - Zac256FL
Production Engineer
Zindagi Games
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100628/4682ff10/attachment-0001.html>