C#’s async/await compared to protothreads in C++(blog.brush.co.nz)
blog.brush.co.nz
C#’s async/await compared to protothreads in C++
http://blog.brush.co.nz/2012/11/async-await-protothreads-cpp/
9 comments
(Disclaimer: I am one of the authors of CPC.)
Protothread is really just a set of macros, based of Duff's device, to make it easier to write automata in a threaded style. It has many limitations: it does not automatically save local variables, it does not compose (except when using "hierarchical protothreads", which involves rewinding the whole stack on every cooperation point), etc. Section 5.3 of Dunkels et al.'s paper states that these are only limitations of the "current protoype", but I am not aware of any implementation of protothreads solving these issues at all (except if you consider CPC a full-fledged implementation of Protothreads, done correctly ;-).
Protothreads is a hack, a maybe clever hack, but a hack nonetheless. CPC, on the other hand, is an extension of the C language, compiled to C by proven source-to-source transformations. Of course, you then have to pay the cost of the added dependency (protothreads is only a bunch of C files to include), and potential bugs in the translator.
You can find a comparison of existing solutions in my PhD thesis, section 1.3 (page 43): http://www.pps.univ-paris-diderot.fr/~kerneis/ (first link in the "research" section).
Protothread is really just a set of macros, based of Duff's device, to make it easier to write automata in a threaded style. It has many limitations: it does not automatically save local variables, it does not compose (except when using "hierarchical protothreads", which involves rewinding the whole stack on every cooperation point), etc. Section 5.3 of Dunkels et al.'s paper states that these are only limitations of the "current protoype", but I am not aware of any implementation of protothreads solving these issues at all (except if you consider CPC a full-fledged implementation of Protothreads, done correctly ;-).
Protothreads is a hack, a maybe clever hack, but a hack nonetheless. CPC, on the other hand, is an extension of the C language, compiled to C by proven source-to-source transformations. Of course, you then have to pay the cost of the added dependency (protothreads is only a bunch of C files to include), and potential bugs in the translator.
You can find a comparison of existing solutions in my PhD thesis, section 1.3 (page 43): http://www.pps.univ-paris-diderot.fr/~kerneis/ (first link in the "research" section).
Creator of protothreads here. Protothreads are not a hack.
Protothreads revolve around the concept of local continuations. Unlike traditional continuations, a local continuation only captures the state of execution within the local function in which they are created. I.e., a local continuation does not contain the call stack. This makes it possible to do things like invoking protothreads from multiple call paths.
The "hack" you refer to is just one possible implementation of the protothread concept, in which the local continuations are implemented by a switch statement in the spirit of Duff's device. This implementation technique allows the protothreads library to be implemented in only 7 lines of code (!) but it has a bunch of drawbacks, such as not recording the state of local variables. In fact, because of these drawbacks, the switch-based implementation arguably does not provide a fully functional version of protothreads.
There are other ways to implement protothreads. The original protothreads library contains an implementation where the local continuations are done using gotos and gcc's labels-as-values feature. This does remove some of the problems with the switch statement, but still does not record local variables. Others have implemented protothreads in C++, where a class object is used to store local variables, and by adding a C2C wrapper compiler that produces C code that stores and restores the local variables.
Protothreads were created to explore some of the finer points in the twilight zone between multithreading/coroutines and events/state machines. The intent was never to emulate continuations, coroutines, or threads but to find a less expensive way to achieve linear code flow. With protothreads, linear code flow can be achieved without having to store multiple thread stacks, which is important in many of the systems for which protothreads were originally intended. The switch-based implementation also has the added benefit of being possible use with any C compiler, which has been very useful as we have ported Contiki to a bunch of different platforms and C compilers.
But, yeah, the switch-based implementation of the protothreads concept can definitely be labelled as a hack. But - admit it - a beautiful hack! :)
Protothreads revolve around the concept of local continuations. Unlike traditional continuations, a local continuation only captures the state of execution within the local function in which they are created. I.e., a local continuation does not contain the call stack. This makes it possible to do things like invoking protothreads from multiple call paths.
The "hack" you refer to is just one possible implementation of the protothread concept, in which the local continuations are implemented by a switch statement in the spirit of Duff's device. This implementation technique allows the protothreads library to be implemented in only 7 lines of code (!) but it has a bunch of drawbacks, such as not recording the state of local variables. In fact, because of these drawbacks, the switch-based implementation arguably does not provide a fully functional version of protothreads.
There are other ways to implement protothreads. The original protothreads library contains an implementation where the local continuations are done using gotos and gcc's labels-as-values feature. This does remove some of the problems with the switch statement, but still does not record local variables. Others have implemented protothreads in C++, where a class object is used to store local variables, and by adding a C2C wrapper compiler that produces C code that stores and restores the local variables.
Protothreads were created to explore some of the finer points in the twilight zone between multithreading/coroutines and events/state machines. The intent was never to emulate continuations, coroutines, or threads but to find a less expensive way to achieve linear code flow. With protothreads, linear code flow can be achieved without having to store multiple thread stacks, which is important in many of the systems for which protothreads were originally intended. The switch-based implementation also has the added benefit of being possible use with any C compiler, which has been very useful as we have ported Contiki to a bunch of different platforms and C compilers.
But, yeah, the switch-based implementation of the protothreads concept can definitely be labelled as a hack. But - admit it - a beautiful hack! :)
Yes, they're a hack, but this is HACKer News, right? :-) More correctly, though, as Adam pointed out, the switch statement implementation of protothreads is a hack.
However, I'd like to also point out that it's a very useful hack. In the tiny embedded micros I work with, something like CPC would be much too heavy weight. Protothreads take 2 bytes of RAM per "thread", and you can even get that down to 1 byte if you use __COUNTER__ instead of __LINE__. Protothreads also have the huge advantage of working in regular C and C++, meaning standard tools just work.
However, I'd like to also point out that it's a very useful hack. In the tiny embedded micros I work with, something like CPC would be much too heavy weight. Protothreads take 2 bytes of RAM per "thread", and you can even get that down to 1 byte if you use __COUNTER__ instead of __LINE__. Protothreads also have the huge advantage of working in regular C and C++, meaning standard tools just work.
Thanks for explaining that. I wasn't aware Protothreads was such a hack, and so limited.
Aren't they both just modeled after the 2007 paper Events Can Make Sense that outlines Tame http://pdos.csail.mit.edu/papers/tame-usenix07.pdf
Definitely not: protothreads (2006) predates Tame (2007). But all of them are somehow (great-)grandchildren of Duff's device: http://www.lysator.liu.se/c/duffs-device.html
Even more so, over the years I've seen in the wild and had cause to roll similar multiple entry points to functions, so standard practice predates both those dates by a decade or two. It is always good to see it written down to share the idea to the next generation.
CPC is something I've longed for in the past. I've always thought C could do with just a couple more features related to function call and frame management to make it the ideal portable low level language.
CPC is something I've longed for in the past. I've always thought C could do with just a couple more features related to function call and frame management to make it the ideal portable low level language.
Of course they are similar, they both stole the concept from Lisp.
I especially like how in C# this asynchronous mode of execution is part of the language itself, and no code transformation tools (or macros) are necessary on the user end. I think this makes it much more accessible, both because it's immediately available, and because it avoids fragmentation. See also my NCD programming language [4], where asynchronous execution is an essential feature of the language.
[1] http://news.ycombinator.com/item?id=4736630
[2] http://tamejs.org/
[3] http://www.pps.univ-paris-diderot.fr/~kerneis/software/cpc/
[4] http://code.google.com/p/badvpn/wiki/NCD