5 ms·

Tom Duff on Duff's Device (1988)

43 points by dv_says 11y ago

protomyth 11y ago
"A second poster tried the test, but botched the implementation, proving only that with diligence it is possible to make anything run slowly." This made me laugh. "with diligence it is possible to make anything run slowly" should be one of the truths carved into an obelisk outside every CompSci department or at least on a t-shirt.
AceJohnny2 11y ago
> (Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.) I'm really, really curious about what that code is.
- mikeash 11y ago
  This is just a guess, but perhaps something like: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
  - jhallenworld 11y ago
    This is a very useful technique for making event driven parsers. I remember being surprised that the case statements didn't all have to be in the same scoping level, but it's true.
  - nraynaud 11y ago
    I just used it a few minutes ago: https://github.com/nraynaud/webgcode/blob/gh-pages/interpolator/main.c#L150 https://github.com/nraynaud/webgcode/blob/gh-pages/interpola... https://github.com/nraynaud/webgcode/blob/gh-pages/interpolator/cnc.h#L111 https://github.com/nraynaud/webgcode/blob/gh-pages/interpola... One problem is the reset of the functions, I just created a makeshift exception, but I don't know how far I want to deviate form the norm. I still don't know if it's a good idea, but that's what personal projects are for.
userbinator 11y ago
I wonder what programmers at the time would think of CPUs eventually being so good at handling loops that unrolling changes from an optimisation technique to be performed manually, to one that compilers might sometimes do, to an anti-optimisation: http://www.agner.org/optimize/blog/read.php?i=142 http://www.agner.org/optimize/blog/read.php?i=142 It is so important to economize the use of the micro-op cache that I would give the advice never to unroll loops. http://lkml.iu.edu/hypermail/linux/kernel/0008.2/0171.html http://lkml.iu.edu/hypermail/linux/kernel/0008.2/0171.html by eliminating all instances of Duff's Device from the XFree86 4.0 server, the server shrunk in size by _half_ _a_ _megabyte_ (!!!), and was faster to boot
- CyberDildonics 11y ago
  Some of that can be attributed to the fact that there are multiple integer and floating point units, so the loop counter is often totally inconsequential.
- TheCoelacanth 11y ago
  It seems from his comments that the idea of a compiler being able to do it better in some circumstances wasn't completely outlandish. > Don't try to be smarter than an over-clever C compiler that recognizes loops that implement block move or block clear and compiles them into machine idioms.
CyberDildonics 11y ago
Funny that he is more famous for this than for inventing Porter-Duff compositing algebra, one of the cornerstones of modern image manipulation.
- versteegen 11y ago
  Thanks for mentioning this. I found a nice article about it and generalisation to blend modes here: http://ssp.impulsetrain.com/porterduff.html http://ssp.impulsetrain.com/porterduff.html

43 points by dv_says 11y ago

"A second poster tried the test, but botched the implementation, proving only that with diligence it is possible to make anything run slowly." This made me laugh. "with diligence it is possible to make anything run slowly" should be one of the truths carved into an obelisk outside every CompSci department or at least on a t-shirt.

AceJohnny2 11y ago

> (Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.) I'm really, really curious about what that code is.

mikeash 11y ago
This is just a guess, but perhaps something like: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
- jhallenworld 11y ago
  This is a very useful technique for making event driven parsers. I remember being surprised that the case statements didn't all have to be in the same scoping level, but it's true.
- nraynaud 11y ago
  I just used it a few minutes ago: https://github.com/nraynaud/webgcode/blob/gh-pages/interpolator/main.c#L150 https://github.com/nraynaud/webgcode/blob/gh-pages/interpola... https://github.com/nraynaud/webgcode/blob/gh-pages/interpolator/cnc.h#L111 https://github.com/nraynaud/webgcode/blob/gh-pages/interpola... One problem is the reset of the functions, I just created a makeshift exception, but I don't know how far I want to deviate form the norm. I still don't know if it's a good idea, but that's what personal projects are for.

userbinator 11y ago

I wonder what programmers at the time would think of CPUs eventually being so good at handling loops that unrolling changes from an optimisation technique to be performed manually, to one that compilers might sometimes do, to an anti-optimisation: http://www.agner.org/optimize/blog/read.php?i=142 http://www.agner.org/optimize/blog/read.php?i=142 It is so important to economize the use of the micro-op cache that I would give the advice never to unroll loops. http://lkml.iu.edu/hypermail/linux/kernel/0008.2/0171.html http://lkml.iu.edu/hypermail/linux/kernel/0008.2/0171.html by eliminating all instances of Duff's Device from the XFree86 4.0 server, the server shrunk in size by _half_ _a_ _megabyte_ (!!!), and was faster to boot

CyberDildonics 11y ago
Some of that can be attributed to the fact that there are multiple integer and floating point units, so the loop counter is often totally inconsequential.
TheCoelacanth 11y ago
It seems from his comments that the idea of a compiler being able to do it better in some circumstances wasn't completely outlandish. > Don't try to be smarter than an over-clever C compiler that recognizes loops that implement block move or block clear and compiles them into machine idioms.

CyberDildonics 11y ago

Funny that he is more famous for this than for inventing Porter-Duff compositing algebra, one of the cornerstones of modern image manipulation.

versteegen 11y ago
Thanks for mentioning this. I found a nice article about it and generalisation to blend modes here: http://ssp.impulsetrain.com/porterduff.html http://ssp.impulsetrain.com/porterduff.html