25 Dec 2002 graydon   » (Master)

concurrency abstractions

multi-threading seems awkward (and often is) because it makes very pessimistic assumptions about concurrency needs, eg:

  • any co-routine might need any/all global resources
  • any co-routine's state == an entire stack segment
  • any instruction is an equally likely preemption point

while making very optimistic assumptions about concurrency uses, eg:

  • threads always co-operate correctly on global resources they share (memory, signals, fds)
  • the sharing mechanisms (say, mutexes) are cheap
  • threads always re-schedule optimally, at zero cost

when people imply that "state machines are better than threads", they are broadly saying that if you analyze real-world concurrency needs and uses, you will more likely find that:

  • a small set of global resources need sharing
  • a small set of values makes up a co-routine's state
  • a small set of instructions are reasonable preemption points

therefore in these cases the mechanism of "full" multi-threading can be seen to be redundant distraction, providing little advantage over managing some small sets of values by hand. but moreover:

  • threads often co-operate incorrectly, due to programmer error, and worse: non-deterministically
  • lock contention and context switching is expensive, especially with increasing cache-dependence
  • a general thread scheduler doesn't always choose a very good schedule for your threads; your application may well know better

so it can be easy to see threads as worse than merely irrelevant, but in fact truly harmful to your program.

this is not to suggest that multi-threading cannot ever be put to good use. but rather that its default assumptions lead to strangely mismatched programs, which have too many unexpected failure cases associated with the optimistic assumptions, and too many ways to make simple tasks complex in order to meet the pessimistic assumptions.

there have, however, been some interesting systems developed which mix some sort of threads with stronger-than-default assumptions (either in language extensions or programming frameworks) to yield good results. see for example:

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!