Sorting Nibbles in Swift

A couple of months back, John Regehr posted a challenge on his blog – write the fastest possible sorting algorithm for all the nibbles in a 64-bit word.

The problem is to sort the 4-bit pieces of a 64-bit word with (unsigned) smaller values towards the small end of the word. The nibble sort of `0xbadbeef` is `0xfeedbba000000000`. The function you implement will perform this sorting operation on a buffer of 1024 64-bit integers:

`void nibble_sort(unsigned long *buf);`

The challenge was in C, but it made me wonder about solving the same problem in Swift. Here’s a straight port of the supplied reference version in Swift:

```func read_nibble(w: UInt64, i: UInt64) -> UInt64 {
let res = w >> (i * 4)
return res & 0xf
}

func write_nibble(inout w: UInt64, i: UInt64, v: UInt64) {
var prom = v;
prom <<= (i * 4)
w |= prom
}

func nibble_sort_word_ref(var arg: UInt64) -> UInt64 {
for var i: UInt64 = 0; i < 16; ++i {
var min = i;
for var j = i+1; j < 16; ++j {
min = j
}
}
if (min != i) {
write_nibble(&arg, min, tmp)
}
}
return arg;
}

func nibble_sort_ref(buf: UnsafeMutablePointer<UInt64>) {
for var i=0; i<1024; i++ {
buf[i] = nibble_sort_word_ref(buf[i])
}
}
```

The first bit of good news is that on my machine, when compiled with `-Ounchecked`, this version performs with pretty much the same speed as the original C version. Sticking with `-O` instead gives up about ~20% performance, which is not too bad for the sake of safety.

So, this version has two functions to read and write the nibble at a given index, and a function to sort it using them. Get/set at a given index? That sounds a lot like a collection type. What if we were to wrap the word in a collection, and use `subscript` instead of the read/write functions? Something like this:

```struct NibbleCollection: MutableCollectionType {
var val: UInt64

var startIndex: UInt64 { return 0 }
var endIndex: UInt64 { return 16 }

subscript(idx: UInt64) -> UInt64 {
get {
return (val >> (idx*4)) & 0xf
}
set(n) {
let mask = 0xf << (idx * 4)
val |= n << (idx * 4)
}
}

typealias Generator = IndexingGenerator<NibbleCollection>
func generate() -> Generator { return Generator(self) }
}
```

Once you have this, you can then use the standard library sorting function on it to implement the challenge:

```func nibble_sort_word_col(arg: UInt64) -> UInt64 {
var col = NibbleCollection(val: arg)
sort(&col)
return col.val
}
```

“Does all this Collection overhead mean it won’t be as fast as the raw function implementation?” you might worry. But there really is no overhead – since `NibbleCollection` is a struct, not a class, it really isn’t anything more than the raw underlying `UInt64` and some functions. All of the scaffolding sloughs away at compile time, leaving you with pretty much identical code to the function-based version.

With one big difference: `Swift.sort` is way better than the reference sort implementation above.1 So this version outperforms it, both in Swift and in C. With `-O`, the collection version is faster than the Swift reference, and the same speed as the C version. With `-Ounchecked` it outperforms the C version by about 25%.

Which tells you two things you should bear in mind when writing Swift:

1. Structs implementing protocols, and generic functions, are a good way of getting abstraction without giving up performance.
2. Always check if the code you want exists as a library function. Using it won‘t just save time and make your code clearer, it could be better optimized than the version you might write.

Of course, the competitive entries in C were orders of magnitute faster than the reference version, using bit-twiddling techniques like bucket sorts and lookup tables that take advantage of the problem being constrained to values less than 16 held in a single word. But since Swift also supports most of the operations they use, many of them can be ported too. A quick and dirty translations I did of a couple of the simpler ones suggests that, like the reference version, Swift can match or almost match them in performance too.

1. Naming the two sort algorithms in question is an exercise for the reader. They might not be the one you’d guess first.

5 thoughts on “Sorting Nibbles in Swift”

1. […] Sorting Nibbles in Swift […]

2. […] In a talk last week at Swift Summit, I spoke a bit about Swift and performance, and about how structs and generic functions in Swift allow you to write high-level code without paying a significant performance penalty. This built on the example I posted a couple of weeks back about sorting nibbles in Swift. […]

3. Daeho says:

Maybe I’m missing something glaringly obvious… but shouldn’t the endIndex by 15, not 16?

• Indices on Swift collections follow the convention that the end index is “one past” the last value rather than the index of the last value.

4. […] A very interesting experiment on Swift performance. Including a nice surprise.. Sorting Nibbles in Swift […]