[HN Gopher] Duff's Device
___________________________________________________________________
Duff's Device
Author : simonpure
Score : 66 points
Date : 2020-05-25 18:38 UTC (4 hours ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| lmilcin wrote:
| I have actually used this in production for cooperative
| multitasking framework for Verifone VX510.
|
| I needed this to run multiple stuff at the same time (for example
| printing while also doing network -- both serial devices on
| VX510).
|
| Could have done this with setjmp/longjmp but it would not be as
| fun:)
| adamnemecek wrote:
| Please don't use Duff's device. Look at how your favorite c std
| lib implements memcpy and think about that rather than this.
| ars wrote:
| It's a very fun historical article, but it's no longer worth it
| on modern CPUs, where it actually harms performance.
| marvy wrote:
| What's not worth it? Loop unrolling? Something else?
| chrisseaton wrote:
| Does duff's device create irreducible control flow? I
| couldn't tell you off the top of my head but seems likely and
| if it does that's a good reason to avoid as some modern
| compilers do not like irreducible control flow.
| tom_mellior wrote:
| Yes, it creates a loop with multiple entry points, which is
| irreducible. (I think it's even one of several equivalent
| definitions of irreducibility.)
| throwaway_pdp09 wrote:
| 'irriducible'?
| chrisseaton wrote:
| It comes from 'reduce' - I think it's spelt
| 'irreducible', but maybe you're American and I'm British.
| throwaway_pdp09 wrote:
| Made me smile. No, I'm questioning the meaning here. I
| have a vague inkling it's a property of the dataflow
| graph of a program, I'm just struggling to remember what.
| Is it literally that repeated collapses of basic node
| types (if/while/sequence) will end up with a single node?
| Basically 'does it properly nest'? Or is it something
| else? (and I'm a brit too BTW)
| chrisseaton wrote:
| Yes it means properly-nested, or really the same thing as
| 'structured' as in 'structured programming.' I'm sure
| there's some graph-theoretic definition but I don't know
| it off the top of my head.
| enriquto wrote:
| It's more a comment about the syntax of the C switch statement
| than about micro-optimization.
| klyrs wrote:
| There's two kinds of C programmers: those familiar with
| Duff's device, and those who wouldn't expect Duff's device to
| even compile.
| tedunangst wrote:
| Sounds like a benchmark is in order!
| x3blah wrote:
| https://raw.githubusercontent.com/lemire/fastbase64/master/s...
| j1elo wrote:
| Don't miss out on the brilliant link at the bottom - Adam
| Dunkels' Protothreads - Lightweight, Stackless Threads in C also
| uses nested switch/case statements [1].
|
| I learned about the theory with it, and used his library to
| implement cooperative multitasking on a bare metal embedded AVR C
| project. I wrote a task manager and dispatcher based on
| Protothreads, and that effort was what later made it simple for
| me to understand the JS async/await paradigm that would appear
| under my radar a couple years later.
|
| EDIT to add that I think the concepts might still apply, since
| these days I've seen things like stackless async coroutines
| discussed for Rust... didn't study those in detail yet, but I
| wouldn't be surprised if the basic concepts are the same.
|
| [1]: Current website: http://dunkels.com/adam/pt/
| dang wrote:
| See also:
|
| 2017 https://news.ycombinator.com/item?id=15679205 - particularly
| https://www.lysator.liu.se/c/duffs-device.html
|
| 2016 (a bit) https://news.ycombinator.com/item?id=12758686 and
| https://news.ycombinator.com/item?id=10830744
|
| 2015 https://news.ycombinator.com/item?id=10175901
|
| 2015 (in Go) https://news.ycombinator.com/item?id=8990742
|
| 2012 https://news.ycombinator.com/item?id=4360306 (note the
| personal anecdote)
|
| 2010 https://news.ycombinator.com/item?id=1896643
|
| 2009 https://news.ycombinator.com/item?id=761177
|
| 2008 https://news.ycombinator.com/item?id=195763
| api wrote:
| This is a fun language hack, but be aware that this is probably
| not good for performance in 2020. Nearly anything larger than a
| coffee machine microcontroller these days probably has
| instruction level parallelism and also operates more efficiently
| on larger data words. Obviously it depends on what you're trying
| to do but using this for any kind of iterative memory op is
| probably slow. It's also such an oddball construction that the
| compiler is not likely to be able to optimize it.
| throwaway_pdp09 wrote:
| Would a modern C compiler even permit that?
|
| The article does say " At the time of the device's invention this
| was the first edition of The C Programming Language which
| requires only that the body of the switch be a syntactically
| valid (compound) statement..." which implies it isn't valid now.
|
| Any correct parser based on any sane grammar should instantly
| choke on that.
| edflsafoiewq wrote:
| Yes, it's correct modern C. I'm not sure what that paragraph is
| supposed ot mean. AFAICT there is no difference between old and
| modern C in how the cases can appear in the body of the switch.
| Here is the first edition of _The C Programming Language_ on
| switch:
|
| > switch (expression) statement
|
| >The usual arithmetic conversion is performed on the
| expression, but the result must be int. The statement is
| typically compound. Any statement within the statement may be
| labeled with one or more case prefixes as follows
|
| > case constant_expression :
|
| https://archive.org/details/TheCProgrammingLanguageFirstEdit...
| chc4 wrote:
| While not a "pure" Duff's Device, Golang apparently does
| something similar with STOSD for an unrolled memcpy that it can
| call into at different points. I think it's really cute.
|
| https://twitter.com/mayahustle/status/1260678725257003008
___________________________________________________________________
(page generated 2020-05-25 23:00 UTC)