Duff’s Device in 2021

Correct. Duff's device is for MMIO which means it needs to do explicit memory writes. We are not doing arithmetic here, we're doing I/O. In C (and C++) you express that by labelling the variable volatile.

Today MMIO is very slow and so you just don't need unrolling. Or I guess from another perspective, MMIO isn't as much faster as absolutely everything else is now, and so again you don't need unrolling. Your CPU can do some arithmetic, make a conditional jump, and still schedule the next MMIO write in plenty of time. Therefore Duff's device is now irrelevant.

The ++*x is completely toxic in the context Tom Duff wrote this - where we want actual writes, because then it actually amounts to this:

  int tmp = read_mmio();
  tmp++;
  write_mmio(tmp);

And immediately you should be filled with dread, who said we could read this MMIO register? What happen if the contents of the MMIO register change while we're twiddling tmp? This all seems like a very bad idea.

What's more curious than the irreducability issue is, how on earth does the syntax ever get accepted by the parser?

I mean the lex/yacc syntax has to reflect the nestability of the while/switch [1], ditto if you do recursive descent, so how is it possible this even parses?

[1] original and weirder version here https://en.wikipedia.org/wiki/Duff%27s_device#Original_versi...

>> The biggest problem with this technique, from an optimization perspective, is that it creates an irreducible control-flow graph.

The technique is considered obsolete with todays compilers specifically because they can do loop optimizations like this without writing strange C code.

OTOH you never know what those wacky compiler guys are going to do. For example, it seems GCC hasn't been doing any vectorization on x86-64 with standard -O2 even though the ISA has supported SSE2 as a minimum from day one. This is being fixed (to some extent) in the next release.

Are those results useless?

The question posed early in the blog was whether Duff's Device is still relevant in 2021. The fact that the compiler can completely elide the loop without it but cannot with it is a pretty good indicator that it's likely to cause more harm than good.

It might prevent inlining of a function call in the loop body, which would make a loop much, much slower to execute. It will make the loop body larger (even without inlining) and likely cause an increase in cache misses. It will be unpredictable based on build: an unrelated change somewhere else might misalign it with a cache line. Different CPUs might have different cache behaviours and perform differently.

The right view on this sort of thing hasn't changed for decades: don't optimize prematurely. Trust your compiler, check it with profiling, look first for algorithmic improvements because you can gain FAR more converting an O(n^2) algorithm to an O(nlogn) than you can by unrolling a loop. Duff's Device is obsolete in all but a vanishingly tiny number of edge cases.

This.

For trivial loop, Both GCC and clang optimize away the entire BasicLoop, but clang failed to optimize away the entire DuffDevice, while GCC did. Thus, the only thing doing the work is clang's Duff Device.

But even then, both GCC and clang optimize the BasicLoop function itself into just single add operation (data += loop_size) while it actually loops on the duff device function (though as mentioned, these functions weren't called from the benchmark)

The thing is duffs device is about IO, so the loop cannot be optimized away as it isn't a pure function. The example code though is a pure function and so the compile is justified in optimizing it away.

We have long known that in general compilers are better at optimization than humans so you should write readable code until a profiler shows otherwise. However there are cases where the compiler doesn't make an optimization. There are sometimes corner cases that the compiler can't figure out doesn't apply to you, so manually doing the optimization might work. These cases need to be re-evaluated with every CPU change, and every compiler upgrade though.

Nothing above says if duff's device applies to not though. Duff's device is very likely to hit a corner cases where the compiler isn't sure if it can safely apply optimizations so it won't. As such I wouldn't be surprised if it is still relevant. (though mostly on embedded systems where we don't have nearly as fast of CPUs as more common computers)

I'm a prolific user of Duff's device for poor man's coroutines in C, but in non-toy applications I do try to isolate the behavior to discrete functional tasks and entirely behind a simple, conventional API. For example, implementing a single-function iterator using a generator pattern: https://github.com/wahern/lunix/blob/36c2107/src/unix-getopt... IOW, I avoid the urge to encapsulate the magic in a library abstraction so it can be reused (and abused) everywhere. There's no spooky action at a distance--you can figure out the behavior from the surrounding code, without having to pour through internal library code (even just hiding stuff in a header can be confusing). The details remain entirely irrelevant to callers. And I minimize opportunities for doing things I might regret (and have regretted), like implementing and relying upon a bespoke threading framework =)

On more than one occasion I wanted to write:

    switch (foo) {
        if (0) {
    case X:
            /* X-specific code */
        } else {
    case Y:
            /* Y-specific code */
        }
        /* common code for X and Y */
        break;
    }

Context here is embedded: I wrote an entire I2C driver on AVR using protothreads. This was so I could just call a single update function in my main loop and it would handle all the various delays.

Do not recommend.

If I had my time again, I would do it with a explicit state machine that runs in the I2C interrupt handler, and a submission and response queue accessed by the main app loop (the equivalent of "userland" for non-embedded folks).

One cool use I saw of it was in the instruction decoder for bochs. Duffs device is really nice for decoding instruction sets that are not necessarily regular in size (such as x86).

I still hope they'll open source it one day. I never really got to use it in anger, and I bet that when you use PGO all the compilers end up pretty similar in the "real world" but it would be a shame for all the work to be lost

> just hand code the vectorization/assembly yourself.

Yes, shoot portability in the foot so you can keep your code free of well defined language constructs.

If your operations are much heavier, then the cost of the loop condition becomes negligible. And if they're not as heavy as you thought (because the compiler's better at logic puzzles than you!), then you've wasted a whole lot more energy than those loop conditions would have.

The loop size is all that matters. The thing that's being optimized is just:

  for (int i = 0; i < loop_size; i++) {
    some_work();
  }

Whatever some_work may be you want to unroll the loop to avoid the jumps. It could be an operation like:

  c[i] = a[i] + b[i]

In which case you'd do like you suggest. But it could also just be some repeated operation on an entire data set, like in a simulation where you want to run loop_size iterations.

>There needs to be a dependency on the index for duff's device to work right?

For it to work "right" the work inside the loop has to be quite minor. The point being that it saves on cpu cycles by reducing the number of times it does i < loop_size, i++, and the number of times it has to branch back to the beginning of the loop. It's almost always some kind of memory copy, or a simple read, lookup, write in which the inside of the loop will complete in a few cpu cycles.

If the work inside the loop is 100x the cost of implementing the loop there is no point.

Yes, but instead of performing a loop control for every computation() it is only performed once every four computation()s.