SIMD and Other Rabbit Holes
Last week I read this post by Mitchell Hashimoto arguing that everyone should know SIMD. It reminded me of how I ran into it myself. Most engineers have no reason to touch complex CPU instruction sets unless they work on something performance sensitive, like building a database or processing images. My own exposure happened by accident, because someone at Mixpanel had the brilliant idea of nerd-sniping engineers into what we called a “perf challenge”.
At Mixpanel, we built a columnar database from scratch to answer product analytics queries, well before something like ClickHouse became commonplace. Performance was a big part of why the product was popular, and the team that built it could not resist a hard problem.
The format of the perf challenge was simple. Take a problem that is trivially easy to get correct but brutally hard to make fast, and timebox it to a couple of weeks, small enough that a weekend of work made you competitive. The 2017 problem was a one liner. Given a file of newline-delimited strings, return a count of each unique entry. The basic approach is obvious. Maintain a hash-map with a count. The challenge was making it run faster than everyone else's, measured on user, sys, and wall-clock time. To make it competitive, we set up a shared Slack channel and gave people a script that posted their run time to the channel on every execution.
The idea behind SIMD instructions is straightforward. Pre-load data into special “registers”, pick the function you want to apply to all of them, and execute it in one instruction instead of many. Once people got the hang of it, the challenge evolved into much harder questions. How do you load data from a file quickly? Are there hash functions that work better for short versus long strings? How does aligning data at word boundaries affect performance? What is the right buffer size for your file system? Does skipping the page cache with DMA actually help? Most of us never had to think about any of this, because libraries and databases handled it transparently. The winning solution applied all of these correctly, but it also had a few insights nobody else found. Getting the basics right is not enough. With most problems, you have to exploit the constraints too.
We did two more perf challenges during my time there. The second added a dimension of approximation. You got a similar file of newline-delimited strings and had to count the total number of unique values, but you could trade accuracy for speed. People discovered HyperLogLog, and then had to get deep into how the sketch was updated, usually with SIMD. The last perf challenge moved in a different direction. The goal was to parse a large file of nested JSON and count the number of keys. By then people were doing genuinely absurd things, like taking apart the simdjson library to beat it or installing advanced linux kernels on state-of-the-art virtual machines in GCP.
In hindsight, the only reason I dug into SIMD was a completely made-up problem I would never have gone looking for on my own. So if you are an engineer stuck building boring CRUD apps (or boring distributed databases), spend a weekend on a toy problem with no real value. A full time job will never hand you a reason to. You usually have to make one up.