Thursday, April 9, 2009

A Curious Course on Coroutines and Concurrency

On Wednesday, March 25th, I attended David Beazley's A Curious Course on Coroutines and Concurrency tutorial at PyCon 2009. This was an excellent tutorial that continued from where David's Generator Tricks for Systems Programmers tutorial from PyCon 2008 left off. (See my notes on that tutorial in my PyCon 2008 Notes blog post; I see I never did write a summary.)

David again has made his tutorial materials (including excellent slides and plenty of code samples) publicly available:

At the start of the tutorial I had written generators and had some recollection of the "Generator Tricks for Systems Programmers" tutorial. But I had only vague sense of what a coroutine is. After the tutorial I feel like my understanding of coroutines is much deeper. I'm ready to use them when called for. I might even understand them well enough to avoid looking for all kinds of inappropriate nails to hit with this new hammer.

After an entertaining overview—David's sense of humor provided some sugar to help the medicine of the sometimes challenging material go down—he introduces coroutines. As he writes (on slide 8), in Python 2.5 generators "picked up some new features to allow 'coroutines'" (see PEP-342 "Coroutines via Enhanced Generators"), "most notably: a new send() method". He adds "If Python books are any guide, this is the most poorly documented, obscure, and apparently useless feature of Python."

I digress, but as the author of the Python Essential Reference, David has raised the bar for himself. I happened to pick up a copy of a draft manuscript of a fragment of chapter 6—"Functions and Functional Programming"—from the upcoming 4th Edition at the Addison-Wesley booth at PyCon. Following a section in that chapter explaining what coroutines are is a section entitled "Using Generators and Coroutines". David explains that "generator functions are useful if you want to set up a processing pipeline, similar in nature to using a pipe in the UNIX shell." After an example of this he writes "Coroutines can be used to write programs based on data-flow processing. Programs organized in this way look like inverted pipelines." The example that follows explains that "the coroutine pipeline remains active indefinitely or until close() is explicitly called on it." So "a program can continue to feed data into a coroutine for as long as necessary", and his example shows two consecutive calls to send different data into the pipeline.

I've never owned a copy of Python Essential Reference, but after reading this draft manuscript and seeing first-hand David's ability to simplify sometimes complex material, I've pre-ordered a copy of the 4th Edition.

Anyway, I need to remember that this is meant to be a summary of the tutorial. If you want the details you can read the slides and look at the code samples.

The tutorial was divided into 9 parts. Part 1 (slides 15 through 33) is a very clear introduction to generators and coroutines. He summarizes (in slide 33) that generators produce data for iteration, whereas coroutines are consumers are data and are not related to iteration. He warns us not to mix the two concepts together.

In Part 2 ("Coroutines, Pipelines, and Dataflow", slides 34 through 52) David explains that coroutines can be used to set up pipes. Each pipeline needs an initial source (a producer) and and end-point (a sink). Because (unlike generators which pull data through the pipe with iteration) coroutines push data into the pipeline with send(), they allow you to send data to multiple destinations. That is, you can have branches in the pipeline. He shows broadcasting to multiple targets as an example. (See slides 44 through 46.) He concludes by showing how coroutines are "somewhat similar to OO design patterns involving simple handler objects". (I think he's talking about the Chain of Responsibility pattern.) He notes that just like a generator is an iterator "stripped down to the bare essentials", so is a coroutine very simple compared to the multiple classes required to implement this pattern. (This is an example of the claim made by Joe Gregorio in his The (lack of) design patterns in Python PyCon 2009 talk.) David also shows that coroutines are faster than objects (because of the lack of self lookups).

Part 3 ("Coroutines and Event Dispatching", slides 53 through 74) shows that "coroutines can be used to write various components that process event streams". His example shows parsing the XML data that is available with the real-time GPS tracking data of most Chicago Transit Authority buses. He has a coroutine that implements a simple state machine to convert the "events" from an XML parser into dictionaries of bus data, another coroutine to filter on dictionary fields, and a coroutine to print the dictionaries as a table. ''What's quite slick about this is that he hooks them together into a pipeline that works without modification'' with SAX, expat, and a custom C extension written on top of the expat C library. (Each is faster than its predecessor, and the latter is slightly faster than using ElementTree.)

Part 4 ("From Data Processing to Concurrent Programming", slides 75 through 91) shows how coroutines "naturally tie into problems involving threads and distributed systems", since you send data to coroutines just as you do to threads (via queues) or processes (via messages). He creates a coroutine call threaded and hooks it up (slide 84) to the example coroutines from Part 3 so the filters and printing coroutines run in a separate thread. (And he notes this makes it run about 50% slower!) He then shows how coroutines could also be used to bridge two processes over a pipe or socket. So he notes that coroutines allow us to separate the implementation of a task (the coroutines) from the execution environment (threads, subprocesses, network). But he cautions us that huge collections of coroutines, threads and processes may be difficult to maintain and without careful study may make your program run slower. He also warns that the send() method on a coroutine must be synchronized, and if you call send() on an already-executing coroutine your program will crash (so no loops or cycles in the pipeline or multiple threads sending data into the same coroutine).

From here, the tutorial gets much more "mondo". In Part 5 (slides 92 through 98) he explains that coroutines look like tasks, the building blocks of concurrent programming. In Part 6 (slides 99 through 109), he gives a crash course in operating systems (and shows the yield statement can be though of like a trap) in order to prepare us for Part 7 (slides 110 through 168), where he builds an operating system using coroutines. I'm not going to go into detail on this, because this summary is already too long and you're better off reading his slides and looking at the code sample than reading my description of this. I'll note though that I enjoyed the humor in slide 152, where having written the a Task class to wrap a coroutine, support for system calls and a Scheduler class with basic task management, he states "The next step is obvious; we must implement a web framework". But he settles for an echo server. In Part 8 (slides 169 through 188) he explains that coroutines can't call subroutine functions that yield, and explains the solution using "trampolining". Slide 187 is worth noting, where he shows that application code has "normal looking control flow", just like traditional socket code (and unlike any code using a module that uses event callbacks).

He wraps it all up in Part 9 (slides 189 through 198). Here's my summary of his summary:
  • generators (and coroutines) are "far more powerful than most people realize"
  • they have decent performance
  • but he's not convinced that it's worth using coroutines for general multitasking
  • it is "critically important" not to mix the three main uses of yield toegether:
  • iteration
  • receiving messages
  • a trap
If you find this at all interesting, I urge you to read David's slides and code. And join me in urging him to present another tutorial at PyCon 2010.

No comments: