Designing a SIMD Algorithm from Scratch (2023)

Sunny Young uses a Rust base64 codec, vb64, to explain how to design SIMD algorithms rather than merely apply vector instructions. The central argument is that SIMD is a way to keep more of a processor’s execution hardware busy by doing the same operation on several data lanes at once. This matters because branches, dependencies, and memory delays stall modern processors, while clock speeds cannot keep rising indefinitely. The explanation builds from scalar bit tricks: population count can be computed efficiently by repeatedly combining neighboring bits into wider groups, illustrating the divide-and-conquer reasoning that also underlies vector algorithms. SIMD extends this approach with lane-wise arithmetic, comparisons that produce masks, and operations for rearranging or selecting data.

The base64 example shows how those ideas become a practical codec. Encoding groups three input bytes into four six-bit values, then maps those values to alphabet characters; decoding reverses the process while checking validity. The challenge is to arrange these steps so many characters can be processed together without relying on per-character branches. The discussion emphasizes that SIMD instruction sets differ across processors, and that language APIs can obscure the hardware operations a programmer needs. Designing a fast, portable implementation therefore requires thinking like a circuit designer: track how bits move between lanes, use masks and shuffles deliberately, and handle incomplete input separately. The piece offers both a conceptual introduction and a worked case study for readers interested in performance programming and Rust’s SIMD facilities.