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.

Alcoholometer

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 thenstatements instead. Not much point, I think. – Mol

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? – Saccharify

just a coding / language question, not a real implementation for something that should be relevant today. – Alcoholometer

@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. – Seventieth

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). – Panto

@AnT exactly, thanks, that was my aim. – Alcoholometer

@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. – Troglodyte

@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. – Saccharify

@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. – Saccharify

Btw DMA has also been invented since 1983. – Saccharify

@Saccharify I'm not sure it is "a completely obsolete practice". Take a look at Open and Efficient Type Switch for C++, OOPSLA 2012 - 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 ;) – Alcoholometer

@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. – Troglodyte

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. – Fawnia

Answer 1

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.

Bilocular

Answer 2

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]"

Sams