Duff's device in Swift

Question

We know that a Duff's device makes use of interlacing the structures of a fallthrough switch and a loop like:

send(to, from, count)
register short *to, *from;
register count;
{
    register n = (count + 7) / 8;
    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);
    }
}

Now, in Swif 2.1, switch-case control flows do not implicitly have fallthrough as we read in Swift docs:

No Implicit Fallthrough

In contrast with switch statements in C and Objective-C, switch statements in Swift do not fall through the bottom of each case and into the next one by default. Instead, the entire switch statement finishes its execution as soon as the first matching switch case is completed, without requiring an explicit break statement. This makes the switch statement safer and easier to use than in C, and avoids executing more than one switch case by mistake.

Now, given that there's a fallthrough clause to have explicitly a fallthrough side effect in Swift:

Fallthrough

Switch statements in Swift do not fall through the bottom of each case and into the next one. Instead, the entire switch statement completes its execution as soon as the first matching case is completed. By contrast, C requires you to insert an explicit break statement at the end of every switch case to prevent fallthrough. Avoiding default fallthrough means that Swift switch statements are much more concise and predictable than their counterparts in C, and thus they avoid executing multiple switch cases by mistake.

that is pretty much like:

let integerToDescribe = 5
var description = "The number \(integerToDescribe) is"
switch integerToDescribe {
case 2, 3, 5, 7, 11, 13, 17, 19:
    description += " a prime number, and also"
    fallthrough
default:
    description += " an integer."
}
print(description)
// prints "The number 5 is a prime number, and also an integer."

considering that as Wikipedia reminds to us, the devices comes out from the issue

A straightforward code to copy items from an array to a memory-mapped output register might look like this:
do {                          /* count > 0 assumed */
    *to = *from++;            /* "to" pointer is NOT incremented, see explanation below */
} while(--count > 0);

Which would be the exact implementation of a Duff's device in Swift?

This is just a language & coding question, it is not intended to be applied in real Swift applications.

Fallthrough is an essential aspect of Duff's device. Without it, I don't think there exists an exact implementation in Swift. In Swift, you can't even simulate fallthrough in a Switch statement, so you would have to use a series of `if then`statements instead. Not much point, I think. — Robert Harvey, Jan 25 '16 at 15:36
Eh... that's an optimization from 1983. Things like cache memories and branch prediction were barely invented, let alone highly optimized `memcpy` implementations. Why do you optimize code according to some 1980s algorithm and why do you think such things are still relevant today? — Lundin, Jan 25 '16 at 15:53
just a coding / language question, not a real implementation for something that should be relevant today. — loretoparisi, Jan 25 '16 at 16:03
@Lundin: I don't see anyone talking about any "optimization". I think it is perfectly clear form the question that it has nothing to do with optimization or even any real-life coding scenarios. This is an abstract question about flexibility of available language constructs. — AnT stands with Russia, Jan 25 '16 at 16:08
Duff's Device relies on two features of C's `switch` statements: (1) execution falls through `case` and `default` labels by default; (2) `case` and `default` labels for an `switch` can appear within a nested control structure (`if/else`, `while`, `do/while`, or `for`). Even if you can do (1) in Swift using the `fallthrough` directive, I'm assuming it doesn't support (2). — Ian Abbott, Jan 25 '16 at 16:40
@Lundin: Duff's device is not a memcpy, so an optimized memcpy won't help. (And a lot of memcpy optimizations boil down to loop unrolling, which is effectively what Duff's device does.) Duff's device can still be relevant in some domains, like embedded systems with microcontrollers. — Adrian McCarthy, Jan 25 '16 at 22:08
@AnT The only reason for writing obscure code like this in the 80s was optimization. It doesn't make sense to do it for any other purpose. — Lundin, Jan 26 '16 at 07:17
@AdrianMcCarthy Oh it is not a memcpy? Then please enlighten me about what it is. The only difference is you keep the same target destination, like a hardware register. As for microcontrollers: anyone who writes a memcpy for small microcontrollers, which relies heavily on division, is gravely incompetent. We can safely dismiss that code as completely obsolete practice. — Lundin, Jan 26 '16 at 07:19
@Lundin I'm not sure it is "a completely obsolete practice". Take a look at `Open and Efficient Type Switch for C++`, `OOPSLA 2012` - http://www.stroustrup.com/OOPSLA-typeswitch-draft.pdf and the `Memoization Device` approach proposed at page 8 fully inspired by "Duff's Device" by `Bjarne Stroustrup`. We were in `2012` here ;) — loretoparisi, Jan 26 '16 at 09:05
@Lundin: The fact that it's copying to a hardware register makes it quite distinct from a memcpy. Besides loop unrolling (which is what Duff's device is all about), the other common memcpy optimization is to move larger units of data at a time, something you can't do if your destination is a 1-byte hardware register. As for the division, it's one integer division and one modulus outside the loop. Since the denominator is a power of two, most compilers are going to translate them into a bitshift and mask--not a problem on a microcontroller. Duff's device is perfectly cromulent today. — Adrian McCarthy, Jan 26 '16 at 17:18
For sure, Swift would not allows that kind of code to compile. In fact, **Duff's device** is essentially an oversight (accident) that should never have compile. At some point, someone figure out that it could be used for loop unrolling optimization so finally the hole in the langage was kept. Today, this is mostly irrelevant as compiler are much more advanced and needed optimization are very different too because the architecture changed a lot with multiple core, caches, pipeline etc. Also in modern language, you are not as close as to the actual CPU instructions. — Phil1970, Jul 10 '19 at 01:43

score 3 · Answer 1 · answered Jul 09 '19 at 23:14

Duffs device is about more than optimisation. If you look at https://research.swtch.com/duff it is a discussion of implementing co-routines using this mechanism (see paragraph 8 for a comment from Mr. Duff).

If you try to write a portable co-routine package without this ability. You will end up in assembly or re-writing jmpbuf entries [ neither is portable ].

Modern languages like go and swift have more restrictive memory models than C, so this sort of mechanism (I imagine) would cause all sorts of tracking problems. Even the lambda-like block structure in clang,gcc end up intertwined with thread local storage, and can cause all sorts of havoc unless you stick to trivial applications.

score 2 · Answer 2 · answered Dec 16 '17 at 18:47

You express your intent in the highest level code possible, and trust the Swift compiler to optimize it for you, instead of trying to optimize it yourself. Swift is a high level language. You don't do low level loop unrolling in a high level language.

And in Swift, especially, you don't need to worry about copying arrays (the original application of Duff's Device) because Swift pretends to copy an array whenever you assign it, using "copy on write." This means that it will use the same array for two variables as long as you are just reading from them, but as soon as you modify one of them, it will create a duplicate in the background.

For example, from https://developer.apple.com/documentation/swift/array Modifying Copies of Arrays

Each array has an independent value that includes the values of all
of its elements. For simple types such as integers and other structures,
this means that when you change a value in one array, the value of that
element does not change in any copies of the array. For example:

var numbers = [1, 2, 3, 4, 5]
var numbersCopy = numbers
numbers[0] = 100
print(numbers)
// Prints "[100, 2, 3, 4, 5]"
print(numbersCopy)
// Prints "[1, 2, 3, 4, 5]"

Duff's device in Swift

2 Answers2