Protothreads and Other Wicked C Tricks 229
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!"
From the source: (Score:5, Informative)
http://www.lysator.liu.se/c/duffs-device.html [lysator.liu.se]
Rob Pike invented this in 1985 (Score:5, Informative)
http://citeseer.ist.psu.edu/cardelli85squeak.html [psu.edu]
Doug Moen
neat way in C to express an old trick (Score:3, Informative)
I recall seeing the same trick implemented in assembler somewhat earlier, I think the technique was called towers?
Re:It isn't Duff's device. (Score:4, Informative)
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.
Not new (Score:4, Informative)
I guess the idea is it's extremely portable. (Score:5, Informative)
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.
Re:Rob Pike invented this in 1985 (Score:2, Informative)
From research!ucbvax!dagobah!td Sun Nov 13 07:35:46 1983
Received: by ucbvax.ARPA (4.16/4.13) id AA18997; Sun, 13 Nov 83 07:35:46 pst
Received: by dagobah.LFL (4.6/4.6b) id AA01034; Thu, 10 Nov 83 17:57:56 PST
Date: Thu, 10 Nov 83 17:57:56 PST
From: ucbvax!dagobah!td (Tom Duff)
Message-Id:
To: ucbvax!decvax!hcr!rrg, ucbvax!ihnp4!hcr!rrg, ucbvax!research!dmr, ucbvax!research!rob
extremely limited applicability (Score:5, Informative)
This is bad, lame, faux cooperative threads.
It's also not even particlarly new [mine-control.com] [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.
Python's way ahead of ya (Score:3, Informative)
The actual Python Enhancement Proposal [python.org] gives more detail and several badass use-cases.
Re: It isn't Duff's device. (Score:5, Informative)
Re:I guess the idea is it's extremely portable. (Score:5, Informative)
The argument that Rob Pike makes in A Concurrent Window System [swtch.com] and with Luca Cardelli in Squeak: a Language for Communicating with Mice [microsoft.com] 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 [swtch.com]. 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:a fun trick only useful in very specialized cas (Score:3, Informative)
It's ugly as sin, but your compiler had better get it right, or else it's not a C compiler.
Re:Implementation in languages? (Score:2, Informative)
I'm kind of surprised it hasn't been mentioned yet.
Re:a fun trick only useful in very specialized cas (Score:5, Informative)
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 [microchip.com]?
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:a fun trick only useful in very specialized cas (Score:2, Informative)
But the compiler won't decide to do this because it won't be able to establish that y (or pi) can not be changed between instances of this code.
Re:a fun trick only useful in very specialized cas (Score:3, Informative)
In your second example, the compiler *cannot* remove the sub-expression because the case statement that gets you there crosses a basic block boundary; the return statement from the blocking code, and the jump in through the switch are caught as valid C constructs that prevent the common sub-expression optimization.
The macros as given give you a semblance of variable continuity and scoping, but the compiler, after the macro substitutions, just sees a return on the end of the blocking section, and a switch into the code following, something like:
The ugliness in the macros is about letting other control constructs live around your switch in, but still generates legit code, but, for example, you can't use a local varible as an index to your for loop. Yuck.Re:wtf? (Score:5, Informative)
You can implement a simple memcpy function like this:So far, so good. Now Duff's problem was that this was too slow for his needs. He wanted to do loop unrolling [wikipedia.org], 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: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:It isn't Duff's device. (Score:3, Informative)
That's what Duff 'discovered', and it's the trick they're using here.
Re:I guess the idea is it's extremely portable. (Score:2, Informative)
Re:wtf? (Score:3, Informative)
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? (Score:5, Informative)
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:I guess the idea is it's extremely portable. (Score:3, Informative)
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.......
Re:I guess the idea is it's extremely portable. (Score:3, Informative)
Re:wtf? (Score:4, Informative)
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.