Sunday, January 4, 2009

Threading is not that hard

So there I was the other day, chilling in #python on freenode, when the discussion turns to threading. There is a regrettable tendency in the Python community to treat threading as some kind of voodoo black magic that should never be used. When I chimed in that I didn't think threading was all that hard, I was immediately told by several people that I was probably doing it wrong. Well, as you can imagine, that pissed me off enough that I'm writing this post now, on how to do threading the easy way.

Disclaimer: Most of this post owes a lot to Prof. Mike Dahlin, and his undergrad OS class. I've made some changes and added some stuff, but he should still probably get most of the credit for this list.

Here is what you do:
  • Identify your shared state, and create monitors for each shared piece of data - In Java locks and condition variables are available in java.util.concurrent.locks; in Python they're in the threading module. Shared data, broadly speaking, is anything that's accessed from more than one thread.
  • Whenever you access the shared data, do the following steps:

  • Acquire the lock
    Wait() on the condition variable for whatever conditions your code needs - spurious interrupts are generally allowed, so you should do this in a loop
    Optionally, assert your invariants
    Do your thing with the shared data
    Optionally, assert your invariants again
    Notify() the condition variable
    Release the lock

    This is sufficient to ensure that you won't get concurrent access to shared state, and you can avoid a whole lot of interesting and time-consuming bugs.

  • Acquire your locks in a consistent order - If two threads acquire the same locks in different orders, there's a chance of a deadlock.
  • Make sure that any given piece of code is only used from one thread - this isn't necessary for correctness, but it will save you a lot of headaches when you're debugging. Debug backtraces include line numbers, but they don't (as far as I know?) include which thread was running when the error happened. Don't make yourself guess! For larger projects, you should probably take this even further, and make sure that code that runs in separate threads goes in separate files.
  • Look at all your threads, figure out which other threads they could wait for, and put that information into a dependency graph. If that graph has any cycles, there's a chance your program could deadlock. A cycle doesn't guarantee a deadlock, of course, but an acyclic dependency graph will guarantee a deadlock-free program.
  • The while() { sleep() } pattern is just flat-out wrong, and painfully slow to boot. I've been guilty of it myself, so I know how tempting it is to use it when you don't know about condition variables, but now that you do, you have no excuse. There is no situation (that I can think of, anyway) where you would want to call sleep() in a loop. In fact, sleep() is usually wrong too, unless you're actually waiting for some fixed amount of real-world time to elapse.
  • People are occasionally tempted to skip locking in order to improve performance. It's true that locking imposes some overhead, but keep in mind: Moore's Law will magically make your program faster over time, but it will never make a buggy program less buggy.
Python partisans will generally recommend using process-based instead of thread-based concurrency, which is understandable since CPython (the most commonly-used implementation of Python) doesn't support thread-based parallelism. (You can have multiple threads, but only one will execute at a time, so you don't gain any performance.) Process-based parallelism is nice, but it has a few obvious drawbacks: You have the added overhead of extra Python interpreters, along with the added overhead of marshaling and unmarshaling data to pass between processes. Furthermore, processes avoid a lot of the problems that threads have by not having implicitly shared state, but it's still possible to have concurrent access bugs if you're not careful.

1 comment:

Æther said...

As expected, I didn't understand most of this post, though I did understand lots of the generalizing pipes post. As such, I normally wouldn't comment at all, except of one bit that I read.

When you mentioned that Moore's Law will magically make your program faster over time, I kind of shuddered. Somewhere before didn't you mention such a mindset is bad? I can't remember exactly, so perhaps you said it in person. In any case, it frightens me that there should be a need for such inefficiencies. Of course, I only know how to code in Java, and I never made it to threading, so I could be missing big something here.