Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Protothreads and Other Wicked C Tricks 229

Posted by CowboyNeal from the working-as-intended dept.
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!"
This discussion has been archived. No new comments can be posted.

Protothreads and Other Wicked C Tricks More

Protothreads and Other Wicked C Tricks

Comments Filter:

  • Looks pretty cool (Score:5, Interesting)

    by bobalu ( 1921 ) on Thursday October 06, 2005 @08:29PM (#13735824)
    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.

    • I guess the idea is it's extremely portable. (Score:5, Informative)

      by skids ( 119237 ) on Thursday October 06, 2005 @09:08PM (#13736017) Homepage
      ...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 [ggi-project.org]

      • Re:I guess the idea is it's extremely portable. (Score:5, Insightful)

        by twiddlingbits ( 707452 ) on Thursday October 06, 2005 @09:26PM (#13736089)
        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. (Score:5, Informative)

          by plalonde2 ( 527372 ) on Thursday October 06, 2005 @10:29PM (#13736397)
          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 [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.

          • 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.

            Wow, I know this one from first hand experience. We use a "graphical" programming language called LabVIEW where I work and I was tasked with the maintanance of a software program that was one giant state machine. Let me tell you, it was almost impossible to tell where the program was and where it was going half the time

            • Let me tell you, it was almost impossible to tell where the program was and where it was going half the time because it passed around a state list like a stack from one state to another and sometimes just deleted the entire list and replaced it with a new order!

              Never ascribe to programming paradigm that which can be adequately explained by programmer stupidity ;).

              There is rarely a need for a statemachine unless you are trying to optimize something really low level in hardware. I can't really think of

          • Re:I guess the idea is it's extremely portable. (Score:4, Interesting)

            by GlassHeart ( 579618 ) on Friday October 07, 2005 @02:34AM (#13737469) Journal
            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.

            • One thing which helps immensely is also having a strong type system with "sum" types, where you can declare types like

              type state =
              State1 with (all_data_pertaining_to_state1)
              | State2 with (all_data_pertaining_to_state2)
              | State3 with (all_data_pertaining_to_state3)
              ...

              and just have one state variable of type state. This will:

              • ensure that you don't accidentally use state information that is not valid in a given state.
              • ensure that all the state transitions in your code explicitly
          • It's worth pointing out that CSP can be implemented by using co-operative multi-tasking that the Protothreads idea is similar to. However at first glance it seems Protothreads are too light-weight to be useful so you must use things like GNU pth, or Microsoft's Fibers. All this can be found in C++CSP [cppcsp.net], as well as other CSP implementations.
        • 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) Demultiple
          • Read the comments in the code. It says if protothreads call other C routines and when in that context the called routine blocks then things don't work right.

            Explicit scheduling is NOT pre-emptive, it's static. It can be priority driven though as is pre-emptive. Pre-emptive is dynamic based on operating conditions such as a user input, interrupt, etc. I've never seen a lot of overhead on task/thread changes in an OS in many years.

            Producer- Consumer tasks have to be very tightly coupled and managed unless you

  • Job security? (Score:4, Funny)

    by elgee ( 308600 ) on Thursday October 06, 2005 @08:30PM (#13735829)
    So this is so "counterintuitive" that no one else will ever understand your code?

    Sounds ideal!

  • From the source: (Score:5, Informative)

    by MythMoth ( 73648 ) on Thursday October 06, 2005 @08:33PM (#13735847) Homepage
    Duff on Duff's Device:
    http://www.lysator.liu.se/c/duffs-device.html [lysator.liu.se]

  • Seen this already (Score:5, Funny)

    by Anonymous Coward on Thursday October 06, 2005 @08:34PM (#13735848)
    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.

  • Implementation in languages? (Score:3, Insightful)

    by Poromenos1 ( 830658 ) on Thursday October 06, 2005 @08:36PM (#13735861) Homepage
    I don't program in C that much any more, but it would be nice if this was implemented in higher level languages. I don't know if they would gain anything, but it's at least interesting.
    • And by that, I mean that the interpreters of languages (Python, Lua, etc) would use this to implement their threads in.

      • Re:Implementation in languages? (Score:2, Interesting)

        by Anonymous Coward
        Protothreads are quite limited in what they can do - they are just a way of expressing a state machine using co-routines.

        Real threads are much better for things like interpreters. JIT compilation with native threads is even better.
        • Just curious - in what ways do you think they are more limited? A OS threading mechanism is just a glorified state machine anyway. I agree that these sorts of 'threads' (or 'fibers' as they are known in Windows) run into troubles with blocking I/O, but with async. I/O they are quite useful once you've got some thread management mechanisms incorporated.
          • One big practical limitation is that you can't actually take advantage of multiple CPUs. This used to not be very important, but with dual-core CPUs available, it's likely there will be a huge increase in the number of desktop machines with SMP. Granted you could modify these systems to run in two threads, but then you lose the cross-platform abilities which are the main benefit. If you can create 2 threads on all systems you support, why not just create as many as you need? It ends up making more sense

      • Python (Score:5, Interesting)

        by meowsqueak ( 599208 ) on Thursday October 06, 2005 @09:42PM (#13736166)
        Weightless threads in Python:

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

        They are cooperative but far more efficient than Python's own threading model. You can easily create hundreds of thousands of concurrent threads.
        • From the desription it seems like Python stackless [stackless.com].
          • Yes, it's similar in many respects, but does not require the Stackless infrastructure. I'm not saying either way which is better.
        • If you like weightless threads, you'll love greenlets [codespeak.net] (a standalone spinoff module of Stackless). Unlike generator-based coroutines, greenlets can be nested and switched to any other routine without the use of 'yield'. Also, any function can be turned into a greenlet - very little rewriting needed. There's hardly any overhead either since it's just an extension module written in C for the unmodified Python interpreter.

      • Python's way ahead of ya (Score:3, Informative)

        by xant ( 99438 )
        Actually, I don't know if this is exactly the same feature, but it sounds like it can be used that way. Check out the What's new in Python [python.org] entry. This is currently implemented in Python CVS, to be available in Python 2.5.

        The actual Python Enhancement Proposal [python.org] gives more detail and several badass use-cases.
      • Lua at least already has something like this. They're called asymmetric coroutines. Also check out Scheme, Scheme's had continuations forever and some folks have done interesting things with them.
    • I agree. What about PHP for example? Is there some clever trick that could be done like this that would enable a thread-like behaviour, since PHP currently lacks the ability to spawn threads? Processes it does, but not threads, and the two are just different enough to limit PHP's general applicability outside of web apps...
    • Try call-with-current-continuation (a.k.a. call/cc) in Scheme or any of the other functional languages. call/cc lets you write co-routines (and many other powerful control constructs) quite easily, and co-routines are much more powerful than this protothread trick. A favorite for Schemers showing off the power of call/cc is the amb macro (which uses call/cc internally). The following code can actually be written in Scheme (after adding the amb and assert macros): (let ((x (amb 1 2 3)) (y (amb 4 5
    • Well, there is always erlang [erlang.org].

      I'm kind of surprised it hasn't been mentioned yet.

  • It isn't Duff's device. (Score:3, Interesting)

    by mc6809e ( 214243 ) on Thursday October 06, 2005 @08:37PM (#13735872)

    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. (Score:4, Informative)

      by LLuthor ( 909583 ) <lexington.luthor@gmail.com> on Thursday October 06, 2005 @08:48PM (#13735911)
      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. (Score:3, Insightful)

      by 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."
      • Tom clarified this on my blog. [brainwagon.org]

        Yeah. I knew this. In my piece about The Device, I mention something about a similar trick for interrupt-driven state machines that is too horrible to go into. This is what I was referring to. I never thought it was an adequate general-purpose coroutine implementation because it's not easy to have multiple simultaneous activations of a coroutine and it's not possible using this method to have coroutines give up control anywhere but in their top-level routine. A simple assembl

    • It can be used to implement coroutines in C. Google for "coroutines in C". any of the first bunch of links talk about it.

    • Re: It isn't Duff's device. (Score:5, Informative)

      by shalunov ( 149369 ) on Thursday October 06, 2005 @10:17PM (#13736336) Homepage
      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.
    • The summary only claims that the 'interesting but quite unintuitive use of the switch/case construct' is originally Duff's device, not application to coroutines.
    • Duff mentions in the description of his device "I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into." Could this be Duff's second device?
    • The idea of the Duff's device is to use switch to jump to a label depending on the value of a variable (in a portable way). You could use 'goto' with a bunch of conditions, but using switch will make cleaner code (as far as jumping around to arbitrary places in your code goes), and the compiler will probably make a jump table in most cases, which is faster.

      That's what Duff 'discovered', and it's the trick they're using here.

      • The idea of the Duff's device is to use switch to jump to a label depending on the value of a variable (in a portable way).

        That's the idea of a switch statement. Duff's device introduces a loop inside the switch statement but covering multiple cases, to efficiently unroll a loop into larger chunks.

  • Rob Pike invented this in 1985 (Score:5, Informative)

    by dmoen ( 88623 ) on Thursday October 06, 2005 @08:38PM (#13735876) Homepage
    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 [psu.edu]

    Doug Moen

    • Re:Rob Pike invented this in 1985 (Score:2, Informative)

      by Anonymous Coward
      He couldn't have invented it in 1985 since Duff sent his original mail in 1983:

      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

  • neat way in C to express an old trick (Score:3, Informative)

    by bani ( 467531 ) on Thursday October 06, 2005 @08:42PM (#13735886)
    While it is probably the first time the copy technique had been expressed in C, it's certainly not the first time the actual technique had been expressed in code.

    I recall seeing the same trick implemented in assembler somewhat earlier, I think the technique was called towers?

  • Not new (Score:4, Informative)

    by Anonymous Coward on Thursday October 06, 2005 @08:51PM (#13735928)
    SGI had state threads library since long http://oss.sgi.com/state-threads [sgi.com]

  • Loop Abuse (Score:5, Interesting)

    by wildsurf ( 535389 ) on Thursday October 06, 2005 @09:11PM (#13736028) Homepage
    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... :-)
    • Pardon my weak attempt at formatting this in HTML:

      It came out okay, but for future reference, Slashdot does allow a specialized <CODE> tag similar to <PRE>.

    • Re:Loop Abuse (Score:3, Interesting)

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

      Adam

      • Re:Loop Abuse (Score:4, Interesting)

        by wildsurf ( 535389 ) on Thursday October 06, 2005 @11:53PM (#13736809) Homepage
        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 (Score:5, Interesting)

    by achurch ( 201270 ) on Thursday October 06, 2005 @09:28PM (#13736099) Homepage

    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.

  • Stackless Python (Score:2, Interesting)

    by alucinor ( 849600 )
    Is this similar to Stackless Python [sjsoft.com] and green threads? I spend most of my time with interpreted languages, so my C is very lacking.

  • extremely limited applicability (Score:5, Informative)

    by nothings ( 597917 ) on Thursday October 06, 2005 @09:43PM (#13736169) Homepage
    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 [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.

    • Please note that this isn't interesting unless you work in, as, the FA says, a severely memory constrained system.

            Yeah, but my brain -- Ooh! Shiny!
    • "This is bad, lame, faux cooperative threads." Nobody said they were cooperative threads (re-read the summyary). Protothreads are not threads, they are something in between event-driven state machines and proper threads.

      You may think they are lame, I still think they are cool.

  • You want cool C stuff... (Score:5, Interesting)

    by Dr. Manhattan ( 29720 ) <<sorceror171> <at> <gmail.com>> on Thursday October 06, 2005 @10:08PM (#13736295) Homepage
    Get the book Obfiscated C and Other Mysteries [amazon.com] 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.

  • Dijkstra says... (Score:2, Interesting)

    by Jeff85 ( 710722 )
    "The competent programmer is fully aware of the limited size of his own skull. He therefore approaches his task with full humility, and avoids clever tricks like the plague." -Edsgar Dijkstra

  • a fun trick only useful in very specialized cases. (Score:4, Insightful)

    by TomRitchford ( 177931 ) on Thursday October 06, 2005 @10:28PM (#13736392) Homepage
    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.

    • The absence of local variables is because the stack is not preserved between invocations, and multiple invocations give the appearance of scheduled threads. There is nothing here that the compiler can break with its optimizer, unless it is breaking valid C code: the control flow expressed using the macros is completely legit C control flow. It's worth running the examples through just the C pre-processor in order to understand what gets built.

      It's ugly as sin, but your compiler had better get it right, o

      • The absence of local variables is because the stack is not preserved between invocations, and multiple invocations give the appearance of scheduled threads. There is nothing here that the compiler can break with its optimizer, unless it is breaking valid C code: the control flow expressed using the macros is completely legit C control flow. It's worth running the examples through just the C pre-processor in order to understand what gets built.

        I downloaded it. But the version that is there does not, in fact

        • Suppose the compiler decided to extract out the common y*(2*pi)/360 term as an optimization.

          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.
        • But that's precisely the reason you musn't use locals: they are not preserved. The switch in the "thread" setup sets up a new scope in which you might declare locals, but that scope need not be entered cleanly, leading to (in the case of your example) an uninitialized local variable.

          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 sw

    • As far as ridiculously low memory constraints go...
      I was talking to a friend the other day, who had to write the code for a car door opener dealie. You know the one. A really nice, high end one with an LCD that displayed stuff (not your average 100% hardware door opener). His code had a staggering 256 bytes of RAM to work with, and even then they were potentially 7 bytes overbooked. So yes, these kinds of constraints still exist. Sadly.

    • Re:a fun trick only useful in very specialized cas (Score:5, Informative)

      by dmadole ( 528015 ) on Thursday October 06, 2005 @11:40PM (#13736741)

      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.

  • Yes, can be useful (depending on platform) (Score:3, Interesting)

    by ihavnoid ( 749312 ) on Thursday October 06, 2005 @11:01PM (#13736533)
    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.
  • Is thre some similarity between these protothreads and fibers [msdn.com]?

  • wtf? (Score:3, Interesting)

    by DeafByBeheading ( 881815 ) on Friday October 07, 2005 @12:48AM (#13737096) Journal
    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?
    • Think of each "case" as a goto label and the "switch" as an indexed goto.

    • Re:wtf? (Score:5, Informative)

      by ggvaidya ( 747058 ) on Friday October 07, 2005 @02:09AM (#13737402) Homepage Journal
      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 [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:
      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
      • But it became largely unnecessary when optimizing compilers became available when RISC came about. A good compiler will unroll a simple loop like this smarter than you can.

        Besides, on any modern machine you'll get more speed up by copying a word at a time instead of tightening your byte-at-a-time loop. Because due to the caches, you'll likely end up moving cache lines at a time over the bus anyway (assuming stuff is aligned), and so the key becomes to minimize the number of instructions needed to do it. And

      • Re:wtf? (Score:3, Informative)

        by Brane ( 210649 )
        [...]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? (Score:5, Informative)

        by ChadN ( 21033 ) on Friday October 07, 2005 @04:53AM (#13737831)
        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? (Score:4, Informative)

          by Tarwn ( 458323 ) on Friday October 07, 2005 @06:35AM (#13738072) Homepage
          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.

      • Hmm. Doesn't make full sense to me this way.

        First part of your explanation is OK - let's say we need to unroll a loop for efficiency. And we decide to unroll it so it has 8 statements inside the loop. So, assuming count>0, we would do something like this (using dots to show indentation because "ecode" eats up leading spaces):

        void copy(char *from, char *to, int count) {
        ..int n = count / 8;
        ..int i;

        ..if (n > 0) {
        ....do {
        ......*from++ = *to++;
        ....../* 7 more times (code omitted to avoid slashdot

  • Use of this technique in Felix (Score:4, Interesting)

    by skaller ( 265521 ) on Friday October 07, 2005 @01:32AM (#13737265)
    FYI this technique is heavily exploited in the programming language Felix:

    http://felix.sf.net/ [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 (Score:3, Insightful)

    by zde ( 183513 ) on Friday October 07, 2005 @07:02AM (#13738147)
    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.

Slashdot Top Deals

Two can Live as Cheaply as One for Half as Long. -- Howard Kandel

Close