Protothreads and Other Wicked C Tricks

lwb writes "For those of you interested in interesting hard-core C programming tricks: Adam Dunkels' protothreads library implements an unusually lightweight type of threads. Protothreads are not real threads, but rather something in between an event-driven state machine and regular threads. But they are implemented in 100% portable ANSI C and with an interesting but quite unintuitive use of the switch/case construct. The same trick has previously been used by Simon Tatham to implement coroutines in C. The trick was originally invented by Tom Duff and dubbed Duff's device. You either love it or you hate it!"

Comments

Looks pretty cool

[bobalu]

I used a Lifeboat lib back in the late 80's that this reminds me of. Cooperative multitasking. Eventually ported the whole thing to OS/2 and used that threading instead. All the code pretyy much worked as-is.

Job security?

[elgee]

So this is so "counterintuitive" that no one else will ever understand your code?

Sounds ideal!

From the source:

[MythMoth]

Duff on Duff's Device:
http://www.lysator.liu.se/c/duffs-device.html

Re:From the source:

[Bastian]

Wow. And I used to think C was frightening when I discovered the fun you can have with a program that takes command-line arguments when you start making recursive calls to main().

When I saw that code snippet, I found myself switching back and forth between thinking "this is the most beautiful thing I have ever seen" and "dear god, who ordered that monster" so rapidly my brain almost a sploded.

Seen this already

[Anonymous Coward]

I first came across this while I was working on the e-voting machines. There was a dept especially allocated to investigating how to hide certain features in c code to make them look like soemthing else.

It isn't Duff's device.

[mc6809e]

Duff's device is a way of forcing C to do a form of loop unrolling. It has nothing to do with coroutines.

Re:It isn't Duff's device.

[LLuthor]

Duff's device was the first convoluted form of a switch() statement which became well known.
All these C "tricks" employ the same technique (though more elegantly) for different goals. Nonetheless, Duff's device can be said to have inspired such code.

Re:It isn't Duff's device.

[Anonymous Coward]

From Duff's 1983 usenet post:

"Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into."

Re: It isn't Duff's device.

[shalunov]

It most certainly is the Duff's device, or at least is very close to it. Duff's device is, indeed, a way to unroll loops; specifically, a way to unroll loops that uses a peculiarity in switch statement syntax that allows case to point inside a loop body. Now, take a look at lc-switch.h in the Protothreads tarball. It contains macros that use the same peculiarity to jump inside functions instead of loops.

Rob Pike invented this in 1985

[dmoen]

This looks very similar to the implementation technique used for the Squeak programming language (not the Smalltalk Squeak). Squeak is a preprocessor for C that makes it very easy to use this technique.

http://citeseer.ist.psu.edu/cardelli85squeak.html

Doug Moen

Not new

[Anonymous Coward]

SGI had state threads library since long http://oss.sgi.com/state-threads

Re:Wait just a minute ...

[LLuthor]

And the JVM is written in C :)

I guess the idea is it's extremely portable.

[skids]

...not bound to any particular OS.

If that's what folks are looking for, another option is the tasks added to LibGG a while back. Tradeoffs either way -- LibGG's requires at least C signals (but will use pthreads or windows threads if detected during compile time), whereas this can be used in OS-less firmware. But on the positive side you can use switch() in LibGG tasks -- what
you can't use are a lot of non-MT-safe system calls. It's an OK abstraction but of course there are so very many ways to accidentally ruin portability that it is far from foolproof.

http://www.ggi-project.org/documentation/libgg/1.0 .x/ggAddTask.3.html

Re:I guess the idea is it's extremely portable.

[twiddlingbits]

It is bound to a paticular KIND of OS. This code would not work right in a pre-emptive multi-tasking OS unless it was the highest priority task. It works best without an OS as it makes it's own blocking.

I read his paper where he said "writing an event-driven system is hard". I guess he has never heard of a using Finite State Automata for the design? State machines are very simple to program. An event driven system is not at all hard to write, although you often times do have to have some deep hardware and/or procesor knowledge to do it well. I wrote many of them in the 1980's when I did embedded C code for DOD work, although I have not done so in quite a few years. Once Ada came along everyone abandoned C as too obtuse for embedded work for the DOD. I once did benchmarks that showed decent C code without strong optimization outperformed Ada code, but C was dead already in their minds. I'm glad to see some folks are still interested in it on the commercial side of programming. After all we can't write everything in Java ;)

Re:I guess the idea is it's extremely portable.

[plalonde2]

The challenge is making the design maintainable. There isn't a program that can't be written as a state machine; but most programs expressed this way are difficult to understand and maintain.

The argument that Rob Pike makes in A Concurrent Window System and with Luca Cardelli in Squeak: a Language for Communicating with Mice is that many of the event systems and associated state machines that we write can be much simplified by treating input multiplexing, and thus coroutine-like structures, as language primitives.

This work follows directly from Hoare's Communicating Sequential Processes - a good summary can be found here. Working with CSP only a little has convinced me of how much easier so many systems tasks are in this framework than in the world of the massive state-system/event loop world.

Re:I guess the idea is it's extremely portable.

[GlassHeart]

There isn't a program that can't be written as a state machine; but most programs expressed this way are difficult to understand and maintain.

My experiences contradict your statement. State machines are both easy to implement, and easy to debug, if you do it the right way. I have seen many entirely wrong implementations, including one where you can go from any of about two dozen "states" to any other. I have seen some that just switch states when they feel like it, or switch states based on complex decisions, which makes debugging difficult. Put another way, you can make a "state machine" degenerate into something else, and nullify its benefits, if you refuse to follow the rules.

A well-implemented state machine has an important characteristic: it is clear to see why you are where you are. This means that state transitions are checked (against unexpected events) and traced, so debugging the machine is literally a matter of reading a log that looks like this:

in state 0, received event A so went to state 2
in state 2, received event B so went to state 1
in state 1, received event C so went to state 5
in state 5, ignoring event A
in state 5, received unexpected event C

and so on. In this particular example, the question to answer is why we're not handling event C properly in state 5, or why we went to state 5 in the first place. Either should be pretty obvious when you consult the original design. The fix is likewise obvious. Figuring out state machines, in my experience, has always been easier than figuring out multi-threaded code.

This isn't to say that all programs should be implemented as a state machine. Simple Unix-style pipe programs, for instance, are generally unsuitable. If you don't know how to design a state machine properly, it's also going to be unsuitable.

Re:I guess the idea is it's extremely portable.

[Cwaig]

I suspect Adam knows all about FSM's - he was also the original author of the LIWP TCP/IP stack.

Your point about only working on a particular kind of OS isn't a valid one. Why would it need to be the highest priority native thread?

I've actually used the Protothread library in implementing the playback code of a PVR - and what it actually provides is explicit scheduling between a set of tasks. For example - playing back an MPEG2 Transport stream requires you to do perform several distinct tasks:
1) Demultiplex the Transport stream
2) Feed the MPEG video decoder hardware
3) Feed the MPEG audio decoder
ie. 1 producer, 2 consumers.

You can implement this using normal threads. Or you can cut down on overheads and use protothreads, given that you only have a single instance of the MPEG hardware blocks, and can only play a single TS anyway.

The system level thread for playback can be thought of as a container for the conceptual Protothreads that schedule cooperatively within the system thread in a producer/consumer type relationship. Kind of like a process/thread separation on a larger OS (the code was running on Nucleus).

Using protothreads provides a deterministic task swap behaviour that removes the need for any locking primitives on the shared data structures between the producer (in this case the Demux thread) and the consumers (hardware feed threads). You can have a task swap occur based on your own complex conditions (for instance, threshold levels in stream buffers vs time until next frame decode is required), rather than the much more simplistic time slice scheduling or message blocking you'd see in a typical "real" threaded system.

The priority give to the thread which contains the Protothread scheduled tasks doesn't have to be the highest priority on the system at all. All that priority signifies is how important the actual process of playing the MPEG stream is relative to the other functions going on in the system in parallel - eg. it'd be lower priority than a flash update that was going on in parallel, or any interrupt service threads, or threads that respond to user input. But it'd be more important than the thread that's just doing the nightly scan for new DTT channels in the background.

I know - I do go on a bit.......

Loop Abuse

[wildsurf]

Reminded me of a function I once wrote...

The PPC architecture has a special-purpose count register with specialized branch instructions relating to it; e.g., the assembly mnemonic 'bdnz' means "decrement the count register by one, and branch if it has not reached zero." I've used this in some pretty weird loops, including this one that broke the Codewarrior 9.3 compiler (fixed in 9.4.) This computes the location of the n'th trailing one in a 32-bit integer. Pardon my weak attempt at formatting this in HTML:

static uint32 nth_trailing_one(register uint32 p, register uint32 n) {

register uint32 pd;
asm {

mtctr n; bdz end
top: subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdnz top

end: }

return __cntlzw(p ^ (p - 1));
}

The idea was that the instruction stream should stay as linear as possible; most of the time the branches are not taken, and execution falls through to the next line of code. Ironically (siliconically?), the entire function could probably be implemented in a single cycle in silicon; shoehorning bitwise functions like this into standard instructions tends to be extremely wasteful. Perhaps FPGA's will make an end run around this at some point. I've also tried this function with a dynamically-calculated jump at the beginning, similar to the case statement logic in the article.

Hmm, I had a point I was trying to make with this post, but now it's escaped my mind... :-)

Re:Loop Abuse

[wildsurf]

Unless you know that n is usually large, wouldn't this be more efficiently implemented with cntlzw?

It would be if I were looking for the n'th leading one, but this code is looking for the n'th trailing one. (e.g. for 0b0010011001011100, the 3rd trailing one is in the fifth-lowest bit.) The equivalent code sequence for leading ones is in fact more complicated, requiring three arithmetic instructions and a branch per iteration. (cntlzw, shift, xor, branch).

I actually use this code as part of an algorithm where I have a very large (e.g. 65k-element) packed single-bit histogram array, and need to find the position of (say) the 1000th set bit. Vector instructions can do a coarse population-count from one end fairly efficiently, but once it's narrowed down to a 32-bit region, it comes down to slicing and dicing. My code operates by clearing the rightmost set bit in each iteration (x & (x - 1)), then at the end, isolating the needed bit (x ^ (x - 1)) and using cntlzw to find its position. To clear the leftmost set bit, you need three instructions: first get its position with cntlzw, then shift 0x80000000 right by that number of bits, and finally XOR to clear the bit. (If there's a shorter sequence, I haven't found it.)

(oh, and for the troll responder-- you are quite spectacularly wrong. But thanks for the giggle.)

It was looking interesting until

[achurch]

I got to this little gem:

The advantage of this approach is that blocking is explicit: the programmer knows exactly which functions that block that which functions the never blocks.

My English parser thread shut down at that point . . .

Seriously, this looks like a handy little thing for low-memory systems, though I'd be a bit hesitant about pushing at the C standard like that--the last thing you need is a little compiler bug eating your program because the compiler writers never thought you'd do crazy things to switch blocks like that.

Python

[meowsqueak]

Weightless threads in Python:

http://www-128.ibm.com/developerworks/library/l-py thrd.html

They are cooperative but far more efficient than Python's own threading model. You can easily create hundreds of thousands of concurrent threads.

extremely limited applicability

[nothings]

Please note that this isn't interesting unless you work in, as, the FA says, a severely memory constrained system. No normal embedded system needs to do this, much less the systems most programmers on Slashdot probably work with.

This is bad, lame, faux cooperative threads.

Local variables are not preserved.

A protothread runs within a single C function and cannot span over other functions. A protothread may call normal C functions, but cannot block inside a called function.

It's also not even particlarly new [1998].

Unless memory is at an absolute premium, just use cooperative threading instead. If you try to use prototheads, you'll quickly discover how unlike "real" programming it is. Even just a 4K stack in your cooperative threads will get you way more than protothreads does.

Re:Stupid

[mvdw]

Ummm, which operating system would that be? Not all programmers have the advantage of an operating system as such; my current development target has no OS, runs at 8MHz, and has 4kbytes of memory. Something like this could be extremely useful for me.

You want cool C stuff...

[Dr. Manhattan]

Get the book Obfiscated C and Other Mysteries by Don Libes. Explanations of various Obfuscated C contest entries, and alternate chapters illustrate neat corners of C, including a few things similar to this little library. Occupies a place of honor on my shelf.

a fun trick only useful in very specialized cases.

[TomRitchford]

It's too clever to be really useful unfortunately. The big issue is of course the no "local variables". Trouble is, if you are writing in C, the compiler may well be creating local variables for you behind your back. In C++ for example there are many cases where this will certainly happen, like

void DoSomething(const string&);
DoSomething("hollow, whirled");

where a local variable of type string will be temporarily created to pass to routine DoSomething.

Even if you are writing in the purest of C, you aren't guaranteed that the optimizer isn't going to very reasonably want to introduce the equivalent of local variables. And even if you are sure there's no optimization going on, you STILL don't know for sure that the compiler isn't using space on the stack. There just is no guarantee built into the language about this. And if you were wrong, you'd get strange, highly intermittent and non-local bugs.

You could be pretty sure. You could force the compiler to use registers as much as possible. You could keep your routines really short. (Hey, if they don't preserve local variables, then how do they do parameter passing?? Parameters are passed on that same stack!)

But to be completely sure, you'd have to look at the output code. It wouldn't be too hard I suppose to write a tool to automatically do it...you'd just look for stack-relative operations and flag them. But then what would you do if something wasn't working? Yell at the compiler? Rewrite the machine language?

I guess I don't quite see the use now I've written this up. When is memory THAT important these days? It ain't like I haven't done this, I've written significant programs that I got paid money to do that fit into 4K (an error correction routine).

But that was an awfully long time ago. Now it's hard to find memory chips below 1Mbit. That two byte number is interesting but your "threads" aren't doing any work for you -- the whole point of threads is that you are preserving some context so that you can go back to them.

And since you can't use local variables, you can't use things like the C libraries or pretty well any library ever written, which is teh sux0r.

For just a few more bytes of memory and a few more cycles, you could save those local variables somewhere and restore 'em later. Suddenly your coding future is a brighter place. Tell the hardware people to give you 128K of RAM, damn the expense!

You could even put in a flag to indicate that that particular routine didn't need its local variables saved so you'd get the best of both worlds, use of external libraries as well as ultra-light switching.

Yes, can be useful (depending on platform)

[ihavnoid]

As the prothread homepage says, it's for extremely small embedded systems, where there are no operating systems, with tiny amount of memory (You can't use DRAMs on systems that cost something less than $1). Want to use threads on those kind of systems, you have no choice.

Another advantage is its portability. Small embedded systems, whether they have operating systems or not, usually can't support some fully-blown threading standard. Those operating systems seem to implement some kind of 'specially tuned' thread APIs.

Using these kind of threads on a full-blown PC (or servers) would have almost no benefit. However, in the embedded software engineer's perspective, it's great to see a ultra-lightweight thread library without any platform-dependent code.

Re:a fun trick only useful in very specialized cas

[dmadole]

It's too clever to be really useful unfortunately. The big issue is of course the no "local variables". Trouble is, if you are writing in C, the compiler may well be creating local variables for you behind your back. In C++ for example there are many cases where this will certainly happen, like

void DoSomething(const string&);
DoSomething("hollow, whirled");

where a local variable of type string will be temporarily created to pass to routine DoSomething.

You need to read the article.

It only says you can't use local variables across functions that block. Actually, it doesn't even say that you can't use them, it only says don't expect their value to be preserved.

In your example, even if the compiler does create a local variable to call DoSomething, and even if DoSomething does block, who cares if the value of that local variable is preserved, since it's impossible to reference it again after that statement?

But that was an awfully long time ago. Now it's hard to find memory chips below 1Mbit.

I can help you with this problem! Is 16 bytes small enough?

And since you can't use local variables, you can't use things like the C libraries or pretty well any library ever written, which is teh sux0r.

But you can use the C libraries. Just don't use local variables across functions that block. Only a very few C library functions block.

Re:Dijkstra says...

[mikeage]

Dijkstra is not $DEITY. There is a difference between a competent programmer and a brilliant programmer. Sometimes one has to be clever in order to get the job done.

Actually, since the running of $export DEITY=Dijkstra, he is now.

wtf?

[DeafByBeheading]

Okay, I'll play the n00b. I understand most of this, but my coding background is not that great, and mostly in C++, Java, and PHP, and I'm having problems with the switch from Duff's Device...


  switch (count % 8)
  {
  case 0: do { *to = *from++;
  case 7: *to = *from++;
  case 6: *to = *from++;
  case 5: *to = *from++;
  case 4: *to = *from++;
  case 3: *to = *from++;
  case 2: *to = *from++;
  case 1: *to = *from++;
        } while (--n > 0);
  }


What the hell is up with that do { applying only in case zero? It's in several places on the net just like that and Visual Studio compiles this just fine, so it's not an error. I checked K&R, and they don't even hint at what could be going on there... I'm lost. Help?

Re:wtf?

[ggvaidya]

Okay, I'll try and see if I can figure this thing out (you have to admit, it screws with your mind just looking at it ...):

You can implement a simple memcpy function like this:

void copy(char *from, char *to, int count) {
  do {
      *from++ = *to++;
      count--;
  } while(count > 0);
}

So far, so good. Now Duff's problem was that this was too slow for his needs. He wanted to do loop unrolling, where each iteration in the loop does more operations, so that the entire loop has to iterate less. This means the 'is count > 0? if so, go back, otherwise go on' part of the loop has to execute fewer times.

Now, the obvious problem with this is that you don't know how much you can unwind this particular loop. If it has 2 elements, you can't unwind it to three elements, for instance.

This is where Duff's Device turns up:

int n = (count + 7) / 8; /* count > 0 assumed */
 
  switch (count % 8)
  {
  case 0: do { *to = *from++;
  case 7: *to++ = *from++;
  case 6: *to++ = *from++;
  case 5: *to++ = *from++;
  case 4: *to++ = *from++;
  case 3: *to++ = *from++;
  case 2: *to++ = *from++;
  case 1: *to++ = *from++;
        } while (--n > 0);
  }

First, we check to see how much we can unroll the loop - for instance, if count is perfectly divisible by 5, but not 6, 7, or 8, in which case we can safely have 5 copies inside our loop without worry that the copy is going to move past the end of the array. Then - and here's the magic trick - we use switch to jump into a do loop. It's a perfectly ordinary do loop; the trick is entirely in the fact that if count==6, for instance, then C considers the do-loop to begin at 'case 6:', causing 6 copies of '*to++ = *from++' to be executed before the 'while' returns the loop position to the 'case 6:' point which is where, as far as C is concerned, the do-loop began.

Thus, the loop is unwound to a level that it can handle.

I think.

Feel free to correct/amplify/mock. :)

cheers,
Gaurav

Re:wtf?

[Brane]

[...]the 'while' returns the loop position to the 'case 6:' point which is where, as far as C is concerned, the do-loop began.

No, it returns to the 'case 0:' point where the 'do {' is. (Otherwise the loop wouldn't be executed count times, and somehow I think this Duff guy would have thought of that...)

Re:wtf?

[ChadN]

I disagree with your assessment, although you were on the right track; The loop doesn't return back to the case label where the loop was entered, it always jumps back to the 'do' statement (synonomous with the case 0:).

The way you describe it is that the loop is unrolled to a size that is safely divisible into the 'count' value, which is an interesting idea, but would not be as efficient (large prime number counts would not get unrolled, for example, and a more complex computed got would be required at the loop end).

My take is this: with loop unrolling, one always has to take care of the 'remainder'. In the above example, the loop is unrolled to be a fixed size (8 repeated copy instructions, instead of one), and any count not divisible by 8 has to handle the remainder of the count after dividing by 8. Conceptually, you could imagine handling this remainder with a separate case section after the unrolled loop. In Duff's device, the remainder is actually dealt with first, by intially jumping into the loop somewhere other than the beginning, then letting the fully unrolled loop finish up.

In answer to the previous poster's question, the 'do' could (probably) be put on it's own line, before case 0:, but that wouldn't look nearly as bizarre. :)

Of course, maybe I'm wrong too. I hope not.

Re:wtf?

[Tarwn]

So in a shorter description, what happens is that:
1) you determine how many groups of 8 you will need, rounding up to count the remainder block as well (if there is one)
2) code enters switch statement based on the remainder value, hits the correct case and falls through (note that if there was no remainder we start at the top of the cases and fall through, consuming an entire 8 block)
3) code hits the while, decrements the number of 8 blocks (as we just finished off the partial "remainder block")
4) return to do, fall through to finish this 8 group
5) loop back to 3

Took me a few minutes of staring at it (and I admit, some tme looking at above descriptions) to get over 4 years of no C in my diet, but now I have to admit that is beautiful.

Use of this technique in Felix

[skaller]

FYI this technique is heavily exploited in the programming language Felix:

http://felix.sf.net/

to provide user space threading. The main difference is that all the 'C tricks' are generated automatically by the language translator. If you're using gcc then the switch is replaced by a computed jump (a gcc language extension). On my AMD64/2800 time for creating 500,000 threads and sending each a message is 2 seconds, most of the time probably being consumed by calls to malloc, so the real thread creation and context switch rate is probably greater than Meg/sec order .. just a tad faster than Linux. Both MLton and Haskell also support this style of threading with high thread counts and switch rates (although the underlying technology is different).

Should work quite fine

[zde]

Unless you try to 'yield' something from within your own 'switch' statements. Then such 'smart' macros will silently pollute current 'switch' block with bogus case values, so it:

1) silently modifies you 'switch' statement sematics
2) fails to continue from the right spot on next iteration.