Wasp's Nest: A Lock-Free Concurrency Pattern In Python

http://emptysquare.net/blog/wasps-nest-lock-free-concurrency-python/

by mmariani • 13 years ago

31 5 13 years ago

kevingadd• 13 years ago

Does anything in CPython really count as lock-free, given the presence of the GIL? Lots of clever algorithms happen to work without the addition of mutexes in CPython, because you can count on individual python instructions being effectively atomic (like list append, if memory serves) due to the interpreter acquiring a global mutex whenever a python thread is running.

Decent writeup of read-copy-update, at least. I'm annoyed that he never provided any actual measurements to prove that the addition of a mutex is a bad solution for the problem, or too slow.

It's really, really easy to write a 'correct' lock-free implementation that gets dramatically outperformed by a simpler implementation using mutexes. It all depends on how you use the mutex, how fast your mutex implementation is, how fast your atomic primitives are, and other details like whether you're sharing cache pages.

munin2• 13 years ago

as a python programmer, you cannot think this way.

<s>one reason you cannot think this way is because the GIL is a CPython concept. if you program with this restriction in mind, you're not writing python, you're writing python targeted to the CPython implementation of python.</s> - edit, this is actually wrong, a comment below explains why.

the other reason is because it is misunderstanding of how the GIL works. the GIL is acquired for each python instruction so no two instructions will race against each other in the interpreter. however, two threads could have any arbitrary ordering of instructions and there is not a strict correspondence of instructions to statements.

CPython uses native threads for python threads so if you make multiple threads, they will race against each other. please don't make any assumptions about how the interpreter and those threads will interact, and just use either locks with good judgement or a lock-free algorithm that is grounded in a very deep understanding of the languages memory model.

samps• 13 years ago

While I agree that it's generally not helpful to rely on implicit atomicity in any Python, the reality is that all the other Pythons have followed CPython's lead and implemented the same memory model for compatibility. PyPy, Jython, and IronPython all have atomic bytecodes. So, for better or for worse, this bytecode atomicity is a de facto part of the language.

ysapir• 13 years ago

Also, in this paradigm, only one thread calls refresh() at any give time (either the MonitorThread or before the thread is created, the initializer thread). This is contrary to some definitions of lock free, such as [1], "if any thread performing an operation on the data structure is suspended at any point during that operation then the other threads accessing the data structure must still be able to complete their tasks". If we kill MonitorThread, other threads accessing RSState won't be able to complete their operation.

[1] http://www.justsoftwaresolutions.co.uk/threading/non_blockin...

Wasp's Nest: A Lock-Free Concurrency Pattern In Python

Related Stories