I’ve been doing a lot more server-side programming in the last few years. Being able to write Swift on both sides is a real joy. I have a client with whom I’ve built a reasonably full-featured social app in Vapor, and all my personal stuff has been using Meridian, which has been going great. (I will have some contracting availability for server-side Swift coming up soon, so definitely get in touch if you have a project!)

However, one part of the process that I don’t enjoy much is using an ORM. There’s too much magic when working with them. I feel disconnected from the queries that are being run, and it’s too easy to accidentally add an n+1 query. I also don’t like how it turns a relational system into an object graph — I’d much prefer to work in terms of records with related IDs, rather than objects with children.

ORMs run some of the biggest sites and systems in the world — if you like them, keep using them. If they make you feel weird too, the rest of the post might be for you.

ORMs do give you one thing that is great: a single source of truth, which is the model definition in the application code. However, this single source of truth is not always trustworthy — there’s nothing to keep it in-line with what’s actually in the database.

For example, if a field in my model object goes from being optional to non-optional, things could work smoothly for almost every row, but if some old row has a stray null in the database, decoding the model object will fail and cause my application to do something unexpected.

The real problem here is that my application code is always changing and a home for bugs.

As much as I distrust my own application code, I’ve come to trust Postgres. Postgres is a reliable and sensible choice for a backend database. Postgres is laden with great features — nullability, strong foreign keys, data blobs, performant unbounded text, JSON, extensions for UUIDs, GIS, and on and on. I just love it. I use it for everything, and far prefer it to other options.

Postgres’s constraint system feels like a warm blanket in the same way that Swift’s type system does.

  • If a field is never supposed to be null, you make it NOT NULL and you’re set.
  • If a field is a foreign key for for another table, mark it so and you won’t be able to delete a referenced row without deleting the referenced row (unless you choose some other behavior).
  • If a field has arbitrary computable constraints (like a score that must be between 0 and 100), you can add those, too.

What I want is a way to marry Postgres’s constraints to Swift’s type system — some way to propogate Postgres’s guarantees into my own type system.

After watching a Gary Bernhardt screencast (video, 18m, corresponding blog post), I saw the path forward. (If you’ve got 18 minutes, watch this talk. It’s a wonder.)

Gary shows how he uses types (in TypeScript) to make a change flow from the database all the way through to the UI, using a TypeScript tool called schemats, which creates simple interfaces that represent each table. These simple structures can be decoded easily and always represent the state of the database.

I ported schemats to Swift, to bring this same strategy to our favorite language. It’s called SchemaSwift. Working with it is pretty straightforward:

SchemaSwift \
    --url="<POSTGRES_URL>" \
    --override blog_posts.category=Category \
    --output ~/Desktop/DatabaseModels.generated.swift \

When you run it, out pops a file with all your tables, represented as Swift structs:

// Generated code:

struct BlogPost: Codable {
    static let tableName = "blog_posts"

    let id: UUID
    let content: String
    let authorID: UUID
    let category: Category?

    enum CodingKeys: String, CodingKey {
        case id = "id"
        case content = "content"
        case author = "author_id"
        case category = "category"
    }
}

The types it can infer as native Swift values are automatically handled, and you can override other fields with your own custom types. Nullability/optionals are brought over, so you’ll never decode an honest value when the database can potentially have a null in it. Postgres enums are turned into Swift enums as well.

It slots really nicely into Vapor’s SQLKit, using Codable:

let users = try db.select()
    ...
    .all(decoding: BlogPost.self)
    .wait()

(I also helped add support for this kind of decoding to another Swift Postgres libary. We have a great community.)

I’ve been using the tool for over 3 years now (I know, I’ve been very remiss in my blogging) and it’s been going great. Because you can see the output of the tool before you commit it, there’s very little risk in using it.

One final component that would normally be handled by ORM is migrations. For that, I want to explore mig, which would fill this gap nicely.

There’s plenty of future work here — running this at build time on the server (so that your build literally won’t complete if it’s building against a database that it can’t talk to!), using SPM’s extensible build tools, storing settings in a JSON file in your git root, type name prefixes and suffixes, and a module to hold all the generated code — these are all appealing ideas. If you end up needing or implementing one of these features, definitely drop me a line! I would love to integrate it.

RGB kind of sucks.

RGB, not unlike ASCII, memory addresses, and having 86,400 seconds in day, is one of those things that makes programming a little simpler for a bit, until it doesn’t anymore.

In theory, RGB is a group of color spaces that lets you tell the display how much voltage each subpixel needs. However, in practice, we now have phones with displays that let you show more than 100% red, which is a new type of red called super red. We have other displays that have twice as much blue as red or green. Your RGB values are not corresponding to display voltages and they probably haven’t for a while now.

RGB is also hard to think about. Red, green, and blue additive light don’t behave like much that we’re used to — you can see the individual colors up close but as you get further away, they blend together and you start to see only one color. From far enough away, you can’t convince your mind that there are three lights. You’re currently looking at millions of tiny little 3 light arrays, and yet the effect is so totalizing that you almost never think about it.

Finally, RGB is hard to manipulate. If you start from black, you can increase the amount of “red” in an RGB color picker, which will make things more red. So far so good. Then you start increasing the “green”, and you get…yellow? This is not a very intuitive color space to navigate around. There are other representations of colors that lend themselves to being changed more easily.

Colors for Years

I have a personal app where I need to show a graph of some years. Each year needs a different color on the graph, and so every new year I go into the code, find a nice new color for the new year, and deploy the app. How many years am I going to do this for until I find an algorithm with which to automate it?

I need some colors that are a) arbitrary feeling, b) nice looking, and c) determined purely by an integer for the year. We need to implement a function like this:

func color(for year: Int) -> Color

RGB can really only satisfy the first of my criteria — it can make random colors with random numbers:

Color(red: .random(in: 0..<1), blue: .random(in: 0..<1), green: .random(in: 0..<1))

Unfortunately, colors generated like this look really bad. They often come out muddy and ruddy, and generating more than one color doesn’t come with any pattern or structure. The colors are all over the place.

This is a structural problem with RGB. RGB is focused on how color is produced, rather than how it’s perceived.

Fortunately, the solution to this problem is well documented. There are a few blog posts out there (warning: JavaScript) that lay out an approach. The idea is this: by using a hue based color space, like HSL, you can hold two parameters constant (saturation and lightness), and modify only the hue, giving you multiple colors that live in the same “family”.

(There are subtle differences between HSL, HSB, HSV, and HWB, but the hue rotation is basically the same in all of the color models, and any of them will work well with this technique.)

For example, using 0.8 for both saturation and lightness gives you nice pastels:

Color(hue: .random(in: 0..<360), saturation: 0.8, lightness: 0.8)

You can play with this color picker; drag the “hue” slider to see lots of colors in this family.

On the other hand, 0.6 for the saturation and 0.5 for the lightness gives you more robust colors:

Color(hue: .random(in: 0..<360), saturation: 0.6, lightness: 0.5)

This color picker shows examples of these colors.

Astute readers will note that, while Apple’s own APIs take a number from 0 to 1, this fake initializer I made expects a hue from 0 to 360. I find this to be more illustrative, because this value represents some number of degrees. There’s a physical analogy here to a hue circle. Circles loop back on themselves, and therefore 359º is basically the same color as 1º. This lets you overshoot the end of the hue circle and mod by 360º to get back to a reasonable color.

This lets us implement most of our color(for year: Int) function.

func color(for year: Int) -> Color {
	let spacing = ...
	return Color(hue: (year * spacing) % 360, saturation: 0.8, lightness: 0.5)
}

The spacing represents the number of degrees to go around the hue wheel each time we need to pick the next color.

What is the optimal number to chose here?

Rotating in Hue Space

If we make this angle too close to zero, the colors will be too close together on the hue wheel, making them too similar. However, if we make it too close to 360º (a full revolution), once the degrees are modded by 360, they’ll still be too similar, except they’ll go backwards around the hue wheel. Maybe we want to try 180º? That makes every other color the exact same, so that’s not quite right either.

In fact, any rotation that divides evenly into 360º will result in repeats after a while. And 360 has a lot of factors!

One solution is to space things out by the 360 divided by the number of years we have, but then the colors would change every time there’s a new year. It makes a rainbow, which, while it does look nice, doesn’t quite have the random look I’m going for.

However, there’s a better way to do this, and the answer is in a YouTube video I watched over 10 years ago. The remarkable Vi Hart published a series of videos (one, two, three) about how plants need to grow their new leaves in such a way that they won’t be blocked by the leaves above, which lets them receive maximum sunlight. The second video in the series is where the relevant bit is.

The number of degrees around the stalk that a plant decides to grow its next leaf from is the exact number we are looking for: some fraction of a turn to rotate by which will give us non-overlapping leaves — I mean, colors.

Because any rational number will result in repeat colors — or overlapping leaves — she seeks an irrational number; ideally the “most” irrational number. She finds it in ϕ, or roughly 1.618. We want to go 1/1.618th of the hue circle each time we need a new color, and this will give us the colors we want.

func color(for year: Int) -> Color {
	let spacing = 360/1.618
	return Color(hue: (year * spacing) % 360, saturation: 0.8, lightness: 0.5)
}

If the colors are not to your liking, you can add a little extra rotation by adding a phase shift to the equation:

func color(for year: Int) -> Color {
	let spacing = 360/1.618
	return Color(hue: 300 + (year * spacing) % 360, saturation: 0.8, lightness: 0.5)
}

This function meets our criteria: colors that come out of it a) are arbitrary, b) look pretty good, and c) are purely determined by the year.

A Step Further

If your only goal is some simple colors for a prototype or for a side project, what I’ve covered so far will suffice. But if you want to use this in more serious and wide-ranging applications, you can take one more step.

HSL has some some serious drawbacks. It, like RGB, was designed for ease of computation rather than precision in the underlying colors. Specifically, when rotating the hue value (which is what we’re doing with this technique), you’ll find that some hues are tinted much lighter than others, even holding saturation and lightness constant. These colors look lighter, even though they’re technically the same “lightness”.

The LCh color space (luminance, chroma, hue) solves this problem. As far as I can tell, it’s the gold standard for colors on a display. It gives you perceptual uniformity, which lets you rotate the hue and get colors that are even more similar to each other than you’d get with HSL; it also confers some benefits when it comes to contrast for reading text.

In fact, if you look closely at the colors above (which represent the colors for the years 2015–2023 using our algorithm), that lime green is looking a little muted relative to its purple neighbor.

You can play with an LCh color picker here. To make LCh work with UIColor, you can use these four useful gists.

Using LCh to generate my colors with the hue rotation technique above yielded beautiful colors.

func color(for year: Int) -> Color {
	let spacing = 360/1.618
	return Color(luminance: 0.7, chroma: 120, hue: 300 + (year * spacing) % 360)
}

These colors all have similar lightness to me, and they look great for something totally procedurally generated. They’re vibrant, uniform, and wonderful.

The model you choose to inhabit creates constraints that you may not have intended to be constrained by. Any color from any of these color spaces can be (more or less) translated to any other color space with a little bit of math, so the colors we ended up with could be written in terms of red, green, and blue values (again, hand-waving a little here). But while RGB can represent these colors, that doesn’t mean you can easily move through the space in a way that yields colors that look good together. Picking the right color space to start out makes the problem at least tractable.

Tractable, but still not solved. These arbitrary beautiful colors can be generated using a process stochastically discovered by evolution, discovered by scientists in 1830, and brought to practice using a robust set of web standards that let me show them to you in a browser.

At the end of it all, a plant’s desire for sunlight held the key to making nice colors for my little chart.

I recently had occasion to give my old Sudoku talk again. For those who haven’t seen the talk, I live-code my way through a Sudoku problem and together we write a solver that can solve any valid grid. It’s a very fun talk to give and I hope it’s enjoyable to watch as well.

While preparing for the talk, I took the chance to update and modernize some of the code.

I was able to use multi-line strings to represent the grid in a graphical way and get rid of an old helper that is now part of the standard library as allSatisfy(_:). More important than those changes, though, I was able to incorporate the new “primary associated types” for protocols, which had a way bigger impact on the code than I expected.

Let dig in. Here’s how the grid is structured:

public struct Grid {
     private var rows: [[Cell]]
}

There are a few ways to represent the data, but I chose an array of arrays, which represent the rows of the grid.

However, the underlying data structure is not as important, because the primary mode of interaction with this object is through the “units” of the grid, like rows, columns, and boxes. Here are some helpers to extract those:

extension Grid { 
     public var cells: [Cell] {
         return Array(rows.joined())
     }

     public func row(forIndex index: Int) -> [Cell] {
         let rowIndex = index / 9
         return rows[rowIndex]
     }

     public func column(forIndex index: Int) -> [Cell] {
         let columnIndex = index % 9
         return self.rows.map({ row in
             return row[columnIndex]
         })
     }

     public func box(forIndex index: Int) -> [Cell] {
         let rowIndex = index / 9
         let columnIndex = index % 9
         let boxColumnIndex = columnIndex / 3
         let boxRowIndex = rowIndex / 3
         return (0..<3).flatMap({ rowOffset in
             return self.rows[boxRowIndex*3+rowOffset][boxColumnIndex*3..<boxColumnIndex*3+3]
         })
     }
}

The box function is definitely the most daunting here, but what I want to look at here is the return types of all these functions. They all return arrays. Every time you request any of these, the relevant data is copied into a new array. This happens so many times during the solve that it starts to add up. For example, isSolved looks like this:

 public var isSolved: Bool {
     return cells.allSatisfy({ $0.isSettled })
 }

It asks for all the cells in the grid, which creates an 81-cell array, copies all the data to it, and then iterates that array exactly one time, looking for a cell that isn’t settled.

Before Swift 5.7, for the cells property, you could return some Collection. This enables you get rid of the of conversion to an Array, which saves you the copying.

 public var cells: some Collection {
     return rows.joined()
 }

Sadly, this pre-Swift-5.7 code is nearly useless. Even though Swift can infer the full return type of this function, the contract with external callers doesn’t include the type of the element. They get to know it’s a collection and that it has some element type, but not what the element is. They have to use it as an opaque value. It was a pretty big shortcoming when working with the some keyword.

Swift 5.7 changes all that. Protocols can now provide some “primary” associated types, which callers can rely on using the angle-bracket generics syntax that we all know and love:

 public var cells: some Collection<Cell> {
     return rows.joined()
 }

This is huge. Now, since .joined() produces a “lazy” collection, the collection stays lazy, and doesn’t have to copy its items to a new array. Less work, big upside, and the contract with callers includes the element type.

Now, you could say this isn’t anything new. After all, I could have written the concrete type of rows.joined() for the return type of the cells property, and seen the same benefit:

 public var cells: JoinedSequence<[Cell]> {
     return rows.joined()
 }

Not too bad, right? However, here’s what the return type for box(forIndex:) looks like when you add a .lazy to get the intended performance:

public func box(forIndex index: Int) -> LazySequence<
    FlattenSequence<
        LazyMapSequence<
            LazySequence<(Range<Int>)>.Elements,
            ArraySlice<Cell>
        >
    >
> {
    let rowIndex = index / 9
    let columnIndex = index % 9
    let boxColumnIndex = columnIndex / 3
    let boxRowIndex = rowIndex / 3
    return (0..<3).lazy.flatMap({ rowOffset in
        return self.rows[boxRowIndex*3+rowOffset][boxColumnIndex*3..<boxColumnIndex*3+3]
    })
}

This isn’t usable. Not only is it hideous, these are implementation details, fully on display for the world to see. If you ever change the implementation of the function or the internal structure of the Grid type, you’ll have to change the return type as well. If this was a library, callers could even rely on details of the return type that you didn’t intend to expose.

The typical pre-5.7 way around the problem of messy return types was to use AnyCollection. Using AnyCollection has performance trade offs though, since it boxes its value, slowing down accesses and other operations.

How bad is that trade off? My expectation was that not returning an Array and returning an AnyCollection instead (which helps you avoid the expensive copy) would get you almost all of the way there. However, it turns out that you get about a 15% improvement in the solver’s runtime with AnyCollection. Switching to some Collection<Cell> gets you an additional 15% improvement. This means that boxing up the collection is about half as bad as fully copying every item to a new buffer. These are ultimately pretty short arrays (under 100 items each) so algorithms that operate on bigger data will benefit even more from these tweaks.

Another lesson (that I always feel like I have to learn afresh) is that you shouldn’t make assumptions about performance. Always profile! Your intuitions are fallible.

So here’s all of the helpers, returning some Collection<Cell> with the new syntax:

public var cells: some Collection<Cell> {
    return rows.joined()
}

public func row(forIndex index: Int) -> some Collection<Cell> {
    let rowIndex = index / 9
    return rows[rowIndex]
}

public func column(forIndex index: Int) -> some Collection<Cell> {
    let columnIndex = index % 9
    return self.rows.lazy.map({ row in
        return row[columnIndex]
    })
}

public func box(forIndex index: Int) -> some Collection<Cell> {
    let rowIndex = index / 9
    let columnIndex = index % 9
    let boxColumnIndex = columnIndex / 3
    let boxRowIndex = rowIndex / 3
    return (0..<3).lazy.flatMap({ rowOffset in
        return self.rows[boxRowIndex*3+rowOffset][boxColumnIndex*3..<boxColumnIndex*3+3]
    })
}

The code is nicer, better reflects its intent, and hides implementation details from the caller. These are all worthwhile ends in themselves, but we also see substantial performance improvements. This feature is a huge boon for collection-heavy code. By making the simple thing the fast thing and the safe thing for libraries you end up with a win on all fronts.

Here’s a fun experiment: if your app has a designer, ask them how many colors they think are in your app. Then, count the number of colors that you actually use in your app. The bigger the app, the more comical the difference will be.

I’ve got a solution for this which is pretty fun to boot. You should name your colors.

I find that a lot of people do a good job picking colors, but when it comes time to put those colors into practice, the names that get picked are somewhat boring. UIColor.gray40? .appRed? Where is the joy in that? Instead of really generic names, try to find short, unique, fun names for each color.

Finding names can be a challenge. Fortunately, there are tools that can help. For example, if you have a hex code, you can plug it into a website like Chirag Mehta’s Name that Color, Robert Cooper’s Color Name or colornames, the last of which seeks to name every single color (to sometimes hilarious effect). There’s also a GitHub repo with 30,000 colors in it that even has a public API for retrieving color names.

From those sites, you’ll get a name, which you may or may not like. If you don’t like the name, you can use the color picker to explore nearby names in the colorspace and try to find a name you you do like.

For example, given #3FAC38, I see “Green Seduction”, “Apple”, and “Grass Stain Green”, on each of the three websites linked above. Exploring a little bit, I can find names like Clover, Lima, or Hedge, any of which I think make reasonable names.

Another random color: #174FC5 gives “Denim”, “Mourning Blue”, and “Indigo Fork”. Denim is quite good, but we can also find Pacific, Sapphire, and Mariner if we want more options.

A great name is usually one word (which makes it short to type and easy to say), very different from the names of any other colors in your app, and is evocative. You want to feel the color as much as possible when you read its name.

The name doesn’t even really have to mean the color, as long as it feels good. For example, there was a blueish color in an app that we called “bunting” which I think we got from the Indigo bunting. We kept the “bunting” and tossed the indigo, even though you would think the other way makes more sense. Do what feels good.

Why name your colors at all? If I’m being completely honest, I mostly do it because it makes my work slightly more fun. You can find practical benefits, however: a small one is that they’re a lot easier to remember when writing code and easier to visualize when reading code.

A bigger benefit is that it forces you to stick to a color palette with a fixed number of colors. If your designer uses a new one in a design (an accident, I’m sure), you can innocuously ask them to name it, which either forces them to think hard about whether they want to add a new color to the roster, or makes them update the mock to reuse an existing color.

To close, a note on grays: I find that in practice, an app has more grays than any other color, and so this is the part that you’ll spend the most time in. Great gray color names come from metals and stones (“silver”, “boulder”, “slate”, “obsidian” “granite”), atmospheric conditions (“mist”, “fog”, “smoke”, “cloud”), and animals (“panther”, “dove”, “wolf”), but feel it out. You’ll find some good names.

Async/await is here!

Five (5!!) years ago, I wrote about what async/await might look like in Swift:

async func getCurrentUsersFollowers() throws -> [User] {
    let user = try await APIClient.getCurrentUser()
    let followers = try await APIClient.getFollowers(for: user)
    return followers
}

I put the async keyword in the wrong place (it actually goes next to the throws), but otherwise, pretty close to the final feature!

Today, I want to look at adopting some of the new async/await features. I have an app that’s already on iOS 15, so it’s a great testbed for these goodies. One of the parts of this app requires a download progress bar.

Normally, the easiest way to build a progress bar is to observe the progress property on the URLSessionDataTask object that you get back when setting up a request:

let task = self.dataTask(with: urlRequest) { (data, response, error) in
    ...
}
self.observation = task.progress.observe(\.fractionCompleted) { progress, change in
    ...
}
task.resume()

Unfortunately, the await-able methods on URLSession don’t return a task anymore, since they just return the thing you want, in an async fashion:

func data(from url: URL, delegate: URLSessionTaskDelegate? = nil) async throws -> (Data, URLResponse)

One would think the URLSessionTaskDelegate would have some affordance that calls you back when new bytes come in, but if that exists, I couldn’t find it.

However, iOS 15 brings a new API that can be used for this purpose — a byte-by-byte asynchronous for loop that can do something every time a new byte comes in from the network — called AsyncBytes.

Using it is a little strange, so I wanted to detail my experience using it. The first thing I had to do was kick off the request.

let (asyncBytes, urlResponse) = try await URLSession.shared.bytes(for: URLRequest(url: url))

This returns two things in a tuple: the asynchronously iterable AsyncBytes and a URLResponse. The URLRepsonse is kind of like the header for the HTTP request. I can get things like the mimeType, a suggestedFilename, and, since my goal is to keep track of progress, the expectedContentLength.

let length = Int(urlResponse.expectedContentLength)

Next, before I could await any bytes, I need to set up a place to put them. Because I now know how many bytes I’m expecting, I can even reserve some capacity in my new buffer so that it doesn’t have too many resizes.

let length = Int(urlResponse.expectedContentLength)
var data = Data()
data.reserveCapacity(length)

Now, with all that set up, I can await bytes, and store them as they come in:

for try await byte in asyncBytes {
    data.append(byte)
}

This for loop is a little different from any for loop you’ve ever written before. asyncBytes produces bytes, and calls the for loop’s scope every time it has something to give it. When it’s out of bytes, the for loop is over and execution continues past the for loop.

One question that this API raises: why does it call your block with every byte? The (very) old NSURLConnectionDelegate would give you updates with chunks of data, so why the change? I too was a little confused about this, but at the end of the day, any API you call with a chunk of data is just going to have a byte-by-byte for loop inside it, iterating over the bytes and copying them somewhere or manipulating them somehow.

Now that I have the basic structure of my data downloader, I can add support for progress. It’s just a for loop, so I can calculate the percent downloaded for each cycle of the for loop and assign it to a property.

for try await byte in asyncBytes {
    data.append(byte)
    self.downloadProgress = Double(data.count) / Double(length)
}

In this case, self.downloadProgress is some SwiftUI @State, and it turns out assigning a new value to that property slows the download by 500%. Not great.

I think this example highlights something important about this new API. The file I was trying to download was about 20MB. That means my for loop is going to spin 20 million times. Because of that, it’s extremely sensitive to any slow tasks that take place in the loop. If you do something that is normally pretty fast — let’s say 1 microsecond — 20 million of those will take 20 seconds. This loop is tight.

My next instinct was to read the data every tick, but only write to it every time the percentage changed.

for try await byte in asyncBytes {
    data.append(byte)
    let currentProgress = Double(data.count) / Double(length)

    if Int(self.downloadPercentage * 100) != Int(currentProgress * 100) {
        self.downloadPercentage = currentProgress
    }
}

This, sadly, also moved at a crawl. Even just reading some @State from SwiftUI is too slow for this loop.

The last thing I did, which did work, is to keep a local variable for the progress, and then only update the progress in SwiftUI when the fastRunningProgress had advanced by a percent.

var fastRunningProgress: Double = 0
for try await byte in asyncBytes {
    data.append(byte)
    let currentProgress = Double(data.count) / Double(length)

    if Int(fastRunningProgress * 100) != Int(currentProgress * 100) {
        self.downloadPercentage = currentProgress
        fastRunningProgress = currentProgress
    }
}

Not the most beautiful code I’ve ever written, but gets the job done!

AsyncBytes is probably the premier new AsyncSequence in iOS 15. While it does feel like a very low-level API that you generally wouldn’t choose, it yields such fine-grained control that it’s flexible enough to handle whatever trickles in over the network. It’s also great to get a little experience with AsyncSequences early. Because of its byte-by-byte interface, it’s very straightforward to write things like progress indicators. Great stuff!

As a professional programmer, there are two main types of tasks you work on. I’ve started thinking about them as the context and the logic.

The logic is what you think this job is going to be about when you first start. How do I slice this collection up? How do I find all the paid invoices for this client and sum up their amounts? How does this date get turned into a string to be displayed on the screen? What floor should this elevator go to next? The logic is what they grill you on in interviews. The logic is algorithms. The logic is sometimes specific to your business. The logic is sometimes reusable. The logic has inputs and outputs that are testable.

The context is…everything else. How do I get this data from that service into this client? How do I make this code from this library talk to that code in that library? How do I make my build compile faster? What UI testing framework are we going to use? How do I fill this view controller up with the dependencies it needs? How do I talk to this nifty new e-ink display I bought? Which compile flags will give me useful stack traces when the app crashes? How do I perform this database migration? The context is everything that’s necessary to get your logic to run successfully, consistently, efficiently.

In Structure and Interpretation of Computer Programs, Abelson and the Sussmans write that an algorithm, the logic, “is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory.” It can’t do any of that stuff without a context in which to run. The context lets it communicate to hardware over protocols, send information to a distant database, and even defines how the code is converted into an intermediate representation, CPU instructions, and finally voltage that plays across the silicon. Without context, the logic is purely abstract.

If I wanted to write a dynamic controller for my HVAC — a thermostat! — in Swift, I probably could do it. I could get some hardware like this to talk to the HVAC over 24V, a Raspberry Pi to run it on, maybe a few Raspberry Pis with thermometer sensors around the house to figure out when to turn the HVAC on and off, probably connect everything over Wi-Fi. But while this is possible, think about how much of your energy would be spent soldering hardware, connecting components, testing, writing servers, defining protocols and wire formats, and then compare that to how much time and energy you’d spend actually writing the dynamic control software. It wouldn’t be easy to write the logic, but it would take a fraction of the time that setting up the context would. (Hmm, now I just have to convince my partner that building our own custom thermostat will somehow be better than our Ecobee. It’ll at least be more fun, that’s for sure.)


How much of your time at your job is actually spent on writing the logic, and how much of it is spent preparing an environment in order for that logic to run? I wouldn’t be surprised at all if I found out that 98% of my time was spent on context.

I think a slightly different (and more familiar) way to think about this is in terms of essential versus accidental complexity, a division first suggested by Fred Brooks in 1986. Essential complexity is the logic, accidental is the context. Dan Luu writes about Brooks’s essay: “while this will vary by domain, I’ve personally never worked on a non-trivial problem that isn’t completely dominated by accidental complexity, making the concept of essential complexity meaningless on any problem I’ve worked on that’s worth discussing.”

Nonetheless, logic is not quite the same thing is as essential complexity, and context is not the same as accidental complexity. One example of something that is logic but still potentially accidental complexity is writing an algorithm like Ruby’s #squish in Swift. It’s still logic, it behaves like something you might ask in an interview question, you have to manipulate abstract symbols to get the right output, but it’s a total accident of history that Ruby has made it so you can use it without thinking about it logically, but Swift hasn’t. Another way to look at it: all context is accidental, but not all logic is essential.

Dan estimates 1% as an upper bound of his time spent on essential complexity.

Another question: how much of your code is logic, and how much of it is an environment in which that code can run? To take a quick example, let’s look at a table view in UIKit and then in SwiftUI:

class CountriesTableViewController: UITableViewController {

    let countries: [Country]
    
    override func viewDidLoad() {
        super.viewDidLoad()
        tableView.register(UITableViewCell.self, forCellReuseIdentifier: "cellIdentifier")
    }
    
    override func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
        return countries.count
    }

    override func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let cell = tableView.dequeueReusableCell(withIdentifier: "CountryCell", for: indexPath)
        
        cell.textLabel?.text = countries[indexPath.row].name

        return cell
    }    
}

I count 3 lines of real, core logic. Defining the countries array, telling it the count of countries, and assigning the label’s text property.

And the same thing in SwiftUI:

struct CountriesList: View {

    let countries: [Country]

    var body: some View {
        List(countries) { country in
            Text(country.name)
        }
    }
}

Where did all of that other stuff go? The 3 lines of core logic are still there, but everything else seems to have disappeared. It was all context, non-essential for this purpose. A different tool made it vanish. This problem only gets worse as you codebase gets larger; your time becomes dominated by the context. From stem to stern, a typical feature might need a new database table on the server, some queries for that table, some endpoints that call those queries, some networking code on the client to hit those endpoints, a ton of routing code to get the user to a new view controller, and finally dozens of lines of table view controller code, all so you can put a label on the screen with the contents of a database field.

The context even has social and political elements. Who is writing the endpoint? What are their priorities? How do they earn promotions and how will that affect their writing the endpoint you need? Every time you read a tweet about how you “can learn the coding part while on the job, but the empathy and human components you need to have before you get there” is exactly about this.

This framing, context vs logic, illustrates two things for me:

First, that we all tell ourselves a lie: this job is primarily about the logic, interview candidates should mainly be tested on their ability to think about the logic, a “good” programmer is someone who can write the logic really well. In fact, an overwhelming amount of the job is making the context work. That’s not to say that the logic isn’t important; without the logic, the context doesn’t do anything and you won’t be able to do the job! But without the context, you still can’t do the job, and sadly there’s a lot more context than logic. I’m primarily a context programmer. I wish I weren’t — I enjoy writing the logic a lot more — but it is the reality. I should embrace that and treat the context as my job, rather than as an impediment to “my real job”.

Second, if you can make your context simpler and smaller, you can spend less time on it. Simplifying and unifying your context (where possible) is valuable, since you can recoup value by spending less time working in the context. Don’t use two technologies where one will do.

Some examples of this:

  1. Using multiple ORMs/data access patterns. The lava layer anti-pattern hurts you specifically because it adds so much extra context to work with. If you can make your context simpler and smaller, you can spend less time on it.
  2. I moved my server set-up from dynamic-sites-on-Heroku/static-sites-on-Linode to everything on Linode (using Dokku). One tool, one server, everything gets treated the same.
  3. Use clever tools, languages, and libraries to make the context become less and less impactful. You can see this in Dan’s essay and with the SwiftUI example. A tool like Fastlane brings code-signing, testing, deploying, and integrations all under one roof and lets you manipulate any of them with short Ruby commands. (In addition to unifying disparate things, this also lets you logic-ify your context, which is neat, too.)

You’ll always have a lot of context to wade around in. This is, sadly, your job. Try to minimize this context as much as possible and you can spend a little less time on it and more time on the good stuff.

“Telling a programmer there’s already a library to do X is like telling a songwriter there’s already a song about love.” - Pete Cordell

Sometimes, it feels like questions that arise during my time programming take years to answer. In particular, my journey to a web framework that I vibe with has been a long one.

A few years ago, I wrote about trying to squeeze the behavior I want out of Vapor. I (rather poorly) named the concept Commands, and I wrote a blog post about the pattern.

Generally speaking, this style of routing, where you use a closure for each route, has been used in frameworks like Flask, Sinatra, and Express. It makes for a pretty great demo, but a project in practice often has complicated endpoints, and putting everything in one big function doesn’t scale.

Going even further, the Rails style of having a giant controller which serves as a namespace for vaguely related methods for each endpoint is borderline offensive. I think we can do better than both of these. (If you want to dig into Ruby server architecture, I’ve taken a few ideas from the Trailblazer project.)

Here’s what the Command protocol basically looked like:

protocol Command {
    
    init(request: Request, droplet: Droplet) throws
    
    var status: Status { get }
    
    func execute() throws -> JSON
	
}

(This is Vapor 2 code, so I think the above code won’t compile with modern versions of Vapor. RIP to “droplets”.)

The Command protocol represented an instance of something that responds to a request. There was a lot I liked about the Command pattern. It was one object per request, meaning each object had strong sense of self, and the code was always nicely structured and easy for me to read.

However, it had some downsides. First, it was tacked on to Vapor. There was a fair bit of code to ensure that things stayed compatible with Vapor, and when they released an update, I was obliged to migrate all my stuff over as well.

In addition, the initializers for Commands always had a ton of work in them:

public init(request: Request, droplet: Droplet) throws {
    self.apnsToken = try request.niceJSON.fetch("apnsToken")
    self.user = try request.session.ensureUser()
}

Anything you needed to extract out of the Request had to be done here, so there was always a lot of configuration and set up code here. For complex requests, this gets huge. Another subtle thing — because it relies on Swift’s error handling, it can only ever report one error.

This initialization code looks to me like it could get simpler still, and with a little configuration, you could get the exact results you wanted, good errors if something went wrong, and a hefty dose of optimization that I could sprinkle in by controlling the whole stack.

Meridian

Enter Meridian.

struct TodoDraft: Codable {
    let name: String
    let priority: Priority
}

struct CreateTodo: Responder {

    @JSONBody var draft: TodoDraft

    @EnvironmentObject var database: Database
    
    @Auth var auth

    func execute() throws -> Response {

        try database.addTodo(draft)

        return try JSON(database.getTodos())
            .statusCode(.created)
    }
}

Server(errorRenderer: JSONErrorRenderer())
    .register {
        CreateTodo()
            .on(.post("/todos"))
    }
.environmentObject(try Database())
.listen()

Property Wrappers

Meridian uses property wrappers to grab useful components from the request so that you can work them into your code without having to specify how to get them. You declare that you want a @JSONBody and give it a type, it handles the rest:

@JSONBody var draft: TodoDraft

Because the value is a non-optional, when your execute() function is called, you’re guaranteed to have your draft. If something is wrong with the JSON payload, your execute() function won’t be called (because it can’t be called). You deal in the exact values you want, and nothing else.

You want a single value from the JSON instead, because making a new Codable type to get a single value is annoying? Bam:

@JSONValue("title") var title: String

You can make the type of title be optional, and then the request won’t fail if the value is missing (but will fail if the value is the wrong type).

URL parameters: very important. Sprinkle in some type safety, and why don’t we make them named (instead of positional) for good measure?

@URLParameter(\.id) var id

Query parameters, including codable support for non-string types:

@QueryParameter("client-hours") var clientHours: Double?

A rich environment, just like SwiftUI, so you can create one database and share it among many responders.

@EnvironmentObject var database: Database

You can use EnvironmentValues for value types or storing multiple objects of the same type.

@Environment(\.shortDateFormatter) var shortDateFormatter

The cherry on top? You can define your own custom property wrappers that can be used just like the first-class ones. I’ve primarily been using this for authentication:

@Auth var auth

You can define them in your app’s module, and use it anywhere in your app, just like a first class property wrapper.

All of these property wrappers seek to have great errors, so users of your API or app will always know what to do to make things work when they fail.

It’s a real joy to simply declare something at the top of your responder, and then use it as though it were a regular value. Even though I wrote the code, and I know exactly how much complexity goes into extracting one of these values, there’s still a magical feeling when I write @QueryParameter("sortOrder") var sortOrder: SortOrder and that value is available for me to use with no extra work from me.

Outgoing Responses

Property wrappers represent information coming in to the request. However, the other side of Meridian is what happens to data on the way out.

For this, Meridian has Responses:

public protocol Response {
    func body() throws -> Data
}

Responses know how to encode themselves, so JSON takes a codable object and returns JSON data. All the user does is return JSON(todos) in their execute() function, and the data is encoded and relevant headers are attached.

EmptyResponse, Redirect, and StringResponse are all pretty straightforward. It’s also not too hard to add your own Response. In one project, I needed to serve static files, so I added a File response type.

struct File: Response {
    let url: URL
    
    func body() throws -> Data {
        try Data(contentsOf: url)
    }
}

This might get more advanced in the future (maybe we could stream the file’s data, let’s say), but this gets the job done.

Responses are a type-aware way of packaging up useful common behavior for data coming out of a request.

Where things are headed

Meridian is nowhere close to done. I’ve written three different JSON APIs with it and a rich web app (using Rob Böhnke’s Swim package to render HTML). The basic concepts are working really well for me, but there’s quite a few things it doesn’t do yet.

  • Parsing multipart input
  • Serving static files
  • Side effects (like the aforelinked Commands)
  • Localization
  • HTML nodes that can access the environment
  • Middleware?

Meridian also knows so much about the way your requests are defined that it should be able to generate an OpenAPI/Swagger spec just from your code, which would be an amazing feature to add.

Meridian is currently synchronous only. The options for async Swift on the server are not great at the moment (because you either end up exposing NIO details or rewriting everything yourself). I’d rather have the migration to async code be as simple as putting await in front of everything, instead of changing all of your code from a block-based callback model to a flat async/await model. I’m focused more on developer experience than sheer request throughput.

I also have a lot of docs to write. I also wrote some docs.

While it’s a bit passé to not blog for over a year, and then dive right back in by talking about your blog setup, I’m going to do it anyway. I recently moved all of my static sites and Swift services over to Dokku, and I am really enjoying it.

Dokku is a collection of shell scripts that act as a self-hosted platform-as-a-service. Basically, it’s your own personal Heroku. Chris and I actually discussed it a few years ago on a (Patreon-only) episode of Fatal Error. I’ve wanted to move my stuff to it for a while, and finally spent some time over the break getting things moved over.

First, I want to run down how things were running before, and why I wanted something like Dokku. First, I manage 4 static sites, including this one. I, through painful trial/error/googling, carefully set up nginx virtual hosting to host all 4 sites on a single Linode instance. I also run 4 git remotes on that server, with clever post-receive hooks that accept pushes, do bundle install and jekyll build (when appropriate) and copy the HTML files to their final destination. This works pretty well and feels Heroku-esque (or Github pages-esque, if you like). I git push, and the rest happens for me automatically. I particularly like this model because it hits the trifecta — I get to host the site myself, I get to use Jekyll (including plugins!), and its interface is just a simple git push. I can even push changes from my phone using Working Copy.

Recently, I also started running a Swift API for a chore app for me and my girlfriend. I hope to blog more about this app soon for a few reasons, not least of which is that I wrote my own property wrapper-based web framework on top of Swift NIO, which has been working great.

This API has been running on Heroku. Because only two people use it, it doesn’t really make sense to pay $7/mo for a dyno, especially given that I run 4 static sites for $5/mo on Linode. Heroku does have a free tier they call “Hobby”, but using it incurs a performance penalty — your app spins down if you don’t use it for a little while (about 30 minutes or so?), and spinning back up takes 5-10 seconds. This makes for a pretty intolerable experience in the app. This too was a good candidate for moving to my own infrastructure.

I wrote one more small Swift-based web service for myself, which also shouldn’t have a ton of usage but does need its own Postgres database, and that cinched it. I wanted to move off of this patchwork system onto something more consistent.

I spun up a new Linode instance, installed Dokku, and got to work. Each Dokku site had three major components for me:

Buildpacks

Dokku uses buildpacks and Procfiles, just like Heroku, to describe how to install and run any app. Buildpacks can be set as an environment variable for the app, or included in the repo in a .buildpacks file. For Jekyll sites, you actually need two buildpacks:

https://github.com/heroku/heroku-buildpack-nginx.git
https://github.com/inket/dokku-buildpack-jekyll3-nginx.git

On the other hand, for Swift sites, the default Vapor buildpack works great:

https://github.com/vapor-community/heroku-buildpack

Encryption

Dokku has a concept of “plugins”, which add functionality to Dokku. The Let’s Encrypt plugin worked flawlessly for me. Installing a plugin is easy:

dokku plugin:install https://github.com/dokku/dokku-letsencrypt.git

You install it, set your email as an environment variable, and ask the plugin to add encryption to your site. (DNS for the relevant domains needs to be pointing at the server already for this to work.) Love it.

Databases

The two Swift services both need Postgres. No problem, just one more plugin:

dokku plugin:install https://github.com/dokku/dokku-postgres.git postgres

From the Postgres plugin, you can create databases, link them to apps, expose them to the internet, and manage them as needed.

Debugging

I want to end on one final note about debugging. Dokku itself is not a particularly complex tool, since it delegates all the isolation and actual deployment of code to Docker. (Side question: is it “dock-oo”, because of Docker, or doe-koo, like Heroku? The world may never know.) The reliance on Docker means that it can be really helpful to know how to debug Docker containers.

Two specific tips I have here:

  1. You can dokku enter my-app-name web to enter the virtualized machine’s console, which can let you explore the structure of things.
  2. You can use docker ps to list all the currently running containers, and use that to watch the logs of a build in progress, by using docker logs -f <container id>. This is super useful for debugging failing builds. (Big thanks to Sam Gross for giving me some insight here.)

Conclusion

Dokku basically checks all my boxes. I get to run things on my own servers, it’s cheap, and deploys are easy as a git push. I’m paying the same amount as before ($5/mo! I can hardly believe it!) My previously manually managed static sites all have the exact same interface as they used to, with a lot less work from me to set up and manage, and now I’m hosting Swift-backed sites as well. Put one in the W column.

Recently, I’ve been working on a music app that needs to get a musical sequence (like a melody) from the server to the client. To do this, we use a format called ABC. (You can read about how ABC music notation works here.) We chose ABC because it’s more readable than MIDI, it’s pretty concise, and it’s a standard, so we wouldn’t be re-inventing some format over JSON.

ABC is a simple format, and it does a great job of representing music in strings. For example, here’s the little bit from Beethoven’s “Für Elise” that everyone knows:

e ^d e d e B =d c A2

The letters correspond to specific pitches, the characters before the letters represent accidentals (sharps and flats), and the numbers after them represent the duration that that note should be played for. ABC has a lot more features (it supports rests, ties, beams, barlines, and so on), but this simple example gives you a sense for how the format works.

The app needs to transform the string into some kind of struct that the sequencer knows how to play. In short, we need to parse this string.

Regular Expressions

At first blush, the problem seems easy enough. Split on spaces, and write some regular expressions to convert each note into some kind of value. For note parsing, the expression looks something like this:

^(\\^+|_+|=)?([a-gA-G])(,+|'+)?(\\d*)(\\/)?(\\d*)$

There are 3 main problems with this regular expression.

It’s inscrutable

It is nearly impossible to determine what this regex does by looking at it. Especially for something like ABC, which uses punctuation marks for things like accidentals (^, _, and =) as well as octave adjustments (' and ,), it’s really hard to tell which are literal characters that we are trying to match, and which are regex control characters that tell the pattern to match zero or more of this one, optionally match that one, and so on.

One thing I will grant here is that despite their inscrutability, regexes are one of the tersest languages you can write.

It’s not composable

Another problem with regular expressions is that the constituent components don’t compose easily. For example, our Beethoven sequence above doesn’t include any rests, but they typically look like just like a note with a z instead of the letter of the pitch. So for example, a half rest might look like z/2.

Ideally, we’d like to be able to reuse the duration pattern, but it’s currently trapped inside that giant regex. In order to compose these regexes together, we have to break them apart first, and then apply some string concatenation:

let accidentalPattern = "(\\^+|_+|=)?"
let letterPattern = "([a-gA-G])"
let octaveAdjustmentPattern = "(,+|'+)?"
let durationPattern = "(\\d*)(\\/)?(\\d*)"
let restPattern = "z"

let noteRegex = try! NSRegularExpression(pattern: accidentalPattern + letterPattern + octaveAdjustmentPattern + durationPattern)

let restRegex = try! NSRegularExpression(pattern: restPattern + durationPattern

This is really the only way to get composability with regexes. And of course, because these are just strings that we’re concatenating, there’s no way to know if our concatenation represents a valid transformation of the underlying regular expression because it isn’t checked at compile time.

It requires additional conversion

Lastly, even once we have successfully composed our regex pattern, compiled it into a regular expression, and parsed a string, we still don’t actually have anything useful! We have a bunch of capture groups that we need to operate on to get our final result. For example, the first capture group in the regex gives us our accidental string. This can either be one more carets (^) (sharp), one more underscores (_) (flat), or an equals sign (=) (natural), but the regex doesn’t tell us which it is, so we need to parse it further.

let numAccidentals = match.captureGroups[0].text.count
let accidentalChar = match.captureGroups[0].text.first

switch accidentalChar {
case "^":
    return .accidental(numAccidentals)
case "_":
    return .accidental(-numAccidentals)
case "=":
    return .natural
case "":
    return Accidental.none
default:
    return nil
}

Requiring a manual step where we have to convert the matched substring into our domain object is kind of annoying.

Combinatorial Parsing

My first clue that we needed to look closer at this problem was a function signature. Our strategy for parsing sequences was to consume small pieces of the front of a string. For example, for a note, we’d have something like this:

func consumeNote(abcString: Substring) -> (note: Note?, remainder: Substring)

A function that returns a tuple of (T?, Substring) looked very familiar. I’d seen it referenced in the Pointfree code about combinatorial parsing:

extension Parser {
    run(_ str: String) -> (match: A?, rest: Substring)
}

This is called a combinatorial parser because it relates to a somewhat obscure part of computer science called combinators. I don’t understand them fully, but I will kick it over to Daniel Steinberg to share some very cool examples.

I figured if we’re trying to parse text and return something in this format anyway, maybe the combinatorial parser could be a good fit. So I did a little research on the topic and started the process of reimplementing our parsing with this new strategy. The crux of the parser is a struct with a single function:

struct Parser<A> {
    let run: (inout Substring) -> A?
}

You give it a string (a substring in this case, for performance reasons) and it consumes characters from the front of the buffer to see if it can construct a generic A from them. If that succeeds, it returns the A. If it fails, it returns nil, ensuring no modifications to the input parameter.

Using parser combinators, it’s possible to write concise, type-safe, composable code that parses strings just as effectively as regexes. For example, here’s how you check for a literal:

static func literal(_ string: String) -> Parser<Void> {
    return Parser<Void>(run: { input in
        if input.hasPrefix(string) {
            input.removeFirst(string.count)
            return ()
        } else {
            return nil
        }
    })
}

If the input has a prefix of the string we’re looking for, drop that many characters off the front and return a valid value (Void in this case). If not, return nil — no match. I won’t go into detail on all the other helpers here — you can find a lot of them in the Pointfree sample code.

Using this helper and others, you can rewrite the accidental parsing from above into something like this:

let accidentalParser: Parser<Accidental> = Parsers.oneOf([
    Parsers.repeating("^").map({ .accidental($0.count) }),
    Parsers.repeating("_").map({ .accidental(-$0.count) }),
    Parsers.literal("=").map({ .natural }),
    Parsers.literal("").map({ .none }),
])

This avoids basically every pitfall that the regex approach has.

First, it’s very readable. You can see what literal characters it’s matching because they’re still strings, but all the regex control characters have changed into named functions, which are approachable for people who aren’t regex experts.

Second, it’s very composable. This parser is made up of smaller parsers, like .repeating or .literal, and is itself composed into bigger parsers, like those for notes, rests, and so on. Here’s the accidental parser in the note parser.

var noteParser: Parser<Note> {
    return Parsers.zip(accidentalParser, pitchParser, durationParser)
        .map({ accidental, pitch, duration in
            return Note(accidental: accidental, pitch: pitch, duration: duration)
        })
}

(zip matches all of the parsers that are given to it, in order, and fails if any of them fail.) In this example, it’s also really great to see how all the types line up cleanly. You get a lot of assurance from the compiler that everything is in order.

The last benefit it has over regex is that it produces the actual value that you’re expecting, an Accidental, as opposed to substring capture groups that you have to process further. Especially using the map operation, you can transform simple results, like a substring or Void into domain specific results, like Accidental or Note.

The only real place that this loses out to regexes is terseness, and when you add the transformation code that regexes require, it’s basically a wash.

Now, we’ve completely handrolled a parsing solution from scratch, in pure Swift, using only tools like substrings and blocks. Surely regexes, which are highly tuned and written in C, should be able to massively outperform this code in terms of speed?

Wrong. By using this new approach, we were able to get 25% faster parsing across the board. This shocked me, to be honest. I will usually take a small speed hit if it makes the code nicer (assuming it’s not a critical path, not noticable by the user, etc), but in this case, that wasn’t even a concern, since the nicer code was also the faster code. Win-win! I think a lot of the speed benefit comes from using substrings. Trimming off the front of a substring is effectively free, which makes a lot of these operations super fast.

There are still a few areas which I’d like to learn more about, like unparsing (what if we want to turn our sequence struct back into an ABC string), and how parsers perform when the needle is in an arbitrary place in the haystack, but it’s going to be pretty hard to get me to go back to regexes after these results.

A few years ago, I wrote Implementing Dictionary In Swift, which was a crash course on how to create something similar to Swift’s Dictionary type.

Since our dictionary will be backed with an array, we need a way to convert the key that’s given into an integer, and then a way to force that integer into the bounds of our array. These two methods are the hashing function and the modulus operation, respectively. By hashing, we can consistently turn our key (usually a string, but can be any type that is Hashable) into a number, and by taking the modulus with respect to the length of the array, we’ll get a consistent slot in the array to set and retrieve the value.

Because there can be collisions, each “bucket” needs to potentially contain multiple items, so the whole thing was modeled as an array of arrays. This was a less-than-performant shortcut to get code that was working up quickly. In the post, I noted that:

A nice implementation of this Dictionary might use a linked list for the values property of the Placeholder.

Since writing that post, I’ve learned a lot of things, but germane to the discussion here: this is a bad strategy. Linked lists are very good when memory is tightly limited, and you can’t reliably secure a long, unbroken block of memory. As memory in our computers has gotten bigger, CPUs have learned to predict and preload memory in long sequences, so working with continuous blocks of memory is remarkably faster to jumping around the memory space through a discontinuous chain.

So if we don’t want to use an array of arrays, and we don’t want to use an array of linked lists, what else can we do? It turns out that there is a Dictionary storage technique that avoids the problems with both solutions.

If you remember that any array of arrays can be “flattened” into one large array, a solution begins to take shape. If the bucket for a given hash value is taken, instead of storing a second value at the same location, put the new value in the neighboring bucket. Then, when searching for that element, if you see something where it should be, check the neighboring buckets until you find it (or an empty slot).

This technique is called “linear probing”. It was invented in 1954 and is the way that Swift’s Dictionary is actually implemented!

In this post, we’re going to writing a Dictionary that’s backed by linear probing. I’m going to use a test-driven development approach for a few reasons.

First, a key thing in Swift has changed since I wrote the last dictionary blog post. Swift 4.2 changed Swift’s hashing to be non-deterministic. This makes it really hard to write to simple tests in a playground, since any value’s hash changes between runs. We need to tightly control how our hash values are produced so that we can be sure that our Dictionary behaves appropriately as we refactor it.

Second, this algorithm behaves interestingly at the boundaries — that is, as it runs up against the end of the backing array and needs to roll over to the start of the array — and we need to make sure we handle that behavior correctly.

Third, deletion is really, really hard to get right with linear probing, and there are quite a few edge cases that need to be examined closely.

The technique also lends itself to some refactoring and restructuring, and having tests will be a great safety net to ensure that we don’t break old behavior as we make the code cleaner and simpler.

Getting Things Compiling

So, let’s get started. Test-driven development requires that you write a failing test before writing the code that makes it work, so let’s do that here.

func testGettingFromAnEmptyDictionary() {
    var dictionary = ProbingDictionary<String, String>()
    XCTAssertEqual(dictionary["a"], nil)
}

This test doesn’t compile, so we can call that failing. Let’s build the basics of the type and get this test passing.

struct ProbingDictionary<Key: Hashable, Value> {

    subscript(key: Key) -> Value? {
        get {
            return nil
        }
        set {
        }
    }

}

Not a very good dictionary, but at least it compiles and passes the first test.

Getting and Setting a Single Value

Next, let’s get it to be able to set and then get a single value. Test first:

func testSettingAndGettingAValue() {
    var dictionary = ProbingDictionary<String, String>()
    dictionary["a"] = "123"
    XCTAssertEqual(dictionary["a"], "123")
}

(The most hardcore TDD acolytes will change the implementation so that it can store exactly one value, probably in an instance variable, since that’s the bare minimum of code that you need to make this test pass. I think that’s kind of silly, so I will skip that step and jump straight to an implementation that works with multiple values.)

For the implementation, we need a few things already. We need some kind of Placeholder type again, like in the last post. However, instead of being able to store an array of key/value pairs, it’ll just store a key and a value, or nothing:

enum Item {
    case element(Key, Value)
    case empty
}

I also added some helpers for grabbing stuff like the key and value easily:

extension Item {
    var value: Value? {
        if case let .element(_, value) = self {
            return value
        }
        return nil
    }
}

We also need storage for the data in the dictionary:

private var storage: [Item] = Array(repeating: .empty, count: 8)

(8 is the initial size of the dictionary. In a real implementation, you might want to start with a bigger value, but for this example, smaller is easier to understand. We’ll implement resizing soon anyway.)

Next, we need to rewrite the get and set subscript methods. This looks a lot like the version of the dictionary from the last post:

subscript(key: Key) -> Value? {
    get {
        let index = abs(key.hashValue % storage.count)
        return storage[index].value
    }
    set {
        if let newValue = newValue {
            let index = abs(key.hashValue % storage.count)
            storage[index] = .element(key, newValue)
        }
    }
}

The abs ensures that negative values are handled correctly. This simple implementation makes our new test pass, but doesn’t handle collisions, so it’s time to write a test for that.

Handling Collision

We’d like to handle collisions, but we have a problem in setting up a test for them. As I mentioned earlier, Swift’s hashing is non-deterministic as of Swift 4.2, which means that if you run the same code twice, you’ll get two different hash values for the same object. That makes forcing a collision to happen really difficult.

We need a way to ensure that our test is perfectly reproducible and actually tests the thing we’re trying to test, which is a collision that has to occur every time we run this test. There two options here. First, you can set an environment variable called SWIFT_DETERMINISTIC_HASHING and find two values that happen to hash to the same bucket.

However, according to Karoy in the Swift forum thread announcing this new feature,

setting SWIFT_DETERMINISTIC_HASHING does not guarantee that hash values remain stable across different versions of the compiler/stdlib – please do not rely on specific hash values and do not save them across executions.

This means that we might have to update our tests every time the Swift toolchain is updated, and that’s not great. Instead, we can write a small type that can perfectly control what it hashes to. It needs fields for its underlying value and its hash value separately, so that a collision (two values that aren’t equal but have the same hash value) can be forced:

struct Hash: Hashable {

    let value: String

    let hashValue: Int

    init(value: String, hashValue: Int) {
        self.value = value
        self.hashValue = hashValue
    }

    static func == (lhs: Hash, rhs: Hash) -> Bool {
        return lhs.value == rhs.value
    }
}

(This type has a warning telling us not to use hashValue directly. Nothing can really be done about that.) Given this small type, we can now write a test with a forced collision:

func testACollision() {
    var dictionary = ProbingDictionary<Hash, String>()
    dictionary[Hash(value: "a", hashValue: 1)] = "123"
    dictionary[Hash(value: "b", hashValue: 1)] = "abc"
    XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 1)], "123")
    XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 1)], "abc")
}

The first and second items in the Dictionary have different values, but the same hash value, which will cause a collision. Running this test, we can observe the failure. The second item is overwriting the first. To fix this, we need to rewrite our get and set functions again.

Instead of returning the value at the hashed index, we need to check if it contains the right key. If it doesn’t, we need to step to the next value and check if it contains the right key. We keep doing this until we find the right key or hit an .empty element. Here’s an implementation that gets the job done.

get {
    let index = abs(key.hashValue % storage.count)
    return storage[index...]
        .prefix(while: { !$0.isEmpty })
        .first(where: { $0.key == key })?
        .value
}
set {
    if let newValue = newValue {
        let index = abs(key.hashValue % storage.count)
        if let insertionIndex = storage[index...].firstIndex(where: { $0.isEmpty || $0.key == key }) {
            storage[insertionIndex % storage.count] = .element(key, newValue)
        }
    }
}

It can be nice to notice that while the prefix + first(where:) in the get and the firstIndex(where:) look different, they can actually be both written the same. By rewriting the get to use .first(where: { $0.isEmpty || $0.key == key }), you can make the two blocks look the same, which suggests that there might be some shared code we can extract from here. We’ll come back to that soon.

Collisions Near the Rollover Boundary

Now that our test is passing, time to write our next failing test. Careful readers will note that we’re not handling the rollover case correctly. If the probing happens at the boundary where the storage array rolls over it’ll return nil even though there is a value in the dictionary at that spot. Let’s write a test for that.

func testARolloverCollision() {
    var dictionary = ProbingDictionary<Hash, String>()
    dictionary[Hash(value: "a", hashValue: 7)] = "123"
    dictionary[Hash(value: "b", hashValue: 7)] = "abc"
    XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 7)], "123")
    XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 7)], "abc")
}

We happen to know that our dictionary’s original size is 8, so we know to put the colliding elements at index 7 of the storage. However, to make this more robust, you might expose the size of the storage as an internal detail so your tests can rely on it but consumer code can’t. Either way, we have another failing test.

Fixing this one is kind of easy, but also kind of hard. Instead of just checking storage[index...], we need to follow it up with a check storage[..<index] as well. The naive solution for this is just to append the two together with a +.

let rotated = storage[index...] + storage[..<index]

This causes a major performance issue, which we have to address.

By examining the types, we can see what’s going on. rotated is an ArraySlice, which usually represents a view on an array — it stores the original array, a start index and an end index. However, this is not really one slice of an array, but rather two concatenated together, which means that because the internal storage of ArraySlice (the array and the two indices) can’t store the components of two different arrays, it will have to copy and modify one of them. Because ArraySlice is a copy-on-write type, this means that the whole storage array has to be copied into new storage when you execute that + operator. This has the ultimate effect of making every read from the dictionary be an O(n) operation, which is unacceptable. There are a few ways to fix this.

The apple/swift repo has a “Prototypes” folder which contains lots of interest and useful things that aren’t shipped with Swift or its standard library, but are useful nonetheless. Two of these are Concatenated and RotatedCollection. The first allows you to concatenate two collection together without copying, and the second enables you to “rotate” a collection around a pivot, which is exactly what we’re trying to do here. However, because we don’t have this type available to us, I’m going to take a different approach.

We discussed earlier that there’s a shared function we can extract from here, called firstOrEmptyIndex(matchingKey:), which finds the first index that matches our key or is empty. We can use that in both the get (grab the value of that Item, which return nil if it’s empty) and set (overwrite the key-value pair at that index). Let’s take a look at that function. We can add support for our new behavior here, checking all indices before the pivot as well.

func firstOrEmptyIndex(matchingKey key: Key) -> Int {
    let block: (Item) -> Bool = { $0.isEmpty || $0.key == key }
    let initialIndex = abs(key.hashValue % storage.count)
    let index = storage[initialIndex...].firstIndex(where: block)
        ?? storage[..<initialIndex].firstIndex(where: block)
     return index! % storage.count
}

Getting and setting become a lot simpler now:

subscript(key: Key) -> Value? {
    get {
        let index = firstOrEmptyIndex(forKey: key)
        return storage[index].value
    }
    set {
        if let newValue = newValue {
            let insertionIndex = firstOrEmptyIndex(forKey: key)
            storage[insertionIndex] = .element(key, newValue)
        }
    }
}

Tests are now passing. We can now handle rollover collisions.

At this point, I added a few more tests that didn’t require code changes. What if there’s a triple collision? What if there’s two or three objects in the dictionary that don’t collide? What about neighboring non-colliding objects? They all passed without requiring any code changes, so I’ll elide them here.

Resizing

The next feature I want to build is resizing. You might have noticed the force unwrap in that new function we just added. If none of our slots are .empty, we risk a crash. Resizing helps us ensure that there’s always free space in the dictionary. Again, test first! I think the best approach here is to store a large number of items in the dictionary (in this case 1000 items) and then assume that that’s enough items to force a resize.

func testResizing() {
    let letters = "abcdefghijklmnopqrstuvwxyz"
    func randomString() -> String {
        return String((0...10).compactMap({ _ in letters.randomElement() }))
    }
    let values = (1...1000).map({ (randomString(), $0) })
    var dictionary = ProbingDictionary<Hash, String>()
    for (key, hash) in values {
        dictionary[Hash(value: key, hashValue: hash)] = key
    }

    for (key, hash) in values {
        XCTAssertEqual(dictionary[Hash(value: key, hashValue: hash)], key)
    }
}

This test fails, so we know that it tests resizing correctly. Resizing is a pretty straightforward feature, and it’s very similar to how the resizing code in the previous blog post worked:

private mutating func resizeIfNeeded() {
    guard self.storage.filter({ $0.hasElement }).count > storage.count / 2 else { return }
    let originalStorage = self.storage
    self.storage = Array(repeating: .empty, count: originalStorage.count * 2)
    for case let .element(key, value) in originalStorage {
        self[key] = value
    }
}

Copy the storage, create a new storage that’s twice as big, and then copy all the elements into the new storage. I even got to use for case syntax in Swift, which I’ve never used before. If we call this method before trying to set any values, our new test will pass.

Collection Conformance

Let’s implement Collection conformance next. Instead of having a separate test for Collection stuff, we can just add an extra assert at the bottom of each test, asserting how many items should be in the Dictionary by the end of the test.

func testACollision() {
    var dictionary = ProbingDictionary<Hash, String>()
    dictionary[Hash(value: "a", hashValue: 1)] = "123"
    dictionary[Hash(value: "b", hashValue: 1)] = "abc"
    XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 1)], "123")
    XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 1)], "abc")
    XCTAssertEqual(dictionary.count, 2)
}

This is this simplest I could get the conformance to be, code-wise:

extension ProbingDictionary: Collection {
    var startIndex: Int {
        return storage.firstIndex(where: { $0.hasElement }) ?? storage.endIndex
    }

    var endIndex: Int {
        return storage.endIndex
    }

    func index(after i: Int) -> Int {
        return storage[i...].dropFirst().firstIndex(where: { $0.hasElement }) ?? endIndex
    }

    subscript(index: Int) -> (Key, Value) {
        return (storage[index].key!, storage[index].value!)
    }
}

While this works, it doesn’t quite meet the performance characteristics that Collection expects. startIndex should be an O(1) operation, but here it’s O(n), since it has to run through the storage array to find the first non-empty element. A better implementation would store the startIndex (and probably the current count, too) so that those things could be returned in O(1) time. The start index would store the first index in the storage array that is not .empty. Although it would add to the layout of the Dictionary, it’s probably worth it in order to deliver complexity guarantees that consumers would expect.

Now is also a fine time to throw in helpers for keys and values, which users also expect:

extension ProbingDictionary {
    var keys: AnySequence<Key> {
        return AnySequence(storage.lazy.compactMap({ $0.key }))
    }

    var values: AnySequence<Value> {
        return AnySequence(storage.lazy.compactMap({ $0.value }))
    }
}

Deletion

Okay. It’s time to write the code to handle deletion from the dictionary. I won’t lie to you — deletion with linear probing is hard. Think about it: you have to find the index (easy enough), replace it with .empty (fine), and then slide down every other element until the next .empty, unless the element is already in the lowest possible slot, in which case skip it and look for another one you can swap down (yikes!).

As always, test first:

func testDeletion() {
    var dictionary = ProbingDictionary<Hash, String>()
    dictionary[Hash(value: "a", hashValue: 7)] = "123"
    dictionary[Hash(value: "b", hashValue: 4)] = "abc"
    dictionary[Hash(value: "a", hashValue: 7)] = nil

    XCTAssertEqual(dictionary[Hash(value: "a", hashValue: 7)], nil)
    XCTAssertEqual(dictionary[Hash(value: "b", hashValue: 4)], "abc")
    XCTAssertEqual(dictionary.count, 1)
}

(Adding collection conformance is quite nice here, since it lets us check that size of the dictionary is accurate after the deletion.)

Writing this code frankly sucked. There’s no cute code that could dig me out of this one:

var deletionIndex = firstOrEmptyIndex(forKey: key)
repeat {
    let potentialNextIndex = (storage[deletionIndex...] + storage[..<deletionIndex])
        .prefix(while: { !$0.isEmpty })
        .dropFirst()
        .firstIndex(where: { abs($0.key!.hashValue % storage.count) <= deletionIndex })
    storage[deletionIndex] = .empty
    if let nextIndex = potentialNextIndex {
        let nextIndex = nextIndex % storage.count
        storage[deletionIndex] = storage[nextIndex]
        deletionIndex = nextIndex
    }
} while !storage[deletionIndex].isEmpty

Truly the stuff of nightmares. Does it work? I think so. It’s hard to be confident when the algorithm is this complicated. At this point, I added tests to cover the cases I could think of — deletion with neighboring non-colliding elements, deletion with colliding elements, deletion with neighboring elements that both collide and don’t collide, deleting elements that don’t exist, deleting an element and writing back to that same key, and so on. I’m fairly confident at this point that the code works, but I much prefer code that I can understand by reading, rather than code whose working state depends on what failures I can think of and write tests for.

Tombstones

Fortunately, there is a better way to handle deletion. Right now, we only have two cases in our Item enum: either it has an element, or it doesn’t. But if we could add a little bit of information to that, we could make a distinction between slots that have never held an element, and slots that used to hold an element but don’t anymore. We call these tombstones (💀), since they represent a marker for something that lived once, but is now dead. Tombstones help us because when we are doing a set, we can treat tombstones the same as empty elements (because they are writable slots) but when doing a get, we can treat them as a filled slot that doesn’t match our key, so we always pass over them and continue. This simplifies things greatly.

Our “first or empty” function needs to change its signature a bit:

func firstOrEmptyIndex(forKey key: Key, includeTombstones: Bool = false) -> Int

Since we now make a distinction between .tombstone and .empty when reading and writing, each of those two operations will pass a different value for this Bool.

This makes our reading, writing, and deleting code super simple:

subscript(key: Key) -> Value? {
    get {
        let index = firstOrEmptyIndex(forKey: key)
        return storage[index].value
    }
    set {
        resizeIfNeeded()
        if let newValue = newValue {
            let insertionIndex = firstOrEmptyIndex(forKey: key, includeTombstones: true)
            storage[insertionIndex] = .element(key, newValue)
        } else {
            let index = firstOrEmptyIndex(forKey: key)
            if !storage[index].isEmpty {
                storage[index] = .tombstone
            }
        }
    }
}

I like simple, because I can understand simple. All the tests still pass, and thus we know our refactor was successful.

As an aside, I’d like to look at our original Item enum again:

enum Item {
    case element(Key, Value)
    case empty
}

When you first see this type, it can be tempting to try to replace it with (Key, Value)?, since this type holds the same amount of information as the optional tuple. However, not only does a custom enum provide more information to the reader of the code, it also is more easily extended to add the .tombstone case. With the optional tuple, it’s tough to see how the tombstone can be added. Using an enum makes it easy it add that extra case and get to the refactored state.

Linear probing is a super interesting approach for building dictionaries. Given that this post is nearly 3000 words, it’s not an easy technique, but as far as I know, it’s the gold standard for fast, reliable dictionaries. It’s used in Python, Rust, Swift, and many other languages besides. Understanding how it works is key to appreciating the speed and structure of a dictionary.