{"article":{"slug":"practical-auto-vectorization","title":"Practical Auto-Vectorization","subtitle":null,"summary":"Mahdi Bahrami walks through auto-vectorizing a Base64 encoder in Swift, showing how to write loops the compiler can turn into SIMD and how that raised Apple's swift-foundation Base64 encoding to around 16 GB/s, with a look at a roughly 30 GB/s implementation.","content_type":"tutorial","language":"en","canonical_url":"https://blog.mahdibm.com/posts/practical-auto-vectorization/","author":{"name":"Mahdi Bahrami","url":"https://blog.mahdibm.com/","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Mahdi Bahrami's blog","url":"https://blog.mahdibm.com/","listing_slug":null,"listing":null},"topics":[{"name":"Performance","slug":"performance","url":"https://listedarticles.com/topics/performance"},{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"Software Engineering","slug":"software-engineering","url":"https://listedarticles.com/topics/software-engineering"}],"about_listings":[],"cover_image_url":"https://blog.mahdibm.com/images/cards/practical-auto-vectorization.png","license":"all-rights-reserved","word_count":7532,"reading_minutes":33,"published_at":"2026-11-08T00:00:00.000Z","added_at":"2026-11-08T17:11:34.811Z","updated_at":"2026-11-08T17:11:34.811Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/practical-auto-vectorization","markdown_url":"https://listedarticles.com/articles/practical-auto-vectorization.md","example":false,"citation":"Mahdi Bahrami, Mahdi Bahrami's blog. \"Practical Auto-Vectorization.\" 8 Nov 2026. https://blog.mahdibm.com/posts/practical-auto-vectorization/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://blog.mahdibm.com/posts/practical-auto-vectorization/"},"body_markdown":"# Practical Auto-Vectorization\n\nIn this post, we'll use Vectorization to optimize our Base64 implementation to perform **tens of gigabytes per second**. We'll also take a brief look at an implementation that performs ~**30 GB/s**.\n\nWe'll see how I made Apple's [swift-foundation](https://github.com/swiftlang/swift-foundation) Base64 encoding [~3 times faster](https://github.com/swiftlang/swift-foundation/pull/2236), and how you can even surpass that.\n\nI'll also share some tips and tricks for leveraging Auto-Vectorization. Tips that the latest and greatest LLMs repeatedly failed to figure out at their maximum effort, when I was first trying out Auto-Vectorization.\n\n## \n\n## \n\nYou can checkout this post's related commit to test out the implementations and measurements.\n\nYou'll need to have Swift 6.4 and above installed on a Linux or macOS system to run the benchmarks.\n\n```\ngit clone https://github.com/MahdiBM/blog-material\ncd blog-material\ngit switch --detach c63c91e7695c1c2c47828508ee636e19c5709859\n```\nIn the post, measurements also mention their related benchmark command.\n\n## \n\nWe'll use Base64 encoding as it's pretty simple and is a good showcase of the different optimizations.\n\nWe'll use the Swift programming language, but pretty much all optimizations are done at the LLVM layer, so most optimization notes apply to Rust as well.\n\n## \n\nLet's take a quick look at the Base64 encoding. It's pretty simple. We need to understand it before attempting to optimize it.\n\nThe Base64 format was created as a way to transfer raw data over a medium which merely accepts text.\n\nSo what it does is to disguise raw data as if it's normal text. The text will indeed look like gibberish, but that's ok.\n\nTo achieve this, Base64 encoding operates on 3 bytes at a time and outputs 4 Base64 values. Then it maps each of those 4 Base64 values to a corresponding ASCII character, which is typically alphanumeric, so it ticks the box of looking like normal text.\n\nWe'll use the following bytes as examples:\n\n| Byte 1 | Byte 2 | Byte 3 | \n|---|---|---|\n| 0b11000100 | 0b10101111 | 0b10110111 | \n\nAs you can see, the 3 bytes, represented as 3 unsigned 8-bit integers, amount to a total of 24 bits.\n\nBase64 reads 6 bits at a time and gathers 4 6-bit values out of those 24 bits.\n\nNote\n\n`0b` is not part of the value. It simply denotes **Binary** notation.\n\nTip\n\nNotice the colors and the byte names. We'll use those colors and the specific `byte1` / `byte2` / `byte3` names throughout, so the post is easier to follow.\n\nThereafter, it maps each value to an ASCII code-point with the knowledge that each value is only 6 bits, so it must be in range of 0 (0b000000) to 63 (0b111111):\n\n| Base64 Value | 0 ... 25 | 26 ... 51 | 52 ... 61 | 62 | 63 | \n|---|---|---|---|---|---|\n| Corresponding Letter(s) | A ... Z | a ... z | 0 ... 9 | + | / | \n| Corresponding ASCII Codes (Decimal) | 65 ... 90 | 97 ... 122 | 48 ... 57 | 43 | 47 | \n| Corresponding ASCII Codes (Hex) | 0x41 ... 0x5A | 0x61 ... 0x7A | 0x30 ... 0x39 | 0x2B | 0x2F | \n\nNote\n\n`0x` is not part of the value. It simply denotes **Hexadecimal** notation.\n\nSo in this specific case, our 4 Base64 values will be:\n\n|  | Base64 Value 1 | Base64 Value 2 | Base64 Value 3 | Base64 Value 4 | \n|---|---|---|---|---|\n| Binary Value | 0b110001 | 0b001010 | 0b111110 | 0b110111 | \n| Decimal Value | 49 | 10 | 62 | 55 | \n| ASCII Mapping (Decimal) | 120 | 75 | 43 | 51 | \n| ASCII Mapping (Hex) | 0x78 | 0x4B | 0x2B | 0x33 | \n| ASCII Mapping (Character) | `x` | `K` | `+` | `3` | \n\nWhen you see a Base64-encoded text on the web, you're looking at the \"ASCII Mapping\" characters of the Base64 values.\n\n### \n\nWe'll implement the bytes-to-Base64-values function like so:\n\n```\n/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let byte1_yellow = byte1 & 0b1111_1100 // All but the least significant 2 bits\n    let byte1_green = byte1 & 0b0000_0011 // Least significant 2 bits\n    let byte2_green = byte2 & 0b1111_0000 // Most significant half of the byte\n    let byte2_blue = byte2 & 0b0000_1111 // Least significant half of the byte\n    let byte3_blue = byte3 & 0b1100_0000 // Most significant 2 bits\n    let byte3_purple = byte3 & 0b0011_1111 // Least significant 6 bits\n    let yellow = byte1_yellow >> 2\n    let green = byte1_green << 4 | byte2_green >> 4\n    let blue = byte2_blue << 2 | byte3_blue >> 6\n    let purple = byte3_purple\n    return (yellow, green, blue, purple)\n}\n```\nWe can optimize the function to the following if we're a little bit smarter about our bit operations:\n\n```\n/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let yellow = byte1 >> 2\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = ((byte1 & 0x03) << 4) | (byte2 >> 4)\n    let blue = ((byte2 & 0x0F) << 2) | (byte3 >> 6)\n    // 0x3F == 0b0011_1111\n    let purple = byte3 & 0x3F\n    return (yellow, green, blue, purple)\n}\n```\nIf you take a peek at the optimized x86-64 Assembly for the 2 functions, you'll notice both compile down to almost the same code:\n\n```\noutput.bytesToBase64(Swift.UInt8, Swift.UInt8, Swift.UInt8) -> (yellow: Swift.UInt8, green: Swift.UInt8, blue: Swift.UInt8, purple: Swift.UInt8): # @\"output.bytesToBase64(Swift.UInt8, Swift.UInt8, Swift.UInt8) -> (yellow: Swift.UInt8, green: Swift.UInt8, blue: Swift.UInt8, purple: Swift.UInt8)\"\n        mov     eax, edi\n        shr     al, 2\n        mov     ecx, esi\n        shr     cl, 4\n        shl     dil, 4\n        or      dil, cl\n        and     dil, 63\n        mov     ecx, edx\n        shr     cl, 6\n        shl     sil, 2\n        or      sil, cl\n        and     sil, 63\n        and     dl, 63\n        movzx   ecx, dl\n        shl     ecx, 24\n        movzx   edx, sil\n        shl     edx, 16\n        or      edx, ecx\n        movzx   ecx, dil\n        shl     ecx, 8\n        or      ecx, edx\n        movzx   eax, al\n        or      eax, ecx\n        ret\n```\nIt's ok if you have little to no idea what's all that. We're not doing an Assembly language deep dive in this post.\n\nThe takeaway is that the compiler was smart enough to do the optimizations for us.\n\nNo matter. We'll continue to use our presumably optimized version.\n\nLet's also implement the function that takes each Base64 value and converts them to ASCII codes:\n\n```\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII(_ value: UInt8) -> UInt8 {\n    if value <= 25 { return value + 65 }\n    if value <= 51 { return value + 71 }\n    if value <= 61 { return value - 4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}\n```\nIn essence, that's all we need to convert bytes to Base64-encoded characters. But how can we do it at tens of gigabytes per second?\n\n### \n\nBase64 encoding operates on 3 bytes at a time, but sometimes the number of bytes is indivisible by 3.\n\nWe'll simply ignore those cases for simplicity's sake, as those 1 or 2 remainder bytes have virtually no effect on performance in the long run when we're encoding 1_000_000 bytes (1 MB).\n\n### \n\nFurthermore, we'll use the default variant of Base64 encoding.\n\nOther variants make little difference to our comparisons, and they're simple enough in concept.\n\nFor example, the \"URL safe\" Base64-encoding variant merely replaces `+` with `-` and `/` with `_`.\n\n## \n\nOk then. Let's stitch the code snippets together so we can measure the performance of our Base64-encoding algorithm.\n\nFor best performance, you'd always want to drop down to a layer that gives you no-overhead access to the underlying contiguous storage of the bytes or values.\n\nIn Swift, this is best done via the `Span` family of types, which allow type-safe, lifetime-bound access to their underlying pointer of contiguous elements.\n\nIn most cases, these `Span` types perform just as well as the good (or bad) ol' `UnsafeBufferPointer` family of types, which behave much more like raw C pointers.\n\nHowever, in our case we'll use an `UnsafeMutableBufferPointer` instead of an `OutputSpan`, as the compiler, while very smart, struggles to notice that we're simply writing a fixed amount of consecutive bytes into the `OutputSpan` and fails to apply 1 very important optimization.\n\nMy general recommendation is to use the `Span` family of types, as they're commonly on par with their `UnsafeBufferPointer` counterparts, until you notice their higher safety is coming at an unacceptable cost.\n\nLet's get back to our Base64 implementation:\n\n```\n/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span<UInt8>,\n    into output: UnsafeMutableBufferPointer<UInt8>\n) {\n    precondition(bytes.count % 3 == 0, \"Bytes count needs to be a multiple of 3\")\n    precondition(output.count >= bytes.count / 3 * 4, \"Insufficient output capacity\")\n    let triples = bytes.count / 3\n    for triple in 0..<triples {\n        let index = triple * 3\n        let outputIndex = triple * 4\n        let byte1 = bytes[index]\n        let byte2 = bytes[index + 1]\n        let byte3 = bytes[index + 2]\n        let base64Values = bytesToBase64(byte1, byte2, byte3)\n        let encodedYellow = base64ValueToASCII(base64Values.yellow)\n        let encodedGreen = base64ValueToASCII(base64Values.green)\n        let encodedBlue = base64ValueToASCII(base64Values.blue)\n        let encodedPurple = base64ValueToASCII(base64Values.purple)\n        unsafe output[outputIndex] = encodedYellow\n        unsafe output[outputIndex + 1] = encodedGreen\n        unsafe output[outputIndex + 2] = encodedBlue\n        unsafe output[outputIndex + 3] = encodedPurple\n    }\n}\n/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let yellow = byte1 >> 2\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = ((byte1 & 0x03) << 4) | (byte2 >> 4)\n    let blue = ((byte2 & 0x0F) << 2) | (byte3 >> 6)\n    // 0x3F == 0b0011_1111\n    let purple = byte3 & 0x3F\n    return (yellow, green, blue, purple)\n}\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII(_ value: UInt8) -> UInt8 {\n    if value <= 25 { return value + 65 }\n    if value <= 51 { return value + 71 }\n    if value <= 61 { return value - 4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}\n```\nHere we will:\n\n- 1. Process 3 bytes at a time.\n- 2. Have to use the `unsafe` keyword as we're using an**Unsafe** MutableBufferPointer.\n  - We've enabled `strictMemorySafety` in our`Package.swift` , which encourages us to mark our unsafe memory accesses as such.\n- We've enabled \n\nLet's run a benchmark over this implementation.\n\nYou'll need to have followed [Support Material](https://blog.mahdibm.com#support-material) if you're running this command yourself.\n\n```\n$ swift package benchmark --target AutoVectorizationBenchs --filter '1_Naive_Loop.*'\n1_Naive_Loop_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │     13151 │     13550 │     13771 │     14074 │     14377 │     15196 │     15607 │      1000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │     16471 │     16523 │     16564 │     16646 │     16777 │     17105 │     18522 │      1000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n1_Naive_Loop_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │       361 │       343 │       338 │       327 │       316 │       293 │       227 │      1000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n```\nAt p50, this implementation performs ~340 rounds per second, each round encoding 1 MB of data (999_999 bytes, to be exact).\n\nThat's roughly 340 MB/s, or less than **0.34 GB/s**.\n\nAt first glance, it might appear that there is little left to optimize in that code.\n\nSwift does checked math by default, even in optimized builds, so as not to compromise on safety.\n\nThat's typically not true about code written in Rust or C/C++.\n\nMaybe if we use unchecked math, something will drastically change?\n\nOr we've heard divisions are slow. Maybe that division by 3 is the culprit?\n\nNot really.\n\nCompilers are smarter than that. Many math operations are already optimized, as the compiler can tell there is no way the numbers can, for example, overflow in any case.\n\nThe division by 3 is also outside the loop. It can't be hurting our performance too much. Anyway, compilers won't leave a division by a constant value as-is. They'll optimize divisions to multiplication + bit-shifts when the divisor is a compile-time constant. Try `func divisionBy3(number: Int) -> Int { number / 3 }` on [Compiler Explorer](https://godbolt.org/) and see for yourself.\n\nThe more performance-minded of you might come up with a great idea:\n\nWe have a very good case for using **Lookup Tables**.\n\n## \n\nRecall that for mapping Base64 values to ASCII characters, we follow the table below:\n\n| Base64 Value | 0 ... 25 | 26 ... 51 | 52 ... 61 | 62 | 63 | \n|---|---|---|---|---|---|\n| Corresponding Letter(s) | A ... Z | a ... z | 0 ... 9 | + | / | \n| Corresponding ASCII Codes (Decimal) | 65 ... 90 | 97 ... 122 | 48 ... 57 | 43 | 47 | \n| Corresponding ASCII Codes (Hex) | 0x41 ... 0x5A | 0x61 ... 0x7A | 0x30 ... 0x39 | 0x2B | 0x2F | \n\nThis is a very good case for using lookup tables.\n\nWe can index the table by the Base64 value and get the ASCII code-point out of it:\n\n```\n/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span<UInt8>,\n    into output: UnsafeMutableBufferPointer<UInt8>\n) {\n    precondition(bytes.count % 3 == 0, \"Bytes count needs to be a multiple of 3\")\n    precondition(output.count >= bytes.count / 3 * 4, \"Insufficient output capacity\")\n    let triples = bytes.count / 3\n    for triple in 0..<triples {\n        let index = triple * 3\n        let outputIndex = triple * 4\n        let byte1 = bytes[index]\n        let byte2 = bytes[index + 1]\n        let byte3 = bytes[index + 2]\n        let base64Values = bytesToBase64(byte1, byte2, byte3)\n        let encodedYellow = base64ValueToASCII_lookupTable(base64Values.yellow)\n        let encodedGreen = base64ValueToASCII_lookupTable(base64Values.green)\n        let encodedBlue = base64ValueToASCII_lookupTable(base64Values.blue)\n        let encodedPurple = base64ValueToASCII_lookupTable(base64Values.purple)\n        unsafe output[outputIndex] = encodedYellow\n        unsafe output[outputIndex + 1] = encodedGreen\n        unsafe output[outputIndex + 2] = encodedBlue\n        unsafe output[outputIndex + 3] = encodedPurple\n    }\n}\n```\nThis is a good showcase of LLVM's abilities to get rid of bounds checks where unnecessary.\n\nAs you can see in this simplified version of `InlineArray`'s (Rust's array equivalent) subscript implementation, it does contain some bounds-check preconditions when subscripting it like `base64Lut[Int(value)]`:\n\n```\nextension InlineArray {\n    /// Accesses the element at the specified position.\n    ///\n    /// - Parameter i: The position of the element to access. `i` must be a valid\n    ///   index of the array that is not equal to the `endIndex` property.\n    ///\n    /// - Complexity: O(1)\n    public subscript(_ i: Index) -> Element {\n        borrow {\n            precondition((0..<count).contains(i), \"Index out of bounds\")\n            let pointer = unsafe _address.project(i)\n            return unsafe pointer.pointee\n        }\n        mutate {\n            precondition((0..<count).contains(i), \"Index out of bounds\")\n            let pointer = unsafe _mutableAddress.project(i)\n            return unsafe &pointer.pointee\n        }\n    }\n}\n```\nBut if you take a look at an optimized representation of the code when inlined into the `encodeBytesToBase64` function, such as in the final Assembly, you'll notice there are no bounds checks inserted to ensure our `InlineArray` accesses are in-bounds:\n\n```\noutput.encodeBytesToBase64(bytes: Swift.Span<Swift.UInt8>, into: Swift.UnsafeMutableBufferPointer<Swift.UInt8>) -> (): # @\"output.encodeBytesToBase64(bytes: Swift.Span<Swift.UInt8>, into: Swift.UnsafeMutableBufferPointer<Swift.UInt8>) -> ()\"\n        lea     rcx, [rip + output.base64Lut : Swift.InlineArray<64, Swift.UInt8>]\n        movzx   r14d, byte ptr [r14 + rcx]\n        movzx   r10d, byte ptr [r10 + rcx]\n        movzx   ebx, byte ptr [rbx + rcx]\n        movzx   r11d, byte ptr [r11 + rcx]\n```\nThat's `base64Lut` right there, somehow being accessed. We don't care what the complete code means, but we do notice there are no bounds checks there. We can see no comparison to `63`. The compiler must've skipped the whole precondition check.\n\nIn comparison, the not-inlined version of the function does show the bounds check, as it can't be sure upfront that it won't receive a value that is in bounds or not. It doesn't matter to our implementation, but here's the code for the curious ones:\n\n```\noutput.base64ValueToASCII_lookupTable(Swift.UInt8) -> Swift.UInt8: # @\"output.base64ValueToASCII_lookupTable(Swift.UInt8) -> Swift.UInt8\"\n        cmp     dil, 63\n        ja      .LBB3_2\n        movzx   eax, dil\n        lea     rcx, [rip + output.base64Lut : Swift.InlineArray<64, Swift.UInt8>]\n        movzx   eax, byte ptr [rax + rcx]\n        ret\n.LBB3_2:\n        ud2\n```\nThe optimization happens because the compiler can see that `InlineArray` is a constant of 64 elements and prove that it's logically impossible to request an index outside `0…63` in the `encodeBytesToBase64` function.\n\nThis optimization is not limited to `InlineArray` and such optimizations are frequently done for more common and more complex types such as `Array` as well (which is a copy-on-write `Arc<Vec<T>>` in Rust terms).\n\nLet's benchmark:\n\n```\n$ swift package benchmark --target AutoVectorizationBenchs --filter '2_Lookup_Table.*'\n2_Lookup_Table_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │       956 │       975 │       977 │       979 │      1011 │      1412 │      1782 │     20000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │      8667 │      8675 │      8675 │      8675 │      8692 │      8757 │      9574 │     20000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n2_Lookup_Table_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │      4751 │      4703 │      4651 │      4503 │      3733 │      2197 │       724 │     20000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n```\nNice! The implementation is now doing **4.6 GB/s**. That's 14 times faster than the initial naive loop implementation.\n\nWhat if I told you we can have another 3-4x performance improvement if we pave the way for the compiler to **Auto-Vectorize** our loop?\n\n## \n\nTo put it in small words, Auto-Vectorization is Vectorization, but well … automatically done! Makes sense, right?\n\nWho does it automatically? The compiler. More specifically, LLVM.\n\nLLVM can automatically vectorize a certain group of loops and commonly make them much faster.\n\nTip\n\nAuto-Vectorization is subject to the same note that we started the post with. It's not limited to Swift.\n\nClang, GCC, Rust, Java and some more languages come with Auto-Vectorization capabilities.\n\nSwift and Rust are pretty friendly to Auto-Vectorization. Both leverage LLVM for it, so they behave similarly.\n\nIn our case, we're going to make our loop 3+ times faster.\n\nWe can even make it 6+ times faster, reaching **90x** performance over the original naive loop implementation. We'll also take a peek at that implementation.\n\n### \n\nVectorization can make your loops much faster. But how?\n\nThe CPU core is the same CPU core. Why does it just not run faster without needing this \"Vectorization\" thing, whatever it is?!?!!\n\nThe Vectorization we'll be making use of is the SIMD type of Vectorization.\n\nSIMD itself stands for **S**ingle **I**nstruction **M**ultiple **D**ata. The power of SIMD comes from the fact that you can tell it to run a specific operation on a wide group of data in one go.\n\nAs a more tangible example, you can tell your CPU: \"Hey, I have these 16 bytes. I want them all to be multiplied by 3, please!\"\n\nA SIMD instruction is only a *single instruction* that is operating on *multiple data*. These instructions sometimes don't even have latency or performance downsides compared to scalar instructions where there is no SIMD usage.\n\n### \n\nSIMD can work on 16 bytes at around the same speed that a scalar instruction would finish 1 byte's work.\n\nDoes that mean SIMD code will be 16 times faster than scalar code?\n\nNot really, but it depends on a few factors.\n\nCPUs nowadays leverage many techniques to be so fast. There are some notes you need to take into account:\n\n- 1. Today's Superscalar CPUs execute multiple instructions in a single cycle via a technique called \"Instruction-Level Parallelism\", without even using SIMD.\n- 2. SIMD code sometimes needs to go through extra hoops and operations to implement the same effect as scalar code.\n- 3. On the positive side, x86-64 CPUs usually accept 256 bits instead of 128, or up to 512 bits of data when they support the AVX-512 instruction set extension.\n  - That's 64 bytes instead of our 16 bytes, which is how wide the vector registers of Arm64 and Apple Silicon's M-series processors are.\n\nTip\n\nThe specific number of instructions a CPU core can execute in the same cycle depends on your CPU's generation, the instruction's latency and throughput, how many execution ports are available, and if the final code doesn't contain other structural hazards.\n\nTo give you an idea, around 5 addition instructions in the same cycle is a good assumption for a recent CPU until you can look up the specifics on a place such as [uops](https://uops.info/).\n\nWe'll benchmark our code on Arm64 on an M6 processor, so theoretically we're not even using the \"best in class\" CPUs in supporting SIMD instructions. Even then, we'll be able to greatly increase the performance of our algorithm.\n\n### \n\nYou might be wondering now, how can you even leverage SIMD?\n\nThere are multiple layers of abstractions you can use:\n\n- **Auto-Vectorization** : Your code will look pretty similar to normal code. The compiler will do the Vectorization.\n- **SIMD Support** : Most languages come with some sort of SIMD support built in. Swift has`SIMD` , C++26 has`std::simd` and Rust has`std::simd` in the nightlies.\n  - There are also libraries which sometimes provide better SIMD support. For example, [Google's Highway](https://github.com/google/highway) for C++.\n- There are also libraries which sometimes provide better SIMD support. For example, \n- **Compiler Intrinsics** : These are platform-dependent low-level functions that generally look like their related instructions and are provided by the compilers themselves. You'll closely call NEON, SSE and AVX instructions this way.\n- **Assembly** : Last but not least, you can simply write your vectorized code in Assembly itself.\n\nHistorically, Auto-Vectorization has been seen as \"not worth it\". However, as compilers get better at it and as more modern languages emerge, lots of the old concerns about Auto-Vectorization become history.\n\nFor instance, to use Auto-Vectorization in C, you'd have to worry about memory aliasing, unknown array sizes and alignment issues. In a modern language like Swift or Rust, these concerns are typically moot.\n\nFor lots of use-cases, Auto-Vectorization is sufficient, and its less-abstracted alternatives provide little advantage.\n\nHowever, for some other use-cases, you can squeeze a decent amount of extra performance by dropping down to some lower layer. That is, if you deem the extra performance to be worth the potential trouble.\n\n## \n\nThere are few resources on the web about Auto-Vectorization. Even the latest and greatest of max-effort LLMs struggle to get it right when pushed to their limits, since their training data is very limited in this space and they fail to adequately and properly research it themselves.\n\nThat's why I've decided to demystify Auto-Vectorization.\n\nIn the rest of this post, you'll learn a few tricks about how to Auto-Vectorize our Base64 implementation. I plan to share another post in the future that covers Auto-Vectorization in more depth and reveals more tricks on how to exploit it.\n\nAuto-Vectorization pays dividends when applied to loops, although it has use-cases [outside loops](https://llvm.org/docs/Vectorizers.html#the-slp-vectorizer) as well.\n\nThere are commands outside the interest of this post with which you can learn why LLVM has decided not to Auto-Vectorize a given code. We'll discuss them in future posts.\n\nThat being said, an experienced developer can tell with their bare eyes that our Base64 loop isn't getting Auto-Vectorized for 2 reasons: **lookup tables** usage and having **branches** in the loop.\n\n### \n\nUsing lookup tables in vectorized code is more restrictive than in scalar code.\n\n- On Arm64, your lookup tables must be small enough to fit in 4 vectors at most.\n  - So you can only afford up to 64 bytes (4 vectors, each 128 bits, which is 16 bytes) for a lookup table on Arm64.\n- On x86-64, there is also some support, and you can work your way to handle 64 bytes of lookup table depending on which AVX instruction set extensions your CPU supports.\n\nOne of the disadvantages of using Auto-Vectorization is that the compilers, for now, simply give up on Auto-Vectorization when they see a lookup table.\n\nThat's why we'll have to say farewell to our lookup table, and welcome back our iffy `base64ValueToASCII` function.\n\n### \n\nLet's take another look at what our Base64 value to ASCII code conversion function looks like:\n\n```\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII(_ value: UInt8) -> UInt8 {\n    if value <= 25 { return value + 65 }\n    if value <= 51 { return value + 71 }\n    if value <= 61 { return value - 4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}\n```\nThere are many ways to take a peek at the Assembly for that function.\n\nOne of the best and simplest ways is to use Godbolt's [Compiler Explorer](https://godbolt.org/).\n\nOn x86-64, it looks like this with optimizations turned on:\n\n```\noutput.base64ValueToASCII(Swift.UInt8) -> Swift.UInt8: # @\"output.base64ValueToASCII(Swift.UInt8) -> Swift.UInt8\"\n        mov     eax, edi\n        cmp     al, 25\n        ja      .LBB1_2\n        add     al, 65\n        ret\n.LBB1_2:\n        cmp     al, 51\n        ja      .LBB1_4\n        add     al, 71\n        ret\n.LBB1_4:\n        cmp     al, 61\n        ja      .LBB1_6\n        add     al, -4\n        ret\n.LBB1_6:\n        cmp     al, 62\n        setne   al\n        shl     al, 2\n        or      al, 43\n        ret\n```\nFor our purpose, what you need to notice are those 3 `ja` instructions. There are a limited amount of instructions for branching to some other place in the code, and `ja` is one of the prevalent ones. The `j` should be a giveaway of what it does: it **jumps** to some other location in the code, which qualifies as branching.\n\nGenerally speaking, you can think of a branch as an `if`. If the condition is matched, then **jump** to the location where the remainder of the code lives, or otherwise fall through.\n\nIn Swift terms, the Assembly code is equivalent to the following:\n\n```\nif value > 25 {\n    if value > 51 {\n        if value > 61 {\n            // A clever way to return 43 if value == 62, otherwise 47.\n            // 43 is `0b101011`, and 47 is `0b101111`.\n            // The only difference is the third least significant bit.\n            // So this code turns on the third least significant bit if `value != 62`.\n            let isNot62: UInt8 = (value == 62) ? 0 : 1\n            // `0b0` when `value == 62`, otherwise `0b100`.\n            let shifted: UInt8 = isNot62 << 2\n            // `0b101011` (43 == '+') when `value == 62`, otherwise `0b101111` (47 == '/').\n            return shifted | 43\n        } else {\n            return value - 4\n        }\n    } else {\n        return value + 71\n    }\n} else {\n    return value + 65\n}\n```\nThe only interesting note is that you can see the compiler optimizing those inner bits of the code for choosing between 43 and 47.\n\nIn this case, LLVM's cost model has decided that this function is better off being branchy than being branchless.\n\nIt could have very well decided that a branchless function will likely be worth it.\n\nAs a matter of fact, this function does compile to branchless code on Arm64 already.\n\nBut how can we push LLVM to make this function branchless everywhere?\n\nWhat hints can we give it so its cost model deems branchless code worthy, so Auto-Vectorization can kick in?\n\n### \n\nx86-64 and Arm64 come with a set of **conditional operation instructions**. These are more limited in tasks they can handle, but as long as you use them, or rather, you get your compiler to use them, your code will be branchless.\n\nWe just need to get LLVM on board with our decision to not emit branchy code for our `if` conditions.\n\n**If-Conversion** is the process of eliminating branches by converting them into conditional instructions.\n\nHow can we consistently convince the compiler to apply If-Conversion to our code?\n\nThere is a simple hint we can give to LLVM to encourage it to output branchless code. However, we need to strengthen our background to later understand why the trick even works.\n\nHas it yet occurred to you why there is such a thing as branchy code and branchless code? Why both? Can't the compiler or the CPUs just use the one that's superior?\n\nThe answer is that neither of them is superior to the other in a general setting.\n\nThey are situational. Sometimes branchless code is faster and sometimes branchy code.\n\nAnd some other times you must use a specific one of them in any case. For example, for Auto-Vectorization we have no other choice than to use branchless code in the vast majority of cases, as that's what compilers accept and it's how you can squeeze maximum performance out of SIMD instructions.\n\nBut when is branchless code better and when is branchy code better?\n\nIt all depends on how *well-predicted* a branch will be.\n\nIf a branch is well-predicted, you're much better off letting it be.\n\nIf it's a frequently mispredicted branch, then you should consider performing an If-Conversion and making it branchless.\n\nWhat even is a well-predicted or mispredicted branch?\n\nFor performance reasons, CPUs always make an educated guess about whether a branch is going to resolve to true or not, and preemptively execute that code path.\n\nThis typically results in big performance wins, but if the branch is unpredictable and the CPU's smart branch predictors can't keep up with it, it can backfire. It depends on multiple factors, but as a rule of thumb, if a branch is mispredicted more than ~25% of the time, a branchless version of that code might be faster than the branchy version, on average.\n\nThe win in using branchy code is that if the branch is well-predicted, your CPU will mostly only execute the correct code path, even before it can confirm the code path is indeed the correct one.\n\nBut if it mispredicts the branch too often, it'll often have to stall and flush its pipeline of executed instructions and start executing the correct path all over again.\n\nBranchless code is the complete opposite. The idea is that \"I know the CPU will frequently mispredict these branches, so let's do the full work anyway\".\n\nWith a frequently mispredicted branch, the CPU will execute the wrong code path, later realize \"Oh shoot, this is not the right code path!\", flush and stall its instruction pipeline, and only then execute the correct code path.\n\nWith branchless code, we simply admit defeat upfront and accept calculating both code paths together so we can calculate the correct value without branching around.\n\nLet's reiterate.\n\nThe advantage of branchy code is that when the branch is well-predicted, only the right code path is executed, commonly ahead of time.\n\nThe win is in executing less instructions, faster.\n\nWe need to give some hints to the compiler to say that we're ok with it executing all code paths of our function, and we're not interested in savings that possible branchy code can come with, if the branches are well-predicted.\n\nAt that point, LLVM's cost model will likely deem branchless code worthy. After all, we're already calculating all the work. There wouldn't be a sufficient win in being branchy anymore.\n\n### \n\nThe trick is to calculate all the values upfront so LLVM is much more inclined to produce branchless code:\n\n```\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Codes  | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula      | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII_branchless_v1(_ value: UInt8) -> UInt8 {\n    let compare25 = value <= 25\n    let compare51 = value <= 51\n    let compare61 = value <= 61\n    let compare62 = value == 62\n    let plus65 = value &+ 65\n    let plus71 = value &+ 71\n    let minus4 = value &- 4\n    if compare25 { return plus65 }\n    if compare51 { return plus71 }\n    if compare61 { return minus4 }\n    if compare62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}\n```\nWe also have to use unchecked math. The function is logically the same as the original branchy code, which would never result in an overflow. We know that overflows are not possible here for the final return value. We only use unchecked math to convince the compiler to not crash if one of the calculations overflows. We won't use any such overflowed results anyway.\n\nOf note, Swift's mathematical operations are always checked, even in release builds, unlike a language like Rust, which by default gets rid of checks in math operations in optimized builds.\n\nChecked math's primary use-case is to ensure there are no overflows. Without checked math, numbers will simply wrap around when they no longer fit:\n\n```\n// WITH checked math\nlet number: UInt8 = 250 + 21 // CRASH\n// WITH UNchecked math\nlet number: UInt8 = 250 &+ 21 // = 15 (logically (250 + 21) % 256)\n```\nAlright. Is it finally branchless? Let's consult Compiler Explorer:\n\n```\noutput.base64ValueToASCII_branchless_v1(Swift.UInt8) -> Swift.UInt8: # @\"output.base64ValueToASCII_branchless_v1(Swift.UInt8) -> Swift.UInt8\"\n        cmp     dil, 62\n        setne   al\n        lea     ecx, [rdi - 4]\n        shl     al, 2\n        or      al, 43\n        cmp     dil, 62\n        movzx   ecx, cl\n        movzx   edx, al\n        cmovb   edx, ecx\n        cmp     dil, 26\n        mov     eax, 65\n        mov     ecx, 71\n        cmovb   ecx, eax\n        add     cl, dil\n        cmp     dil, 52\n        movzx   eax, cl\n        cmovae  eax, edx\n        ret\n```\nNice! The `j`ump instructions have ceased to exist!\n\nWe can also see a few conditional-move instructions to implement our function as branchless.\n\nThis trick works in most cases, but if a branch is too heavy, LLVM can still elect to not write the whole code as branchless. At that point, we'll need to apply some more common tricks, such as utilizing *speculative writes*.\n\nLuckily, we don't need that trick right now.\n\nThis code will perform pretty well. However, while we have Compiler Explorer opened up, we can play with the composition of values a little bit and see if any other changes result in better code.\n\nAfter playing with it for a few minutes, it appears LLVM generates better code when we don't hoist the `value == 62` comparison:\n\n```\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII_branchless(_ value: UInt8) -> UInt8 {\n    let compare25 = value <= 25\n    let compare51 = value <= 51\n    let compare61 = value <= 61\n    let plus65 = value &+ 65\n    let plus71 = value &+ 71\n    let minus4 = value &- 4\n    if compare25 { return plus65 }\n    if compare51 { return plus71 }\n    if compare61 { return minus4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}\n```\nHow does the Assembly look?\n\n```\noutput.base64ValueToASCII_branchless(Swift.UInt8) -> Swift.UInt8: # @\"output.base64ValueToASCII_branchless(Swift.UInt8) -> Swift.UInt8\"\n        cmp     dil, 26\n        mov     eax, 65\n        mov     ecx, 71\n        cmovb   ecx, eax\n        cmp     dil, 52\n        mov     eax, 252\n        cmovb   eax, ecx\n        add     al, dil\n        cmp     dil, 62\n        setne   cl\n        shl     cl, 2\n        or      cl, 43\n        cmp     dil, 62\n        movzx   edx, al\n        movzx   eax, cl\n        cmovb   eax, edx\n        ret\n```\nWe shaved a single instruction, what a victory!\n\nThe rest of the instructions are also very similar to the previous implementation's instructions, so it's unlikely that we have 1 instruction less but the performance would still regress or cease to improve.\n\nThere are many ways to take a peek at how the functions would compare, such as using machine code analyzers. The simplest way is, however, to benchmark the code. I've tried that, and indeed this new function performs better by ~12%.\n\nVery good. The code we wrote is now branchless. But is the whole loop actually branchless now? No.\n\n### \n\nSome other common branchy operations in Swift are the collection subscripts.\n\nIn order to ensure they don't access out-of-bounds memory, they come with a precondition that will crash the process before you can access memory that is not yours. This is similar to our previous look at `InlineArray`'s subscript:\n\n```\nextension Span {\n    /// Accesses the element at the specified index in the `Span`.\n    ///\n    /// - Parameter position: The offset of the element to access. `position`\n    ///     must be greater or equal to zero, and less than `count`.\n    ///\n    /// - Complexity: O(1)\n    public subscript(_ position: Index) -> Element {\n        borrow {\n            precondition((0..<count).contains(position), \"Index out of bounds\")\n            return unsafe self[unchecked: position]\n        }\n    }\n}\n```\nIn many cases these preconditions are optimized out by LLVM. Even if they're not optimized out, they normally cost little to no performance as they are quickly identified as unused branches by CPUs.\n\nHowever, the compiler is not smart enough to optimize out the preconditions in our case, even though logically there is no way we're accessing out-of-bounds memory of the `Span<UInt8>`.\n\nWe'll use the unchecked `Span` subscripts to dodge the preconditions being inserted into our code when subscripting `bytes`.\n\nIn a widely used implementation, depending on the stakes and our confidence in the implementation, we would also accompany this code with rigorous unit tests, occasional fuzz-testing, and more recently with LLM-assisted security analysis to ensure there is no hole in our logic. However, we'll skip those in this post.\n\n`UnsafeBufferPointer`s, on the other hand, come with a mere assertion. That is, their subscripts will guard against out-of-bounds access, but not in optimized and release builds. Therefore, they have no `unchecked` accessors anyway. This means we don't need to modify the `output` buffer writes to avoid any possible precondition checks.\n\nThe index calculations don't need any unchecked math operations. They're light work for the compiler to optimize.\n\nAt last, let's put our branchless code together and see how it performs:\n\n```\n/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span<UInt8>,\n    into output: UnsafeMutableBufferPointer<UInt8>\n) {\n    precondition(bytes.count % 3 == 0, \"Bytes count needs to be a multiple of 3\")\n    precondition(output.count >= bytes.count / 3 * 4, \"Insufficient output capacity\")\n    let triples = bytes.count / 3\n    for triple in 0..<triples {\n        let index = triple * 3\n        let outputIndex = triple * 4\n        let byte1 = unsafe bytes[unchecked: index]\n        let byte2 = unsafe bytes[unchecked: index + 1]\n        let byte3 = unsafe bytes[unchecked: index + 2]\n        let base64Values = bytesToBase64(byte1, byte2, byte3)\n        let encodedYellow = base64ValueToASCII_branchless(base64Values.yellow)\n        let encodedGreen = base64ValueToASCII_branchless(base64Values.green)\n        let encodedBlue = base64ValueToASCII_branchless(base64Values.blue)\n        let encodedPurple = base64ValueToASCII_branchless(base64Values.purple)\n        unsafe output[outputIndex] = encodedYellow\n        unsafe output[outputIndex + 1] = encodedGreen\n        unsafe output[outputIndex + 2] = encodedBlue\n        unsafe output[outputIndex + 3] = encodedPurple\n    }\n}\n/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let yellow = byte1 >> 2\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = ((byte1 & 0x03) << 4) | (byte2 >> 4)\n    let blue = ((byte2 & 0x0F) << 2) | (byte3 >> 6)\n    // 0x3F == 0b0011_1111\n    let purple = byte3 & 0x3F\n    return (yellow, green, blue, purple)\n}\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII_branchless(_ value: UInt8) -> UInt8 {\n    let compare25 = value <= 25\n    let compare51 = value <= 51\n    let compare61 = value <= 61\n    let plus65 = value &+ 65\n    let plus71 = value &+ 71\n    let minus4 = value &- 4\n    if compare25 { return plus65 }\n    if compare51 { return plus71 }\n    if compare61 { return minus4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}\n```\nLet's benchmark:\n\n```\n$ swift package benchmark --target AutoVectorizationBenchs --filter '3_Auto_Vectorized.*'\n3_Auto_Vectorized_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │       284 │       285 │       285 │       286 │       348 │       422 │       580 │     50000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │      1105 │      1106 │      1106 │      1106 │      1116 │      1209 │      1575 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n3_Auto_Vectorized_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │     16140 │     16087 │     16007 │     15647 │     11959 │      7359 │      1557 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n```\nSplendid! **16 GB/s**, up from 4.6 GB/s of the non-vectorized implementation.\n\nBut how can we tell whether it's actually Auto-Vectorized or not?\n\nFor one, the performance of the loop should lift your eyebrows. It's probably Auto-Vectorized, or it wouldn't be this fast.\n\nBut in general, there are multiple ways to tell a code is Auto-Vectorized. You can read the Assembly as an example.\n\nHowever, there is a no-brainer way that requires no understanding of other representations of the code:\n\nYou can check the optimized LLVM IR representation of your code and simply search for `vector.body:`.\n\nIf there is such text in the generated IR, it means your code has indeed been Auto-Vectorized.\n\nLet's try it out for ourselves. We'll use Godbolt. We normally only pass the `-O` compiler flag to request optimized code. We'll now add an extra `-emit-ir` flag to request the LLVM IR representation instead of the generated Assembly:\n\n```\nvector.body:\n  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ], !dbg !267\n  %18 = shl i64 %index, 2, !dbg !269\n```\nThere it is! The confirmation that our loop is truly vectorized.\n\nThis is where we stopped with Swift's own [swift-foundation](https://github.com/swiftlang/swift-foundation) Base64 [encoding implementation](https://github.com/swiftlang/swift-foundation/pull/2236). But you can reach for even higher performance.\n\nWhat if we could use our lookup table in combination with Vectorization? Let's take a brief look.\n\n## \n\nLuckily for us, the lookup table is exactly 64 bytes and no more, which is the maximum size we can afford on Arm64 without tricks.\n\nThat means we can use a lookup table for our Base64 implementation. Just not with Auto-Vectorization. Not yet, at least.\n\nManually writing vectorized code will have to be the subject of a future post, but I'll give you a sneak peek of it.\n\nVia my early-stage work-in-progress port of [Google's Highway](https://github.com/google/highway) to Swift, you can write the following code, which is inspired by [Daniel Lemire](https://github.com/lemire) and [Wojciech Muła](https://github.com/WojciechMula)'s [Base64 implementation](https://github.com/simdutf/simdutf):\n\n```\n/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span<UInt8>,\n    into output: UnsafeMutableBufferPointer<UInt8>\n) {\n    precondition(bytes.count % 3 == 0, \"Bytes count needs to be a multiple of 3\")\n    precondition(output.count >= bytes.count / 3 * 4, \"Insufficient output capacity\")\n    let bytesPerIteration = SIMDUInt8.laneCount * 3\n    let outputBytesPerIteration = SIMDUInt8.laneCount * 4\n    let iterations = bytes.count / bytesPerIteration\n    withAlignedBase64Lut { base64Lut in\n        for iteration in 0..<iterations {\n            let index = iteration * bytesPerIteration\n            let outputIndex = iteration * outputBytesPerIteration\n            var byte1 = SIMDUInt8.zero()\n            var byte2 = SIMDUInt8.zero()\n            var byte3 = SIMDUInt8.zero()\n            SIMDUInt8.loadInterleaved3(\n                from: bytes.extracting(droppingFirst: index), &byte1, &byte2, &byte3\n            )\n            let base64Values = bytesToBase64_vectorized(byte1, byte2, byte3)\n            let encodedYellow = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.yellow, base64Lut: base64Lut\n            )\n            let encodedGreen = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.green, base64Lut: base64Lut\n            )\n            let encodedBlue = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.blue, base64Lut: base64Lut\n            )\n            let encodedPurple = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.purple, base64Lut: base64Lut\n            )\n            unsafe SIMDUInt8.storeInterleaved4(\n                encodedYellow, encodedGreen, encodedBlue, encodedPurple,\n                to: output.baseAddress.unsafelyUnwrapped + outputIndex\n            )\n        }\n    }\n    /// The last bytes that weren't enough for a full `bytesPerIteration` iteration.\n    let remainingBytes = bytes.extracting(droppingFirst: iterations * bytesPerIteration)\n    let remainingOutput = unsafe UnsafeMutableBufferPointer(\n        rebasing: output[(iterations * outputBytesPerIteration)...]\n    )\n    unsafe AutoVectorized().encodeBytesToBase64(bytes: remainingBytes, into: remainingOutput)\n}\n/// Receives 3 vectors of bytes, returns 4 vectors of base-64 values, each in range of 0 to 63.\nfunc bytesToBase64_vectorized(\n    _ byte1: SIMDUInt8.Vector,\n    _ byte2: SIMDUInt8.Vector,\n    _ byte3: SIMDUInt8.Vector\n) -> (\n    yellow: SIMDUInt8.Vector,\n    green: SIMDUInt8.Vector,\n    blue: SIMDUInt8.Vector,\n    purple: SIMDUInt8.Vector\n) {\n    let yellow = SIMDUInt8.shiftedRight(byte1, by: 2)\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = SIMDUInt8.bitwiseOr(\n        SIMDUInt8.shiftedLeft(\n            SIMDUInt8.bitwiseAnd(byte1, SIMDUInt8.repeating(0x03)), by: 4\n        ),\n        SIMDUInt8.shiftedRight(byte2, by: 4)\n    )\n    let blue = SIMDUInt8.bitwiseOr(\n        SIMDUInt8.shiftedLeft(\n            SIMDUInt8.bitwiseAnd(byte2, SIMDUInt8.repeating(0x0F)), by: 2\n        ),\n        SIMDUInt8.shiftedRight(byte3, by: 6)\n    )\n    // 0x3F == 0b0011_1111\n    let purple = SIMDUInt8.bitwiseAnd(byte3, SIMDUInt8.repeating(0x3F))\n    return (yellow, green, blue, purple)\n}\n/// The Base64 Lookup Table (LUT) as an inline array.\nstatic let base64Lut: InlineArray<64, UInt8> = [\n    UInt8(ascii: \"A\"), UInt8(ascii: \"B\"), UInt8(ascii: \"C\"), UInt8(ascii: \"D\"),\n    UInt8(ascii: \"E\"), UInt8(ascii: \"F\"), UInt8(ascii: \"G\"), UInt8(ascii: \"H\"),\n    UInt8(ascii: \"I\"), UInt8(ascii: \"J\"), UInt8(ascii: \"K\"), UInt8(ascii: \"L\"),\n    UInt8(ascii: \"M\"), UInt8(ascii: \"N\"), UInt8(ascii: \"O\"), UInt8(ascii: \"P\"),\n    UInt8(ascii: \"Q\"), UInt8(ascii: \"R\"), UInt8(ascii: \"S\"), UInt8(ascii: \"T\"),\n    UInt8(ascii: \"U\"), UInt8(ascii: \"V\"), UInt8(ascii: \"W\"), UInt8(ascii: \"X\"),\n    UInt8(ascii: \"Y\"), UInt8(ascii: \"Z\"), UInt8(ascii: \"a\"), UInt8(ascii: \"b\"),\n    UInt8(ascii: \"c\"), UInt8(ascii: \"d\"), UInt8(ascii: \"e\"), UInt8(ascii: \"f\"),\n    UInt8(ascii: \"g\"), UInt8(ascii: \"h\"), UInt8(ascii: \"i\"), UInt8(ascii: \"j\"),\n    UInt8(ascii: \"k\"), UInt8(ascii: \"l\"), UInt8(ascii: \"m\"), UInt8(ascii: \"n\"),\n    UInt8(ascii: \"o\"), UInt8(ascii: \"p\"), UInt8(ascii: \"q\"), UInt8(ascii: \"r\"),\n    UInt8(ascii: \"s\"), UInt8(ascii: \"t\"), UInt8(ascii: \"u\"), UInt8(ascii: \"v\"),\n    UInt8(ascii: \"w\"), UInt8(ascii: \"x\"), UInt8(ascii: \"y\"), UInt8(ascii: \"z\"),\n    UInt8(ascii: \"0\"), UInt8(ascii: \"1\"), UInt8(ascii: \"2\"), UInt8(ascii: \"3\"),\n    UInt8(ascii: \"4\"), UInt8(ascii: \"5\"), UInt8(ascii: \"6\"), UInt8(ascii: \"7\"),\n    UInt8(ascii: \"8\"), UInt8(ascii: \"9\"), UInt8(ascii: \"+\"), UInt8(ascii: \"/\"),\n]\n```\nHow does this perform?\n\n```\n$ swift package benchmark --target AutoVectorizationBenchs --filter '4_Vectorized_With_Lookup_Table.*'\n4_Vectorized_With_Lookup_Table_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │       153 │       154 │       155 │       159 │       208 │       252 │       397 │     50000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │       522 │       522 │       522 │       522 │       523 │       569 │       762 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n4_Vectorized_With_Lookup_Table_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │     29667 │     29487 │     29199 │     28639 │     27439 │     19199 │      2843 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n```\nOn the cusp of **30 GB/s**, 90 times faster than our original naive loop!\n\nWhat does **30 GB/s** even mean?\n\nIt's 30 billion bytes per second, or 30 bytes per nanosecond, or around 6 bytes per clock cycle, on average.\n\nThink about it for a second. We're encoding 6 bytes to 8 Base64-encoded characters in each CPU cycle with this implementation.\n\n## \n\nHere's how the 4 different implementations compare to each other, alongside [Daniel Lemire](https://github.com/lemire)'s own implementation in C++, which is a full implementation with all the bells and whistles:\n\n```\nswift package benchmark --target AutoVectorizationBenchs\n```\n| Implementation | p50 | Instructions | Cycles | \n|---|---|---|---|\n| Naive loop | 0.34 GB/s | 16600 K | 13800 K | \n| Lookup table | 4.6 GB/s | 8700 K | 980 K | \n| Auto-Vectorized | 16.0 GB/s | 1100 K | 285 K | \n| [Lemire (C++)](https://github.com/simdutf/simdutf) | 27.8 GB/s | 420 K | 165 K | \n| Vectorized + LUT | 29.2 GB/s | 520 K | 155 K | \n\n## \n\nAs always, I'm open to any kinds of suggestions, be it technical or not.\n\nIf you'd like to discuss this post, I've opened up [this thread](https://forums.swift.org/t/blog-post-practical-auto-vectorization-not-llm-generated-per-usual/) on Swift's forums. I'll be waiting for you there.\n\nI'll be happy to know what parts of this post you'd like to know more about in the future.\n\nThank you for reading right through the end.","body_html":"<h1 id=\"practical-auto-vectorization\">Practical Auto-Vectorization</h1>\n<p>In this post, we&#39;ll use Vectorization to optimize our Base64 implementation to perform <strong>tens of gigabytes per second</strong>. We&#39;ll also take a brief look at an implementation that performs ~<strong>30 GB/s</strong>.</p>\n<p>We&#39;ll see how I made Apple&#39;s <a href=\"https://github.com/swiftlang/swift-foundation\" rel=\"nofollow ugc noopener\">swift-foundation</a> Base64 encoding <a href=\"https://github.com/swiftlang/swift-foundation/pull/2236\" rel=\"nofollow ugc noopener\">~3 times faster</a>, and how you can even surpass that.</p>\n<p>I&#39;ll also share some tips and tricks for leveraging Auto-Vectorization. Tips that the latest and greatest LLMs repeatedly failed to figure out at their maximum effort, when I was first trying out Auto-Vectorization.</p>\n<p>## </p>\n<p>## </p>\n<p>You can checkout this post&#39;s related commit to test out the implementations and measurements.</p>\n<p>You&#39;ll need to have Swift 6.4 and above installed on a Linux or macOS system to run the benchmarks.</p>\n<pre><code>git clone https://github.com/MahdiBM/blog-material\ncd blog-material\ngit switch --detach c63c91e7695c1c2c47828508ee636e19c5709859</code></pre>\n<p>In the post, measurements also mention their related benchmark command.</p>\n<p>## </p>\n<p>We&#39;ll use Base64 encoding as it&#39;s pretty simple and is a good showcase of the different optimizations.</p>\n<p>We&#39;ll use the Swift programming language, but pretty much all optimizations are done at the LLVM layer, so most optimization notes apply to Rust as well.</p>\n<p>## </p>\n<p>Let&#39;s take a quick look at the Base64 encoding. It&#39;s pretty simple. We need to understand it before attempting to optimize it.</p>\n<p>The Base64 format was created as a way to transfer raw data over a medium which merely accepts text.</p>\n<p>So what it does is to disguise raw data as if it&#39;s normal text. The text will indeed look like gibberish, but that&#39;s ok.</p>\n<p>To achieve this, Base64 encoding operates on 3 bytes at a time and outputs 4 Base64 values. Then it maps each of those 4 Base64 values to a corresponding ASCII character, which is typically alphanumeric, so it ticks the box of looking like normal text.</p>\n<p>We&#39;ll use the following bytes as examples:</p>\n<div class=\"table-wrap\"><table><thead><tr><th>Byte 1</th><th>Byte 2</th><th>Byte 3</th></tr></thead><tbody><tr><td>0b11000100</td><td>0b10101111</td><td>0b10110111</td></tr></tbody></table></div>\n<p>As you can see, the 3 bytes, represented as 3 unsigned 8-bit integers, amount to a total of 24 bits.</p>\n<p>Base64 reads 6 bits at a time and gathers 4 6-bit values out of those 24 bits.</p>\n<p>Note</p>\n<p><code>0b</code> is not part of the value. It simply denotes <strong>Binary</strong> notation.</p>\n<p>Tip</p>\n<p>Notice the colors and the byte names. We&#39;ll use those colors and the specific <code>byte1</code> / <code>byte2</code> / <code>byte3</code> names throughout, so the post is easier to follow.</p>\n<p>Thereafter, it maps each value to an ASCII code-point with the knowledge that each value is only 6 bits, so it must be in range of 0 (0b000000) to 63 (0b111111):</p>\n<div class=\"table-wrap\"><table><thead><tr><th>Base64 Value</th><th>0 ... 25</th><th>26 ... 51</th><th>52 ... 61</th><th>62</th><th>63</th></tr></thead><tbody><tr><td>Corresponding Letter(s)</td><td>A ... Z</td><td>a ... z</td><td>0 ... 9</td><td>+</td><td>/</td></tr><tr><td>Corresponding ASCII Codes (Decimal)</td><td>65 ... 90</td><td>97 ... 122</td><td>48 ... 57</td><td>43</td><td>47</td></tr><tr><td>Corresponding ASCII Codes (Hex)</td><td>0x41 ... 0x5A</td><td>0x61 ... 0x7A</td><td>0x30 ... 0x39</td><td>0x2B</td><td>0x2F</td></tr></tbody></table></div>\n<p>Note</p>\n<p><code>0x</code> is not part of the value. It simply denotes <strong>Hexadecimal</strong> notation.</p>\n<p>So in this specific case, our 4 Base64 values will be:</p>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th>Base64 Value 1</th><th>Base64 Value 2</th><th>Base64 Value 3</th><th>Base64 Value 4</th></tr></thead><tbody><tr><td>Binary Value</td><td>0b110001</td><td>0b001010</td><td>0b111110</td><td>0b110111</td></tr><tr><td>Decimal Value</td><td>49</td><td>10</td><td>62</td><td>55</td></tr><tr><td>ASCII Mapping (Decimal)</td><td>120</td><td>75</td><td>43</td><td>51</td></tr><tr><td>ASCII Mapping (Hex)</td><td>0x78</td><td>0x4B</td><td>0x2B</td><td>0x33</td></tr><tr><td>ASCII Mapping (Character)</td><td><code>x</code></td><td><code>K</code></td><td><code>+</code></td><td><code>3</code></td></tr></tbody></table></div>\n<p>When you see a Base64-encoded text on the web, you&#39;re looking at the &quot;ASCII Mapping&quot; characters of the Base64 values.</p>\n<p>### </p>\n<p>We&#39;ll implement the bytes-to-Base64-values function like so:</p>\n<pre><code>/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -&gt; (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let byte1_yellow = byte1 &amp; 0b1111_1100 // All but the least significant 2 bits\n    let byte1_green = byte1 &amp; 0b0000_0011 // Least significant 2 bits\n    let byte2_green = byte2 &amp; 0b1111_0000 // Most significant half of the byte\n    let byte2_blue = byte2 &amp; 0b0000_1111 // Least significant half of the byte\n    let byte3_blue = byte3 &amp; 0b1100_0000 // Most significant 2 bits\n    let byte3_purple = byte3 &amp; 0b0011_1111 // Least significant 6 bits\n    let yellow = byte1_yellow &gt;&gt; 2\n    let green = byte1_green &lt;&lt; 4 | byte2_green &gt;&gt; 4\n    let blue = byte2_blue &lt;&lt; 2 | byte3_blue &gt;&gt; 6\n    let purple = byte3_purple\n    return (yellow, green, blue, purple)\n}</code></pre>\n<p>We can optimize the function to the following if we&#39;re a little bit smarter about our bit operations:</p>\n<pre><code>/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -&gt; (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let yellow = byte1 &gt;&gt; 2\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = ((byte1 &amp; 0x03) &lt;&lt; 4) | (byte2 &gt;&gt; 4)\n    let blue = ((byte2 &amp; 0x0F) &lt;&lt; 2) | (byte3 &gt;&gt; 6)\n    // 0x3F == 0b0011_1111\n    let purple = byte3 &amp; 0x3F\n    return (yellow, green, blue, purple)\n}</code></pre>\n<p>If you take a peek at the optimized x86-64 Assembly for the 2 functions, you&#39;ll notice both compile down to almost the same code:</p>\n<pre><code>output.bytesToBase64(Swift.UInt8, Swift.UInt8, Swift.UInt8) -&gt; (yellow: Swift.UInt8, green: Swift.UInt8, blue: Swift.UInt8, purple: Swift.UInt8): # @&quot;output.bytesToBase64(Swift.UInt8, Swift.UInt8, Swift.UInt8) -&gt; (yellow: Swift.UInt8, green: Swift.UInt8, blue: Swift.UInt8, purple: Swift.UInt8)&quot;\n        mov     eax, edi\n        shr     al, 2\n        mov     ecx, esi\n        shr     cl, 4\n        shl     dil, 4\n        or      dil, cl\n        and     dil, 63\n        mov     ecx, edx\n        shr     cl, 6\n        shl     sil, 2\n        or      sil, cl\n        and     sil, 63\n        and     dl, 63\n        movzx   ecx, dl\n        shl     ecx, 24\n        movzx   edx, sil\n        shl     edx, 16\n        or      edx, ecx\n        movzx   ecx, dil\n        shl     ecx, 8\n        or      ecx, edx\n        movzx   eax, al\n        or      eax, ecx\n        ret</code></pre>\n<p>It&#39;s ok if you have little to no idea what&#39;s all that. We&#39;re not doing an Assembly language deep dive in this post.</p>\n<p>The takeaway is that the compiler was smart enough to do the optimizations for us.</p>\n<p>No matter. We&#39;ll continue to use our presumably optimized version.</p>\n<p>Let&#39;s also implement the function that takes each Base64 value and converts them to ASCII codes:</p>\n<pre><code>/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII(_ value: UInt8) -&gt; UInt8 {\n    if value &lt;= 25 { return value + 65 }\n    if value &lt;= 51 { return value + 71 }\n    if value &lt;= 61 { return value - 4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}</code></pre>\n<p>In essence, that&#39;s all we need to convert bytes to Base64-encoded characters. But how can we do it at tens of gigabytes per second?</p>\n<p>### </p>\n<p>Base64 encoding operates on 3 bytes at a time, but sometimes the number of bytes is indivisible by 3.</p>\n<p>We&#39;ll simply ignore those cases for simplicity&#39;s sake, as those 1 or 2 remainder bytes have virtually no effect on performance in the long run when we&#39;re encoding 1_000_000 bytes (1 MB).</p>\n<p>### </p>\n<p>Furthermore, we&#39;ll use the default variant of Base64 encoding.</p>\n<p>Other variants make little difference to our comparisons, and they&#39;re simple enough in concept.</p>\n<p>For example, the &quot;URL safe&quot; Base64-encoding variant merely replaces <code>+</code> with <code>-</code> and <code>/</code> with <code>_</code>.</p>\n<p>## </p>\n<p>Ok then. Let&#39;s stitch the code snippets together so we can measure the performance of our Base64-encoding algorithm.</p>\n<p>For best performance, you&#39;d always want to drop down to a layer that gives you no-overhead access to the underlying contiguous storage of the bytes or values.</p>\n<p>In Swift, this is best done via the <code>Span</code> family of types, which allow type-safe, lifetime-bound access to their underlying pointer of contiguous elements.</p>\n<p>In most cases, these <code>Span</code> types perform just as well as the good (or bad) ol&#39; <code>UnsafeBufferPointer</code> family of types, which behave much more like raw C pointers.</p>\n<p>However, in our case we&#39;ll use an <code>UnsafeMutableBufferPointer</code> instead of an <code>OutputSpan</code>, as the compiler, while very smart, struggles to notice that we&#39;re simply writing a fixed amount of consecutive bytes into the <code>OutputSpan</code> and fails to apply 1 very important optimization.</p>\n<p>My general recommendation is to use the <code>Span</code> family of types, as they&#39;re commonly on par with their <code>UnsafeBufferPointer</code> counterparts, until you notice their higher safety is coming at an unacceptable cost.</p>\n<p>Let&#39;s get back to our Base64 implementation:</p>\n<pre><code>/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span&lt;UInt8&gt;,\n    into output: UnsafeMutableBufferPointer&lt;UInt8&gt;\n) {\n    precondition(bytes.count % 3 == 0, &quot;Bytes count needs to be a multiple of 3&quot;)\n    precondition(output.count &gt;= bytes.count / 3 * 4, &quot;Insufficient output capacity&quot;)\n    let triples = bytes.count / 3\n    for triple in 0..&lt;triples {\n        let index = triple * 3\n        let outputIndex = triple * 4\n        let byte1 = bytes[index]\n        let byte2 = bytes[index + 1]\n        let byte3 = bytes[index + 2]\n        let base64Values = bytesToBase64(byte1, byte2, byte3)\n        let encodedYellow = base64ValueToASCII(base64Values.yellow)\n        let encodedGreen = base64ValueToASCII(base64Values.green)\n        let encodedBlue = base64ValueToASCII(base64Values.blue)\n        let encodedPurple = base64ValueToASCII(base64Values.purple)\n        unsafe output[outputIndex] = encodedYellow\n        unsafe output[outputIndex + 1] = encodedGreen\n        unsafe output[outputIndex + 2] = encodedBlue\n        unsafe output[outputIndex + 3] = encodedPurple\n    }\n}\n/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -&gt; (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let yellow = byte1 &gt;&gt; 2\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = ((byte1 &amp; 0x03) &lt;&lt; 4) | (byte2 &gt;&gt; 4)\n    let blue = ((byte2 &amp; 0x0F) &lt;&lt; 2) | (byte3 &gt;&gt; 6)\n    // 0x3F == 0b0011_1111\n    let purple = byte3 &amp; 0x3F\n    return (yellow, green, blue, purple)\n}\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII(_ value: UInt8) -&gt; UInt8 {\n    if value &lt;= 25 { return value + 65 }\n    if value &lt;= 51 { return value + 71 }\n    if value &lt;= 61 { return value - 4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}</code></pre>\n<p>Here we will:</p>\n<ul><li>1. Process 3 bytes at a time.</li><li>2. Have to use the <code>unsafe</code> keyword as we&#39;re using an<strong>Unsafe</strong> MutableBufferPointer.<ul><li>We&#39;ve enabled <code>strictMemorySafety</code> in our<code>Package.swift</code> , which encourages us to mark our unsafe memory accesses as such.</li></ul></li><li>We&#39;ve enabled </li></ul>\n<p>Let&#39;s run a benchmark over this implementation.</p>\n<p>You&#39;ll need to have followed <a href=\"https://blog.mahdibm.com#support-material\" rel=\"nofollow ugc noopener\">Support Material</a> if you&#39;re running this command yourself.</p>\n<pre><code>$ swift package benchmark --target AutoVectorizationBenchs --filter &#39;1_Naive_Loop.*&#39;\n1_Naive_Loop_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │     13151 │     13550 │     13771 │     14074 │     14377 │     15196 │     15607 │      1000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │     16471 │     16523 │     16564 │     16646 │     16777 │     17105 │     18522 │      1000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n1_Naive_Loop_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │       361 │       343 │       338 │       327 │       316 │       293 │       227 │      1000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛</code></pre>\n<p>At p50, this implementation performs ~340 rounds per second, each round encoding 1 MB of data (999_999 bytes, to be exact).</p>\n<p>That&#39;s roughly 340 MB/s, or less than <strong>0.34 GB/s</strong>.</p>\n<p>At first glance, it might appear that there is little left to optimize in that code.</p>\n<p>Swift does checked math by default, even in optimized builds, so as not to compromise on safety.</p>\n<p>That&#39;s typically not true about code written in Rust or C/C++.</p>\n<p>Maybe if we use unchecked math, something will drastically change?</p>\n<p>Or we&#39;ve heard divisions are slow. Maybe that division by 3 is the culprit?</p>\n<p>Not really.</p>\n<p>Compilers are smarter than that. Many math operations are already optimized, as the compiler can tell there is no way the numbers can, for example, overflow in any case.</p>\n<p>The division by 3 is also outside the loop. It can&#39;t be hurting our performance too much. Anyway, compilers won&#39;t leave a division by a constant value as-is. They&#39;ll optimize divisions to multiplication + bit-shifts when the divisor is a compile-time constant. Try <code>func divisionBy3(number: Int) -&gt; Int { number / 3 }</code> on <a href=\"https://godbolt.org/\" rel=\"nofollow ugc noopener\">Compiler Explorer</a> and see for yourself.</p>\n<p>The more performance-minded of you might come up with a great idea:</p>\n<p>We have a very good case for using <strong>Lookup Tables</strong>.</p>\n<p>## </p>\n<p>Recall that for mapping Base64 values to ASCII characters, we follow the table below:</p>\n<div class=\"table-wrap\"><table><thead><tr><th>Base64 Value</th><th>0 ... 25</th><th>26 ... 51</th><th>52 ... 61</th><th>62</th><th>63</th></tr></thead><tbody><tr><td>Corresponding Letter(s)</td><td>A ... Z</td><td>a ... z</td><td>0 ... 9</td><td>+</td><td>/</td></tr><tr><td>Corresponding ASCII Codes (Decimal)</td><td>65 ... 90</td><td>97 ... 122</td><td>48 ... 57</td><td>43</td><td>47</td></tr><tr><td>Corresponding ASCII Codes (Hex)</td><td>0x41 ... 0x5A</td><td>0x61 ... 0x7A</td><td>0x30 ... 0x39</td><td>0x2B</td><td>0x2F</td></tr></tbody></table></div>\n<p>This is a very good case for using lookup tables.</p>\n<p>We can index the table by the Base64 value and get the ASCII code-point out of it:</p>\n<pre><code>/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span&lt;UInt8&gt;,\n    into output: UnsafeMutableBufferPointer&lt;UInt8&gt;\n) {\n    precondition(bytes.count % 3 == 0, &quot;Bytes count needs to be a multiple of 3&quot;)\n    precondition(output.count &gt;= bytes.count / 3 * 4, &quot;Insufficient output capacity&quot;)\n    let triples = bytes.count / 3\n    for triple in 0..&lt;triples {\n        let index = triple * 3\n        let outputIndex = triple * 4\n        let byte1 = bytes[index]\n        let byte2 = bytes[index + 1]\n        let byte3 = bytes[index + 2]\n        let base64Values = bytesToBase64(byte1, byte2, byte3)\n        let encodedYellow = base64ValueToASCII_lookupTable(base64Values.yellow)\n        let encodedGreen = base64ValueToASCII_lookupTable(base64Values.green)\n        let encodedBlue = base64ValueToASCII_lookupTable(base64Values.blue)\n        let encodedPurple = base64ValueToASCII_lookupTable(base64Values.purple)\n        unsafe output[outputIndex] = encodedYellow\n        unsafe output[outputIndex + 1] = encodedGreen\n        unsafe output[outputIndex + 2] = encodedBlue\n        unsafe output[outputIndex + 3] = encodedPurple\n    }\n}</code></pre>\n<p>This is a good showcase of LLVM&#39;s abilities to get rid of bounds checks where unnecessary.</p>\n<p>As you can see in this simplified version of <code>InlineArray</code>&#39;s (Rust&#39;s array equivalent) subscript implementation, it does contain some bounds-check preconditions when subscripting it like <code>base64Lut[Int(value)]</code>:</p>\n<pre><code>extension InlineArray {\n    /// Accesses the element at the specified position.\n    ///\n    /// - Parameter i: The position of the element to access. `i` must be a valid\n    ///   index of the array that is not equal to the `endIndex` property.\n    ///\n    /// - Complexity: O(1)\n    public subscript(_ i: Index) -&gt; Element {\n        borrow {\n            precondition((0..&lt;count).contains(i), &quot;Index out of bounds&quot;)\n            let pointer = unsafe _address.project(i)\n            return unsafe pointer.pointee\n        }\n        mutate {\n            precondition((0..&lt;count).contains(i), &quot;Index out of bounds&quot;)\n            let pointer = unsafe _mutableAddress.project(i)\n            return unsafe &amp;pointer.pointee\n        }\n    }\n}</code></pre>\n<p>But if you take a look at an optimized representation of the code when inlined into the <code>encodeBytesToBase64</code> function, such as in the final Assembly, you&#39;ll notice there are no bounds checks inserted to ensure our <code>InlineArray</code> accesses are in-bounds:</p>\n<pre><code>output.encodeBytesToBase64(bytes: Swift.Span&lt;Swift.UInt8&gt;, into: Swift.UnsafeMutableBufferPointer&lt;Swift.UInt8&gt;) -&gt; (): # @&quot;output.encodeBytesToBase64(bytes: Swift.Span&lt;Swift.UInt8&gt;, into: Swift.UnsafeMutableBufferPointer&lt;Swift.UInt8&gt;) -&gt; ()&quot;\n        lea     rcx, [rip + output.base64Lut : Swift.InlineArray&lt;64, Swift.UInt8&gt;]\n        movzx   r14d, byte ptr [r14 + rcx]\n        movzx   r10d, byte ptr [r10 + rcx]\n        movzx   ebx, byte ptr [rbx + rcx]\n        movzx   r11d, byte ptr [r11 + rcx]</code></pre>\n<p>That&#39;s <code>base64Lut</code> right there, somehow being accessed. We don&#39;t care what the complete code means, but we do notice there are no bounds checks there. We can see no comparison to <code>63</code>. The compiler must&#39;ve skipped the whole precondition check.</p>\n<p>In comparison, the not-inlined version of the function does show the bounds check, as it can&#39;t be sure upfront that it won&#39;t receive a value that is in bounds or not. It doesn&#39;t matter to our implementation, but here&#39;s the code for the curious ones:</p>\n<pre><code>output.base64ValueToASCII_lookupTable(Swift.UInt8) -&gt; Swift.UInt8: # @&quot;output.base64ValueToASCII_lookupTable(Swift.UInt8) -&gt; Swift.UInt8&quot;\n        cmp     dil, 63\n        ja      .LBB3_2\n        movzx   eax, dil\n        lea     rcx, [rip + output.base64Lut : Swift.InlineArray&lt;64, Swift.UInt8&gt;]\n        movzx   eax, byte ptr [rax + rcx]\n        ret\n.LBB3_2:\n        ud2</code></pre>\n<p>The optimization happens because the compiler can see that <code>InlineArray</code> is a constant of 64 elements and prove that it&#39;s logically impossible to request an index outside <code>0…63</code> in the <code>encodeBytesToBase64</code> function.</p>\n<p>This optimization is not limited to <code>InlineArray</code> and such optimizations are frequently done for more common and more complex types such as <code>Array</code> as well (which is a copy-on-write <code>Arc&lt;Vec&lt;T&gt;&gt;</code> in Rust terms).</p>\n<p>Let&#39;s benchmark:</p>\n<pre><code>$ swift package benchmark --target AutoVectorizationBenchs --filter &#39;2_Lookup_Table.*&#39;\n2_Lookup_Table_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │       956 │       975 │       977 │       979 │      1011 │      1412 │      1782 │     20000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │      8667 │      8675 │      8675 │      8675 │      8692 │      8757 │      9574 │     20000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n2_Lookup_Table_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │      4751 │      4703 │      4651 │      4503 │      3733 │      2197 │       724 │     20000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛</code></pre>\n<p>Nice! The implementation is now doing <strong>4.6 GB/s</strong>. That&#39;s 14 times faster than the initial naive loop implementation.</p>\n<p>What if I told you we can have another 3-4x performance improvement if we pave the way for the compiler to <strong>Auto-Vectorize</strong> our loop?</p>\n<p>## </p>\n<p>To put it in small words, Auto-Vectorization is Vectorization, but well … automatically done! Makes sense, right?</p>\n<p>Who does it automatically? The compiler. More specifically, LLVM.</p>\n<p>LLVM can automatically vectorize a certain group of loops and commonly make them much faster.</p>\n<p>Tip</p>\n<p>Auto-Vectorization is subject to the same note that we started the post with. It&#39;s not limited to Swift.</p>\n<p>Clang, GCC, Rust, Java and some more languages come with Auto-Vectorization capabilities.</p>\n<p>Swift and Rust are pretty friendly to Auto-Vectorization. Both leverage LLVM for it, so they behave similarly.</p>\n<p>In our case, we&#39;re going to make our loop 3+ times faster.</p>\n<p>We can even make it 6+ times faster, reaching <strong>90x</strong> performance over the original naive loop implementation. We&#39;ll also take a peek at that implementation.</p>\n<p>### </p>\n<p>Vectorization can make your loops much faster. But how?</p>\n<p>The CPU core is the same CPU core. Why does it just not run faster without needing this &quot;Vectorization&quot; thing, whatever it is?!?!!</p>\n<p>The Vectorization we&#39;ll be making use of is the SIMD type of Vectorization.</p>\n<p>SIMD itself stands for <strong>S*<em>ingle *</em>I</strong>nstruction <strong>M*<em>ultiple *</em>D</strong>ata. The power of SIMD comes from the fact that you can tell it to run a specific operation on a wide group of data in one go.</p>\n<p>As a more tangible example, you can tell your CPU: &quot;Hey, I have these 16 bytes. I want them all to be multiplied by 3, please!&quot;</p>\n<p>A SIMD instruction is only a <em>single instruction</em> that is operating on <em>multiple data</em>. These instructions sometimes don&#39;t even have latency or performance downsides compared to scalar instructions where there is no SIMD usage.</p>\n<p>### </p>\n<p>SIMD can work on 16 bytes at around the same speed that a scalar instruction would finish 1 byte&#39;s work.</p>\n<p>Does that mean SIMD code will be 16 times faster than scalar code?</p>\n<p>Not really, but it depends on a few factors.</p>\n<p>CPUs nowadays leverage many techniques to be so fast. There are some notes you need to take into account:</p>\n<ul><li>1. Today&#39;s Superscalar CPUs execute multiple instructions in a single cycle via a technique called &quot;Instruction-Level Parallelism&quot;, without even using SIMD.</li><li>2. SIMD code sometimes needs to go through extra hoops and operations to implement the same effect as scalar code.</li><li>3. On the positive side, x86-64 CPUs usually accept 256 bits instead of 128, or up to 512 bits of data when they support the AVX-512 instruction set extension.<ul><li>That&#39;s 64 bytes instead of our 16 bytes, which is how wide the vector registers of Arm64 and Apple Silicon&#39;s M-series processors are.</li></ul></li></ul>\n<p>Tip</p>\n<p>The specific number of instructions a CPU core can execute in the same cycle depends on your CPU&#39;s generation, the instruction&#39;s latency and throughput, how many execution ports are available, and if the final code doesn&#39;t contain other structural hazards.</p>\n<p>To give you an idea, around 5 addition instructions in the same cycle is a good assumption for a recent CPU until you can look up the specifics on a place such as <a href=\"https://uops.info/\" rel=\"nofollow ugc noopener\">uops</a>.</p>\n<p>We&#39;ll benchmark our code on Arm64 on an M6 processor, so theoretically we&#39;re not even using the &quot;best in class&quot; CPUs in supporting SIMD instructions. Even then, we&#39;ll be able to greatly increase the performance of our algorithm.</p>\n<p>### </p>\n<p>You might be wondering now, how can you even leverage SIMD?</p>\n<p>There are multiple layers of abstractions you can use:</p>\n<ul><li><strong>Auto-Vectorization</strong> : Your code will look pretty similar to normal code. The compiler will do the Vectorization.</li><li><strong>SIMD Support</strong> : Most languages come with some sort of SIMD support built in. Swift has<code>SIMD</code> , C++26 has<code>std::simd</code> and Rust has<code>std::simd</code> in the nightlies.<ul><li>There are also libraries which sometimes provide better SIMD support. For example, <a href=\"https://github.com/google/highway\" rel=\"nofollow ugc noopener\">Google&#39;s Highway</a> for C++.</li></ul></li><li>There are also libraries which sometimes provide better SIMD support. For example, </li><li><strong>Compiler Intrinsics</strong> : These are platform-dependent low-level functions that generally look like their related instructions and are provided by the compilers themselves. You&#39;ll closely call NEON, SSE and AVX instructions this way.</li><li><strong>Assembly</strong> : Last but not least, you can simply write your vectorized code in Assembly itself.</li></ul>\n<p>Historically, Auto-Vectorization has been seen as &quot;not worth it&quot;. However, as compilers get better at it and as more modern languages emerge, lots of the old concerns about Auto-Vectorization become history.</p>\n<p>For instance, to use Auto-Vectorization in C, you&#39;d have to worry about memory aliasing, unknown array sizes and alignment issues. In a modern language like Swift or Rust, these concerns are typically moot.</p>\n<p>For lots of use-cases, Auto-Vectorization is sufficient, and its less-abstracted alternatives provide little advantage.</p>\n<p>However, for some other use-cases, you can squeeze a decent amount of extra performance by dropping down to some lower layer. That is, if you deem the extra performance to be worth the potential trouble.</p>\n<p>## </p>\n<p>There are few resources on the web about Auto-Vectorization. Even the latest and greatest of max-effort LLMs struggle to get it right when pushed to their limits, since their training data is very limited in this space and they fail to adequately and properly research it themselves.</p>\n<p>That&#39;s why I&#39;ve decided to demystify Auto-Vectorization.</p>\n<p>In the rest of this post, you&#39;ll learn a few tricks about how to Auto-Vectorize our Base64 implementation. I plan to share another post in the future that covers Auto-Vectorization in more depth and reveals more tricks on how to exploit it.</p>\n<p>Auto-Vectorization pays dividends when applied to loops, although it has use-cases <a href=\"https://llvm.org/docs/Vectorizers.html#the-slp-vectorizer\" rel=\"nofollow ugc noopener\">outside loops</a> as well.</p>\n<p>There are commands outside the interest of this post with which you can learn why LLVM has decided not to Auto-Vectorize a given code. We&#39;ll discuss them in future posts.</p>\n<p>That being said, an experienced developer can tell with their bare eyes that our Base64 loop isn&#39;t getting Auto-Vectorized for 2 reasons: <strong>lookup tables</strong> usage and having <strong>branches</strong> in the loop.</p>\n<p>### </p>\n<p>Using lookup tables in vectorized code is more restrictive than in scalar code.</p>\n<ul><li>On Arm64, your lookup tables must be small enough to fit in 4 vectors at most.<ul><li>So you can only afford up to 64 bytes (4 vectors, each 128 bits, which is 16 bytes) for a lookup table on Arm64.</li></ul></li><li>On x86-64, there is also some support, and you can work your way to handle 64 bytes of lookup table depending on which AVX instruction set extensions your CPU supports.</li></ul>\n<p>One of the disadvantages of using Auto-Vectorization is that the compilers, for now, simply give up on Auto-Vectorization when they see a lookup table.</p>\n<p>That&#39;s why we&#39;ll have to say farewell to our lookup table, and welcome back our iffy <code>base64ValueToASCII</code> function.</p>\n<p>### </p>\n<p>Let&#39;s take another look at what our Base64 value to ASCII code conversion function looks like:</p>\n<pre><code>/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII(_ value: UInt8) -&gt; UInt8 {\n    if value &lt;= 25 { return value + 65 }\n    if value &lt;= 51 { return value + 71 }\n    if value &lt;= 61 { return value - 4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}</code></pre>\n<p>There are many ways to take a peek at the Assembly for that function.</p>\n<p>One of the best and simplest ways is to use Godbolt&#39;s <a href=\"https://godbolt.org/\" rel=\"nofollow ugc noopener\">Compiler Explorer</a>.</p>\n<p>On x86-64, it looks like this with optimizations turned on:</p>\n<pre><code>output.base64ValueToASCII(Swift.UInt8) -&gt; Swift.UInt8: # @&quot;output.base64ValueToASCII(Swift.UInt8) -&gt; Swift.UInt8&quot;\n        mov     eax, edi\n        cmp     al, 25\n        ja      .LBB1_2\n        add     al, 65\n        ret\n.LBB1_2:\n        cmp     al, 51\n        ja      .LBB1_4\n        add     al, 71\n        ret\n.LBB1_4:\n        cmp     al, 61\n        ja      .LBB1_6\n        add     al, -4\n        ret\n.LBB1_6:\n        cmp     al, 62\n        setne   al\n        shl     al, 2\n        or      al, 43\n        ret</code></pre>\n<p>For our purpose, what you need to notice are those 3 <code>ja</code> instructions. There are a limited amount of instructions for branching to some other place in the code, and <code>ja</code> is one of the prevalent ones. The <code>j</code> should be a giveaway of what it does: it <strong>jumps</strong> to some other location in the code, which qualifies as branching.</p>\n<p>Generally speaking, you can think of a branch as an <code>if</code>. If the condition is matched, then <strong>jump</strong> to the location where the remainder of the code lives, or otherwise fall through.</p>\n<p>In Swift terms, the Assembly code is equivalent to the following:</p>\n<pre><code>if value &gt; 25 {\n    if value &gt; 51 {\n        if value &gt; 61 {\n            // A clever way to return 43 if value == 62, otherwise 47.\n            // 43 is `0b101011`, and 47 is `0b101111`.\n            // The only difference is the third least significant bit.\n            // So this code turns on the third least significant bit if `value != 62`.\n            let isNot62: UInt8 = (value == 62) ? 0 : 1\n            // `0b0` when `value == 62`, otherwise `0b100`.\n            let shifted: UInt8 = isNot62 &lt;&lt; 2\n            // `0b101011` (43 == &#39;+&#39;) when `value == 62`, otherwise `0b101111` (47 == &#39;/&#39;).\n            return shifted | 43\n        } else {\n            return value - 4\n        }\n    } else {\n        return value + 71\n    }\n} else {\n    return value + 65\n}</code></pre>\n<p>The only interesting note is that you can see the compiler optimizing those inner bits of the code for choosing between 43 and 47.</p>\n<p>In this case, LLVM&#39;s cost model has decided that this function is better off being branchy than being branchless.</p>\n<p>It could have very well decided that a branchless function will likely be worth it.</p>\n<p>As a matter of fact, this function does compile to branchless code on Arm64 already.</p>\n<p>But how can we push LLVM to make this function branchless everywhere?</p>\n<p>What hints can we give it so its cost model deems branchless code worthy, so Auto-Vectorization can kick in?</p>\n<p>### </p>\n<p>x86-64 and Arm64 come with a set of <strong>conditional operation instructions</strong>. These are more limited in tasks they can handle, but as long as you use them, or rather, you get your compiler to use them, your code will be branchless.</p>\n<p>We just need to get LLVM on board with our decision to not emit branchy code for our <code>if</code> conditions.</p>\n<p><strong>If-Conversion</strong> is the process of eliminating branches by converting them into conditional instructions.</p>\n<p>How can we consistently convince the compiler to apply If-Conversion to our code?</p>\n<p>There is a simple hint we can give to LLVM to encourage it to output branchless code. However, we need to strengthen our background to later understand why the trick even works.</p>\n<p>Has it yet occurred to you why there is such a thing as branchy code and branchless code? Why both? Can&#39;t the compiler or the CPUs just use the one that&#39;s superior?</p>\n<p>The answer is that neither of them is superior to the other in a general setting.</p>\n<p>They are situational. Sometimes branchless code is faster and sometimes branchy code.</p>\n<p>And some other times you must use a specific one of them in any case. For example, for Auto-Vectorization we have no other choice than to use branchless code in the vast majority of cases, as that&#39;s what compilers accept and it&#39;s how you can squeeze maximum performance out of SIMD instructions.</p>\n<p>But when is branchless code better and when is branchy code better?</p>\n<p>It all depends on how <em>well-predicted</em> a branch will be.</p>\n<p>If a branch is well-predicted, you&#39;re much better off letting it be.</p>\n<p>If it&#39;s a frequently mispredicted branch, then you should consider performing an If-Conversion and making it branchless.</p>\n<p>What even is a well-predicted or mispredicted branch?</p>\n<p>For performance reasons, CPUs always make an educated guess about whether a branch is going to resolve to true or not, and preemptively execute that code path.</p>\n<p>This typically results in big performance wins, but if the branch is unpredictable and the CPU&#39;s smart branch predictors can&#39;t keep up with it, it can backfire. It depends on multiple factors, but as a rule of thumb, if a branch is mispredicted more than ~25% of the time, a branchless version of that code might be faster than the branchy version, on average.</p>\n<p>The win in using branchy code is that if the branch is well-predicted, your CPU will mostly only execute the correct code path, even before it can confirm the code path is indeed the correct one.</p>\n<p>But if it mispredicts the branch too often, it&#39;ll often have to stall and flush its pipeline of executed instructions and start executing the correct path all over again.</p>\n<p>Branchless code is the complete opposite. The idea is that &quot;I know the CPU will frequently mispredict these branches, so let&#39;s do the full work anyway&quot;.</p>\n<p>With a frequently mispredicted branch, the CPU will execute the wrong code path, later realize &quot;Oh shoot, this is not the right code path!&quot;, flush and stall its instruction pipeline, and only then execute the correct code path.</p>\n<p>With branchless code, we simply admit defeat upfront and accept calculating both code paths together so we can calculate the correct value without branching around.</p>\n<p>Let&#39;s reiterate.</p>\n<p>The advantage of branchy code is that when the branch is well-predicted, only the right code path is executed, commonly ahead of time.</p>\n<p>The win is in executing less instructions, faster.</p>\n<p>We need to give some hints to the compiler to say that we&#39;re ok with it executing all code paths of our function, and we&#39;re not interested in savings that possible branchy code can come with, if the branches are well-predicted.</p>\n<p>At that point, LLVM&#39;s cost model will likely deem branchless code worthy. After all, we&#39;re already calculating all the work. There wouldn&#39;t be a sufficient win in being branchy anymore.</p>\n<p>### </p>\n<p>The trick is to calculate all the values upfront so LLVM is much more inclined to produce branchless code:</p>\n<pre><code>/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Codes  | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula      | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII_branchless_v1(_ value: UInt8) -&gt; UInt8 {\n    let compare25 = value &lt;= 25\n    let compare51 = value &lt;= 51\n    let compare61 = value &lt;= 61\n    let compare62 = value == 62\n    let plus65 = value &amp;+ 65\n    let plus71 = value &amp;+ 71\n    let minus4 = value &amp;- 4\n    if compare25 { return plus65 }\n    if compare51 { return plus71 }\n    if compare61 { return minus4 }\n    if compare62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}</code></pre>\n<p>We also have to use unchecked math. The function is logically the same as the original branchy code, which would never result in an overflow. We know that overflows are not possible here for the final return value. We only use unchecked math to convince the compiler to not crash if one of the calculations overflows. We won&#39;t use any such overflowed results anyway.</p>\n<p>Of note, Swift&#39;s mathematical operations are always checked, even in release builds, unlike a language like Rust, which by default gets rid of checks in math operations in optimized builds.</p>\n<p>Checked math&#39;s primary use-case is to ensure there are no overflows. Without checked math, numbers will simply wrap around when they no longer fit:</p>\n<pre><code>// WITH checked math\nlet number: UInt8 = 250 + 21 // CRASH\n// WITH UNchecked math\nlet number: UInt8 = 250 &amp;+ 21 // = 15 (logically (250 + 21) % 256)</code></pre>\n<p>Alright. Is it finally branchless? Let&#39;s consult Compiler Explorer:</p>\n<pre><code>output.base64ValueToASCII_branchless_v1(Swift.UInt8) -&gt; Swift.UInt8: # @&quot;output.base64ValueToASCII_branchless_v1(Swift.UInt8) -&gt; Swift.UInt8&quot;\n        cmp     dil, 62\n        setne   al\n        lea     ecx, [rdi - 4]\n        shl     al, 2\n        or      al, 43\n        cmp     dil, 62\n        movzx   ecx, cl\n        movzx   edx, al\n        cmovb   edx, ecx\n        cmp     dil, 26\n        mov     eax, 65\n        mov     ecx, 71\n        cmovb   ecx, eax\n        add     cl, dil\n        cmp     dil, 52\n        movzx   eax, cl\n        cmovae  eax, edx\n        ret</code></pre>\n<p>Nice! The <code>j</code>ump instructions have ceased to exist!</p>\n<p>We can also see a few conditional-move instructions to implement our function as branchless.</p>\n<p>This trick works in most cases, but if a branch is too heavy, LLVM can still elect to not write the whole code as branchless. At that point, we&#39;ll need to apply some more common tricks, such as utilizing <em>speculative writes</em>.</p>\n<p>Luckily, we don&#39;t need that trick right now.</p>\n<p>This code will perform pretty well. However, while we have Compiler Explorer opened up, we can play with the composition of values a little bit and see if any other changes result in better code.</p>\n<p>After playing with it for a few minutes, it appears LLVM generates better code when we don&#39;t hoist the <code>value == 62</code> comparison:</p>\n<pre><code>/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII_branchless(_ value: UInt8) -&gt; UInt8 {\n    let compare25 = value &lt;= 25\n    let compare51 = value &lt;= 51\n    let compare61 = value &lt;= 61\n    let plus65 = value &amp;+ 65\n    let plus71 = value &amp;+ 71\n    let minus4 = value &amp;- 4\n    if compare25 { return plus65 }\n    if compare51 { return plus71 }\n    if compare61 { return minus4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}</code></pre>\n<p>How does the Assembly look?</p>\n<pre><code>output.base64ValueToASCII_branchless(Swift.UInt8) -&gt; Swift.UInt8: # @&quot;output.base64ValueToASCII_branchless(Swift.UInt8) -&gt; Swift.UInt8&quot;\n        cmp     dil, 26\n        mov     eax, 65\n        mov     ecx, 71\n        cmovb   ecx, eax\n        cmp     dil, 52\n        mov     eax, 252\n        cmovb   eax, ecx\n        add     al, dil\n        cmp     dil, 62\n        setne   cl\n        shl     cl, 2\n        or      cl, 43\n        cmp     dil, 62\n        movzx   edx, al\n        movzx   eax, cl\n        cmovb   eax, edx\n        ret</code></pre>\n<p>We shaved a single instruction, what a victory!</p>\n<p>The rest of the instructions are also very similar to the previous implementation&#39;s instructions, so it&#39;s unlikely that we have 1 instruction less but the performance would still regress or cease to improve.</p>\n<p>There are many ways to take a peek at how the functions would compare, such as using machine code analyzers. The simplest way is, however, to benchmark the code. I&#39;ve tried that, and indeed this new function performs better by ~12%.</p>\n<p>Very good. The code we wrote is now branchless. But is the whole loop actually branchless now? No.</p>\n<p>### </p>\n<p>Some other common branchy operations in Swift are the collection subscripts.</p>\n<p>In order to ensure they don&#39;t access out-of-bounds memory, they come with a precondition that will crash the process before you can access memory that is not yours. This is similar to our previous look at <code>InlineArray</code>&#39;s subscript:</p>\n<pre><code>extension Span {\n    /// Accesses the element at the specified index in the `Span`.\n    ///\n    /// - Parameter position: The offset of the element to access. `position`\n    ///     must be greater or equal to zero, and less than `count`.\n    ///\n    /// - Complexity: O(1)\n    public subscript(_ position: Index) -&gt; Element {\n        borrow {\n            precondition((0..&lt;count).contains(position), &quot;Index out of bounds&quot;)\n            return unsafe self[unchecked: position]\n        }\n    }\n}</code></pre>\n<p>In many cases these preconditions are optimized out by LLVM. Even if they&#39;re not optimized out, they normally cost little to no performance as they are quickly identified as unused branches by CPUs.</p>\n<p>However, the compiler is not smart enough to optimize out the preconditions in our case, even though logically there is no way we&#39;re accessing out-of-bounds memory of the <code>Span&lt;UInt8&gt;</code>.</p>\n<p>We&#39;ll use the unchecked <code>Span</code> subscripts to dodge the preconditions being inserted into our code when subscripting <code>bytes</code>.</p>\n<p>In a widely used implementation, depending on the stakes and our confidence in the implementation, we would also accompany this code with rigorous unit tests, occasional fuzz-testing, and more recently with LLM-assisted security analysis to ensure there is no hole in our logic. However, we&#39;ll skip those in this post.</p>\n<p><code>UnsafeBufferPointer</code>s, on the other hand, come with a mere assertion. That is, their subscripts will guard against out-of-bounds access, but not in optimized and release builds. Therefore, they have no <code>unchecked</code> accessors anyway. This means we don&#39;t need to modify the <code>output</code> buffer writes to avoid any possible precondition checks.</p>\n<p>The index calculations don&#39;t need any unchecked math operations. They&#39;re light work for the compiler to optimize.</p>\n<p>At last, let&#39;s put our branchless code together and see how it performs:</p>\n<pre><code>/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span&lt;UInt8&gt;,\n    into output: UnsafeMutableBufferPointer&lt;UInt8&gt;\n) {\n    precondition(bytes.count % 3 == 0, &quot;Bytes count needs to be a multiple of 3&quot;)\n    precondition(output.count &gt;= bytes.count / 3 * 4, &quot;Insufficient output capacity&quot;)\n    let triples = bytes.count / 3\n    for triple in 0..&lt;triples {\n        let index = triple * 3\n        let outputIndex = triple * 4\n        let byte1 = unsafe bytes[unchecked: index]\n        let byte2 = unsafe bytes[unchecked: index + 1]\n        let byte3 = unsafe bytes[unchecked: index + 2]\n        let base64Values = bytesToBase64(byte1, byte2, byte3)\n        let encodedYellow = base64ValueToASCII_branchless(base64Values.yellow)\n        let encodedGreen = base64ValueToASCII_branchless(base64Values.green)\n        let encodedBlue = base64ValueToASCII_branchless(base64Values.blue)\n        let encodedPurple = base64ValueToASCII_branchless(base64Values.purple)\n        unsafe output[outputIndex] = encodedYellow\n        unsafe output[outputIndex + 1] = encodedGreen\n        unsafe output[outputIndex + 2] = encodedBlue\n        unsafe output[outputIndex + 3] = encodedPurple\n    }\n}\n/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.\nfunc bytesToBase64(\n    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8\n) -&gt; (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {\n    let yellow = byte1 &gt;&gt; 2\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = ((byte1 &amp; 0x03) &lt;&lt; 4) | (byte2 &gt;&gt; 4)\n    let blue = ((byte2 &amp; 0x0F) &lt;&lt; 2) | (byte3 &gt;&gt; 6)\n    // 0x3F == 0b0011_1111\n    let purple = byte3 &amp; 0x3F\n    return (yellow, green, blue, purple)\n}\n/// Converts a Base64 value to its corresponding ASCII code based on the following table.\n/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |\n/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |\n/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |\n/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |\n/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.\nfunc base64ValueToASCII_branchless(_ value: UInt8) -&gt; UInt8 {\n    let compare25 = value &lt;= 25\n    let compare51 = value &lt;= 51\n    let compare61 = value &lt;= 61\n    let plus65 = value &amp;+ 65\n    let plus71 = value &amp;+ 71\n    let minus4 = value &amp;- 4\n    if compare25 { return plus65 }\n    if compare51 { return plus71 }\n    if compare61 { return minus4 }\n    if value == 62 { return 43 }\n    // If the value is none of the above, it must be 63 then.\n    return 47\n}</code></pre>\n<p>Let&#39;s benchmark:</p>\n<pre><code>$ swift package benchmark --target AutoVectorizationBenchs --filter &#39;3_Auto_Vectorized.*&#39;\n3_Auto_Vectorized_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │       284 │       285 │       285 │       286 │       348 │       422 │       580 │     50000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │      1105 │      1106 │      1106 │      1106 │      1116 │      1209 │      1575 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n3_Auto_Vectorized_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │     16140 │     16087 │     16007 │     15647 │     11959 │      7359 │      1557 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛</code></pre>\n<p>Splendid! <strong>16 GB/s</strong>, up from 4.6 GB/s of the non-vectorized implementation.</p>\n<p>But how can we tell whether it&#39;s actually Auto-Vectorized or not?</p>\n<p>For one, the performance of the loop should lift your eyebrows. It&#39;s probably Auto-Vectorized, or it wouldn&#39;t be this fast.</p>\n<p>But in general, there are multiple ways to tell a code is Auto-Vectorized. You can read the Assembly as an example.</p>\n<p>However, there is a no-brainer way that requires no understanding of other representations of the code:</p>\n<p>You can check the optimized LLVM IR representation of your code and simply search for <code>vector.body:</code>.</p>\n<p>If there is such text in the generated IR, it means your code has indeed been Auto-Vectorized.</p>\n<p>Let&#39;s try it out for ourselves. We&#39;ll use Godbolt. We normally only pass the <code>-O</code> compiler flag to request optimized code. We&#39;ll now add an extra <code>-emit-ir</code> flag to request the LLVM IR representation instead of the generated Assembly:</p>\n<pre><code>vector.body:\n  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ], !dbg !267\n  %18 = shl i64 %index, 2, !dbg !269</code></pre>\n<p>There it is! The confirmation that our loop is truly vectorized.</p>\n<p>This is where we stopped with Swift&#39;s own <a href=\"https://github.com/swiftlang/swift-foundation\" rel=\"nofollow ugc noopener\">swift-foundation</a> Base64 <a href=\"https://github.com/swiftlang/swift-foundation/pull/2236\" rel=\"nofollow ugc noopener\">encoding implementation</a>. But you can reach for even higher performance.</p>\n<p>What if we could use our lookup table in combination with Vectorization? Let&#39;s take a brief look.</p>\n<p>## </p>\n<p>Luckily for us, the lookup table is exactly 64 bytes and no more, which is the maximum size we can afford on Arm64 without tricks.</p>\n<p>That means we can use a lookup table for our Base64 implementation. Just not with Auto-Vectorization. Not yet, at least.</p>\n<p>Manually writing vectorized code will have to be the subject of a future post, but I&#39;ll give you a sneak peek of it.</p>\n<p>Via my early-stage work-in-progress port of <a href=\"https://github.com/google/highway\" rel=\"nofollow ugc noopener\">Google&#39;s Highway</a> to Swift, you can write the following code, which is inspired by <a href=\"https://github.com/lemire\" rel=\"nofollow ugc noopener\">Daniel Lemire</a> and <a href=\"https://github.com/WojciechMula\" rel=\"nofollow ugc noopener\">Wojciech Muła</a>&#39;s <a href=\"https://github.com/simdutf/simdutf\" rel=\"nofollow ugc noopener\">Base64 implementation</a>:</p>\n<pre><code>/// Generate Base64 encoded bytes from the given input bytes.\n/// Writes to `output`.\n/// Requires:\n///   - `bytes.count` must be a multiple of 3.\n///   - `output.count` must be at least `bytes.count / 3 * 4`.\npackage func encodeBytesToBase64(\n    bytes: Span&lt;UInt8&gt;,\n    into output: UnsafeMutableBufferPointer&lt;UInt8&gt;\n) {\n    precondition(bytes.count % 3 == 0, &quot;Bytes count needs to be a multiple of 3&quot;)\n    precondition(output.count &gt;= bytes.count / 3 * 4, &quot;Insufficient output capacity&quot;)\n    let bytesPerIteration = SIMDUInt8.laneCount * 3\n    let outputBytesPerIteration = SIMDUInt8.laneCount * 4\n    let iterations = bytes.count / bytesPerIteration\n    withAlignedBase64Lut { base64Lut in\n        for iteration in 0..&lt;iterations {\n            let index = iteration * bytesPerIteration\n            let outputIndex = iteration * outputBytesPerIteration\n            var byte1 = SIMDUInt8.zero()\n            var byte2 = SIMDUInt8.zero()\n            var byte3 = SIMDUInt8.zero()\n            SIMDUInt8.loadInterleaved3(\n                from: bytes.extracting(droppingFirst: index), &amp;byte1, &amp;byte2, &amp;byte3\n            )\n            let base64Values = bytesToBase64_vectorized(byte1, byte2, byte3)\n            let encodedYellow = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.yellow, base64Lut: base64Lut\n            )\n            let encodedGreen = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.green, base64Lut: base64Lut\n            )\n            let encodedBlue = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.blue, base64Lut: base64Lut\n            )\n            let encodedPurple = base64ValueToASCII_vectorizedLookupTable(\n                base64Values.purple, base64Lut: base64Lut\n            )\n            unsafe SIMDUInt8.storeInterleaved4(\n                encodedYellow, encodedGreen, encodedBlue, encodedPurple,\n                to: output.baseAddress.unsafelyUnwrapped + outputIndex\n            )\n        }\n    }\n    /// The last bytes that weren&#39;t enough for a full `bytesPerIteration` iteration.\n    let remainingBytes = bytes.extracting(droppingFirst: iterations * bytesPerIteration)\n    let remainingOutput = unsafe UnsafeMutableBufferPointer(\n        rebasing: output[(iterations * outputBytesPerIteration)...]\n    )\n    unsafe AutoVectorized().encodeBytesToBase64(bytes: remainingBytes, into: remainingOutput)\n}\n/// Receives 3 vectors of bytes, returns 4 vectors of base-64 values, each in range of 0 to 63.\nfunc bytesToBase64_vectorized(\n    _ byte1: SIMDUInt8.Vector,\n    _ byte2: SIMDUInt8.Vector,\n    _ byte3: SIMDUInt8.Vector\n) -&gt; (\n    yellow: SIMDUInt8.Vector,\n    green: SIMDUInt8.Vector,\n    blue: SIMDUInt8.Vector,\n    purple: SIMDUInt8.Vector\n) {\n    let yellow = SIMDUInt8.shiftedRight(byte1, by: 2)\n    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111\n    let green = SIMDUInt8.bitwiseOr(\n        SIMDUInt8.shiftedLeft(\n            SIMDUInt8.bitwiseAnd(byte1, SIMDUInt8.repeating(0x03)), by: 4\n        ),\n        SIMDUInt8.shiftedRight(byte2, by: 4)\n    )\n    let blue = SIMDUInt8.bitwiseOr(\n        SIMDUInt8.shiftedLeft(\n            SIMDUInt8.bitwiseAnd(byte2, SIMDUInt8.repeating(0x0F)), by: 2\n        ),\n        SIMDUInt8.shiftedRight(byte3, by: 6)\n    )\n    // 0x3F == 0b0011_1111\n    let purple = SIMDUInt8.bitwiseAnd(byte3, SIMDUInt8.repeating(0x3F))\n    return (yellow, green, blue, purple)\n}\n/// The Base64 Lookup Table (LUT) as an inline array.\nstatic let base64Lut: InlineArray&lt;64, UInt8&gt; = [\n    UInt8(ascii: &quot;A&quot;), UInt8(ascii: &quot;B&quot;), UInt8(ascii: &quot;C&quot;), UInt8(ascii: &quot;D&quot;),\n    UInt8(ascii: &quot;E&quot;), UInt8(ascii: &quot;F&quot;), UInt8(ascii: &quot;G&quot;), UInt8(ascii: &quot;H&quot;),\n    UInt8(ascii: &quot;I&quot;), UInt8(ascii: &quot;J&quot;), UInt8(ascii: &quot;K&quot;), UInt8(ascii: &quot;L&quot;),\n    UInt8(ascii: &quot;M&quot;), UInt8(ascii: &quot;N&quot;), UInt8(ascii: &quot;O&quot;), UInt8(ascii: &quot;P&quot;),\n    UInt8(ascii: &quot;Q&quot;), UInt8(ascii: &quot;R&quot;), UInt8(ascii: &quot;S&quot;), UInt8(ascii: &quot;T&quot;),\n    UInt8(ascii: &quot;U&quot;), UInt8(ascii: &quot;V&quot;), UInt8(ascii: &quot;W&quot;), UInt8(ascii: &quot;X&quot;),\n    UInt8(ascii: &quot;Y&quot;), UInt8(ascii: &quot;Z&quot;), UInt8(ascii: &quot;a&quot;), UInt8(ascii: &quot;b&quot;),\n    UInt8(ascii: &quot;c&quot;), UInt8(ascii: &quot;d&quot;), UInt8(ascii: &quot;e&quot;), UInt8(ascii: &quot;f&quot;),\n    UInt8(ascii: &quot;g&quot;), UInt8(ascii: &quot;h&quot;), UInt8(ascii: &quot;i&quot;), UInt8(ascii: &quot;j&quot;),\n    UInt8(ascii: &quot;k&quot;), UInt8(ascii: &quot;l&quot;), UInt8(ascii: &quot;m&quot;), UInt8(ascii: &quot;n&quot;),\n    UInt8(ascii: &quot;o&quot;), UInt8(ascii: &quot;p&quot;), UInt8(ascii: &quot;q&quot;), UInt8(ascii: &quot;r&quot;),\n    UInt8(ascii: &quot;s&quot;), UInt8(ascii: &quot;t&quot;), UInt8(ascii: &quot;u&quot;), UInt8(ascii: &quot;v&quot;),\n    UInt8(ascii: &quot;w&quot;), UInt8(ascii: &quot;x&quot;), UInt8(ascii: &quot;y&quot;), UInt8(ascii: &quot;z&quot;),\n    UInt8(ascii: &quot;0&quot;), UInt8(ascii: &quot;1&quot;), UInt8(ascii: &quot;2&quot;), UInt8(ascii: &quot;3&quot;),\n    UInt8(ascii: &quot;4&quot;), UInt8(ascii: &quot;5&quot;), UInt8(ascii: &quot;6&quot;), UInt8(ascii: &quot;7&quot;),\n    UInt8(ascii: &quot;8&quot;), UInt8(ascii: &quot;9&quot;), UInt8(ascii: &quot;+&quot;), UInt8(ascii: &quot;/&quot;),\n]</code></pre>\n<p>How does this perform?</p>\n<pre><code>$ swift package benchmark --target AutoVectorizationBenchs --filter &#39;4_Vectorized_With_Lookup_Table.*&#39;\n4_Vectorized_With_Lookup_Table_Instructions\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Cycles (K) *              │       153 │       154 │       155 │       159 │       208 │       252 │       397 │     50000 │\n├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤\n│ Instructions (K) *        │       522 │       522 │       522 │       522 │       523 │       569 │       762 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛\n4_Vectorized_With_Lookup_Table_Throughput\n╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕\n│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │\n╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡\n│ Throughput (# / s) (#)    │     29667 │     29487 │     29199 │     28639 │     27439 │     19199 │      2843 │     50000 │\n╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛</code></pre>\n<p>On the cusp of <strong>30 GB/s</strong>, 90 times faster than our original naive loop!</p>\n<p>What does <strong>30 GB/s</strong> even mean?</p>\n<p>It&#39;s 30 billion bytes per second, or 30 bytes per nanosecond, or around 6 bytes per clock cycle, on average.</p>\n<p>Think about it for a second. We&#39;re encoding 6 bytes to 8 Base64-encoded characters in each CPU cycle with this implementation.</p>\n<p>## </p>\n<p>Here&#39;s how the 4 different implementations compare to each other, alongside <a href=\"https://github.com/lemire\" rel=\"nofollow ugc noopener\">Daniel Lemire</a>&#39;s own implementation in C++, which is a full implementation with all the bells and whistles:</p>\n<pre><code>swift package benchmark --target AutoVectorizationBenchs</code></pre>\n<div class=\"table-wrap\"><table><thead><tr><th>Implementation</th><th>p50</th><th>Instructions</th><th>Cycles</th></tr></thead><tbody><tr><td>Naive loop</td><td>0.34 GB/s</td><td>16600 K</td><td>13800 K</td></tr><tr><td>Lookup table</td><td>4.6 GB/s</td><td>8700 K</td><td>980 K</td></tr><tr><td>Auto-Vectorized</td><td>16.0 GB/s</td><td>1100 K</td><td>285 K</td></tr><tr><td><a href=\"https://github.com/simdutf/simdutf\" rel=\"nofollow ugc noopener\">Lemire (C++)</a></td><td>27.8 GB/s</td><td>420 K</td><td>165 K</td></tr><tr><td>Vectorized + LUT</td><td>29.2 GB/s</td><td>520 K</td><td>155 K</td></tr></tbody></table></div>\n<p>## </p>\n<p>As always, I&#39;m open to any kinds of suggestions, be it technical or not.</p>\n<p>If you&#39;d like to discuss this post, I&#39;ve opened up <a href=\"https://forums.swift.org/t/blog-post-practical-auto-vectorization-not-llm-generated-per-usual/\" rel=\"nofollow ugc noopener\">this thread</a> on Swift&#39;s forums. I&#39;ll be waiting for you there.</p>\n<p>I&#39;ll be happy to know what parts of this post you&#39;d like to know more about in the future.</p>\n<p>Thank you for reading right through the end.</p>","headings":[{"level":1,"text":"Practical Auto-Vectorization","id":"practical-auto-vectorization"}]}}