---
title: "Practical Auto-Vectorization"
slug: practical-auto-vectorization
url: https://listedarticles.com/articles/practical-auto-vectorization
canonical_url: https://blog.mahdibm.com/posts/practical-auto-vectorization/
content_type: tutorial
language: en
published_at: 2026-11-08T00:00:00.000Z
updated_at: 2026-11-08T17:11:34.811Z
author: "Mahdi Bahrami"
author_url: https://blog.mahdibm.com/
authored_by: human
publisher: "Mahdi Bahrami's blog"
publisher_url: https://blog.mahdibm.com/
topics: ["Performance", "Programming", "Software Engineering"]
license: all-rights-reserved
word_count: 7532
reading_minutes: 33
citation: "Mahdi Bahrami, Mahdi Bahrami's blog. \"Practical Auto-Vectorization.\" 8 Nov 2026. https://blog.mahdibm.com/posts/practical-auto-vectorization/ (all-rights-reserved)"
# The full text follows. The web page shows an extract and sends readers
# to the source above; quote the citation and link the canonical URL.
---

# Practical Auto-Vectorization

> 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.

# Practical Auto-Vectorization

In 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**.

We'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.

I'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.

## 

## 

You can checkout this post's related commit to test out the implementations and measurements.

You'll need to have Swift 6.4 and above installed on a Linux or macOS system to run the benchmarks.

```
git clone https://github.com/MahdiBM/blog-material
cd blog-material
git switch --detach c63c91e7695c1c2c47828508ee636e19c5709859
```
In the post, measurements also mention their related benchmark command.

## 

We'll use Base64 encoding as it's pretty simple and is a good showcase of the different optimizations.

We'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.

## 

Let's take a quick look at the Base64 encoding. It's pretty simple. We need to understand it before attempting to optimize it.

The Base64 format was created as a way to transfer raw data over a medium which merely accepts text.

So 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.

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.

We'll use the following bytes as examples:

| Byte 1 | Byte 2 | Byte 3 | 
|---|---|---|
| 0b11000100 | 0b10101111 | 0b10110111 | 

As you can see, the 3 bytes, represented as 3 unsigned 8-bit integers, amount to a total of 24 bits.

Base64 reads 6 bits at a time and gathers 4 6-bit values out of those 24 bits.

Note

`0b` is not part of the value. It simply denotes **Binary** notation.

Tip

Notice 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.

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):

| Base64 Value | 0 ... 25 | 26 ... 51 | 52 ... 61 | 62 | 63 | 
|---|---|---|---|---|---|
| Corresponding Letter(s) | A ... Z | a ... z | 0 ... 9 | + | / | 
| Corresponding ASCII Codes (Decimal) | 65 ... 90 | 97 ... 122 | 48 ... 57 | 43 | 47 | 
| Corresponding ASCII Codes (Hex) | 0x41 ... 0x5A | 0x61 ... 0x7A | 0x30 ... 0x39 | 0x2B | 0x2F | 

Note

`0x` is not part of the value. It simply denotes **Hexadecimal** notation.

So in this specific case, our 4 Base64 values will be:

|  | Base64 Value 1 | Base64 Value 2 | Base64 Value 3 | Base64 Value 4 | 
|---|---|---|---|---|
| Binary Value | 0b110001 | 0b001010 | 0b111110 | 0b110111 | 
| Decimal Value | 49 | 10 | 62 | 55 | 
| ASCII Mapping (Decimal) | 120 | 75 | 43 | 51 | 
| ASCII Mapping (Hex) | 0x78 | 0x4B | 0x2B | 0x33 | 
| ASCII Mapping (Character) | `x` | `K` | `+` | `3` | 

When you see a Base64-encoded text on the web, you're looking at the "ASCII Mapping" characters of the Base64 values.

### 

We'll implement the bytes-to-Base64-values function like so:

```
/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.
func bytesToBase64(
    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8
) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {
    let byte1_yellow = byte1 & 0b1111_1100 // All but the least significant 2 bits
    let byte1_green = byte1 & 0b0000_0011 // Least significant 2 bits
    let byte2_green = byte2 & 0b1111_0000 // Most significant half of the byte
    let byte2_blue = byte2 & 0b0000_1111 // Least significant half of the byte
    let byte3_blue = byte3 & 0b1100_0000 // Most significant 2 bits
    let byte3_purple = byte3 & 0b0011_1111 // Least significant 6 bits
    let yellow = byte1_yellow >> 2
    let green = byte1_green << 4 | byte2_green >> 4
    let blue = byte2_blue << 2 | byte3_blue >> 6
    let purple = byte3_purple
    return (yellow, green, blue, purple)
}
```
We can optimize the function to the following if we're a little bit smarter about our bit operations:

```
/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.
func bytesToBase64(
    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8
) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {
    let yellow = byte1 >> 2
    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111
    let green = ((byte1 & 0x03) << 4) | (byte2 >> 4)
    let blue = ((byte2 & 0x0F) << 2) | (byte3 >> 6)
    // 0x3F == 0b0011_1111
    let purple = byte3 & 0x3F
    return (yellow, green, blue, purple)
}
```
If 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:

```
output.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)"
        mov     eax, edi
        shr     al, 2
        mov     ecx, esi
        shr     cl, 4
        shl     dil, 4
        or      dil, cl
        and     dil, 63
        mov     ecx, edx
        shr     cl, 6
        shl     sil, 2
        or      sil, cl
        and     sil, 63
        and     dl, 63
        movzx   ecx, dl
        shl     ecx, 24
        movzx   edx, sil
        shl     edx, 16
        or      edx, ecx
        movzx   ecx, dil
        shl     ecx, 8
        or      ecx, edx
        movzx   eax, al
        or      eax, ecx
        ret
```
It'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.

The takeaway is that the compiler was smart enough to do the optimizations for us.

No matter. We'll continue to use our presumably optimized version.

Let's also implement the function that takes each Base64 value and converts them to ASCII codes:

```
/// Converts a Base64 value to its corresponding ASCII code based on the following table.
/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |
/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |
/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |
/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |
/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.
func base64ValueToASCII(_ value: UInt8) -> UInt8 {
    if value <= 25 { return value + 65 }
    if value <= 51 { return value + 71 }
    if value <= 61 { return value - 4 }
    if value == 62 { return 43 }
    // If the value is none of the above, it must be 63 then.
    return 47
}
```
In 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?

### 

Base64 encoding operates on 3 bytes at a time, but sometimes the number of bytes is indivisible by 3.

We'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).

### 

Furthermore, we'll use the default variant of Base64 encoding.

Other variants make little difference to our comparisons, and they're simple enough in concept.

For example, the "URL safe" Base64-encoding variant merely replaces `+` with `-` and `/` with `_`.

## 

Ok then. Let's stitch the code snippets together so we can measure the performance of our Base64-encoding algorithm.

For 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.

In 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.

In 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.

However, 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.

My 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.

Let's get back to our Base64 implementation:

```
/// Generate Base64 encoded bytes from the given input bytes.
/// Writes to `output`.
/// Requires:
///   - `bytes.count` must be a multiple of 3.
///   - `output.count` must be at least `bytes.count / 3 * 4`.
package func encodeBytesToBase64(
    bytes: Span<UInt8>,
    into output: UnsafeMutableBufferPointer<UInt8>
) {
    precondition(bytes.count % 3 == 0, "Bytes count needs to be a multiple of 3")
    precondition(output.count >= bytes.count / 3 * 4, "Insufficient output capacity")
    let triples = bytes.count / 3
    for triple in 0..<triples {
        let index = triple * 3
        let outputIndex = triple * 4
        let byte1 = bytes[index]
        let byte2 = bytes[index + 1]
        let byte3 = bytes[index + 2]
        let base64Values = bytesToBase64(byte1, byte2, byte3)
        let encodedYellow = base64ValueToASCII(base64Values.yellow)
        let encodedGreen = base64ValueToASCII(base64Values.green)
        let encodedBlue = base64ValueToASCII(base64Values.blue)
        let encodedPurple = base64ValueToASCII(base64Values.purple)
        unsafe output[outputIndex] = encodedYellow
        unsafe output[outputIndex + 1] = encodedGreen
        unsafe output[outputIndex + 2] = encodedBlue
        unsafe output[outputIndex + 3] = encodedPurple
    }
}
/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.
func bytesToBase64(
    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8
) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {
    let yellow = byte1 >> 2
    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111
    let green = ((byte1 & 0x03) << 4) | (byte2 >> 4)
    let blue = ((byte2 & 0x0F) << 2) | (byte3 >> 6)
    // 0x3F == 0b0011_1111
    let purple = byte3 & 0x3F
    return (yellow, green, blue, purple)
}
/// Converts a Base64 value to its corresponding ASCII code based on the following table.
/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |
/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |
/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |
/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |
/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.
func base64ValueToASCII(_ value: UInt8) -> UInt8 {
    if value <= 25 { return value + 65 }
    if value <= 51 { return value + 71 }
    if value <= 61 { return value - 4 }
    if value == 62 { return 43 }
    // If the value is none of the above, it must be 63 then.
    return 47
}
```
Here we will:

- 1. Process 3 bytes at a time.
- 2. Have to use the `unsafe` keyword as we're using an**Unsafe** MutableBufferPointer.
  - We've enabled `strictMemorySafety` in our`Package.swift` , which encourages us to mark our unsafe memory accesses as such.
- We've enabled 

Let's run a benchmark over this implementation.

You'll need to have followed [Support Material](https://blog.mahdibm.com#support-material) if you're running this command yourself.

```
$ swift package benchmark --target AutoVectorizationBenchs --filter '1_Naive_Loop.*'
1_Naive_Loop_Instructions
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Cycles (K) *              │     13151 │     13550 │     13771 │     14074 │     14377 │     15196 │     15607 │      1000 │
├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Instructions (K) *        │     16471 │     16523 │     16564 │     16646 │     16777 │     17105 │     18522 │      1000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
1_Naive_Loop_Throughput
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Throughput (# / s) (#)    │       361 │       343 │       338 │       327 │       316 │       293 │       227 │      1000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
```
At p50, this implementation performs ~340 rounds per second, each round encoding 1 MB of data (999_999 bytes, to be exact).

That's roughly 340 MB/s, or less than **0.34 GB/s**.

At first glance, it might appear that there is little left to optimize in that code.

Swift does checked math by default, even in optimized builds, so as not to compromise on safety.

That's typically not true about code written in Rust or C/C++.

Maybe if we use unchecked math, something will drastically change?

Or we've heard divisions are slow. Maybe that division by 3 is the culprit?

Not really.

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.

The 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.

The more performance-minded of you might come up with a great idea:

We have a very good case for using **Lookup Tables**.

## 

Recall that for mapping Base64 values to ASCII characters, we follow the table below:

| Base64 Value | 0 ... 25 | 26 ... 51 | 52 ... 61 | 62 | 63 | 
|---|---|---|---|---|---|
| Corresponding Letter(s) | A ... Z | a ... z | 0 ... 9 | + | / | 
| Corresponding ASCII Codes (Decimal) | 65 ... 90 | 97 ... 122 | 48 ... 57 | 43 | 47 | 
| Corresponding ASCII Codes (Hex) | 0x41 ... 0x5A | 0x61 ... 0x7A | 0x30 ... 0x39 | 0x2B | 0x2F | 

This is a very good case for using lookup tables.

We can index the table by the Base64 value and get the ASCII code-point out of it:

```
/// Generate Base64 encoded bytes from the given input bytes.
/// Writes to `output`.
/// Requires:
///   - `bytes.count` must be a multiple of 3.
///   - `output.count` must be at least `bytes.count / 3 * 4`.
package func encodeBytesToBase64(
    bytes: Span<UInt8>,
    into output: UnsafeMutableBufferPointer<UInt8>
) {
    precondition(bytes.count % 3 == 0, "Bytes count needs to be a multiple of 3")
    precondition(output.count >= bytes.count / 3 * 4, "Insufficient output capacity")
    let triples = bytes.count / 3
    for triple in 0..<triples {
        let index = triple * 3
        let outputIndex = triple * 4
        let byte1 = bytes[index]
        let byte2 = bytes[index + 1]
        let byte3 = bytes[index + 2]
        let base64Values = bytesToBase64(byte1, byte2, byte3)
        let encodedYellow = base64ValueToASCII_lookupTable(base64Values.yellow)
        let encodedGreen = base64ValueToASCII_lookupTable(base64Values.green)
        let encodedBlue = base64ValueToASCII_lookupTable(base64Values.blue)
        let encodedPurple = base64ValueToASCII_lookupTable(base64Values.purple)
        unsafe output[outputIndex] = encodedYellow
        unsafe output[outputIndex + 1] = encodedGreen
        unsafe output[outputIndex + 2] = encodedBlue
        unsafe output[outputIndex + 3] = encodedPurple
    }
}
```
This is a good showcase of LLVM's abilities to get rid of bounds checks where unnecessary.

As 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)]`:

```
extension InlineArray {
    /// Accesses the element at the specified position.
    ///
    /// - Parameter i: The position of the element to access. `i` must be a valid
    ///   index of the array that is not equal to the `endIndex` property.
    ///
    /// - Complexity: O(1)
    public subscript(_ i: Index) -> Element {
        borrow {
            precondition((0..<count).contains(i), "Index out of bounds")
            let pointer = unsafe _address.project(i)
            return unsafe pointer.pointee
        }
        mutate {
            precondition((0..<count).contains(i), "Index out of bounds")
            let pointer = unsafe _mutableAddress.project(i)
            return unsafe &pointer.pointee
        }
    }
}
```
But 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:

```
output.encodeBytesToBase64(bytes: Swift.Span<Swift.UInt8>, into: Swift.UnsafeMutableBufferPointer<Swift.UInt8>) -> (): # @"output.encodeBytesToBase64(bytes: Swift.Span<Swift.UInt8>, into: Swift.UnsafeMutableBufferPointer<Swift.UInt8>) -> ()"
        lea     rcx, [rip + output.base64Lut : Swift.InlineArray<64, Swift.UInt8>]
        movzx   r14d, byte ptr [r14 + rcx]
        movzx   r10d, byte ptr [r10 + rcx]
        movzx   ebx, byte ptr [rbx + rcx]
        movzx   r11d, byte ptr [r11 + rcx]
```
That'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.

In 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:

```
output.base64ValueToASCII_lookupTable(Swift.UInt8) -> Swift.UInt8: # @"output.base64ValueToASCII_lookupTable(Swift.UInt8) -> Swift.UInt8"
        cmp     dil, 63
        ja      .LBB3_2
        movzx   eax, dil
        lea     rcx, [rip + output.base64Lut : Swift.InlineArray<64, Swift.UInt8>]
        movzx   eax, byte ptr [rax + rcx]
        ret
.LBB3_2:
        ud2
```
The 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.

This 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).

Let's benchmark:

```
$ swift package benchmark --target AutoVectorizationBenchs --filter '2_Lookup_Table.*'
2_Lookup_Table_Instructions
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Cycles (K) *              │       956 │       975 │       977 │       979 │      1011 │      1412 │      1782 │     20000 │
├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Instructions (K) *        │      8667 │      8675 │      8675 │      8675 │      8692 │      8757 │      9574 │     20000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
2_Lookup_Table_Throughput
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Throughput (# / s) (#)    │      4751 │      4703 │      4651 │      4503 │      3733 │      2197 │       724 │     20000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
```
Nice! The implementation is now doing **4.6 GB/s**. That's 14 times faster than the initial naive loop implementation.

What 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?

## 

To put it in small words, Auto-Vectorization is Vectorization, but well … automatically done! Makes sense, right?

Who does it automatically? The compiler. More specifically, LLVM.

LLVM can automatically vectorize a certain group of loops and commonly make them much faster.

Tip

Auto-Vectorization is subject to the same note that we started the post with. It's not limited to Swift.

Clang, GCC, Rust, Java and some more languages come with Auto-Vectorization capabilities.

Swift and Rust are pretty friendly to Auto-Vectorization. Both leverage LLVM for it, so they behave similarly.

In our case, we're going to make our loop 3+ times faster.

We 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.

### 

Vectorization can make your loops much faster. But how?

The CPU core is the same CPU core. Why does it just not run faster without needing this "Vectorization" thing, whatever it is?!?!!

The Vectorization we'll be making use of is the SIMD type of Vectorization.

SIMD 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.

As 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!"

A 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.

### 

SIMD can work on 16 bytes at around the same speed that a scalar instruction would finish 1 byte's work.

Does that mean SIMD code will be 16 times faster than scalar code?

Not really, but it depends on a few factors.

CPUs nowadays leverage many techniques to be so fast. There are some notes you need to take into account:

- 1. Today's Superscalar CPUs execute multiple instructions in a single cycle via a technique called "Instruction-Level Parallelism", without even using SIMD.
- 2. SIMD code sometimes needs to go through extra hoops and operations to implement the same effect as scalar code.
- 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.
  - 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.

Tip

The 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.

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 [uops](https://uops.info/).

We'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.

### 

You might be wondering now, how can you even leverage SIMD?

There are multiple layers of abstractions you can use:

- **Auto-Vectorization** : Your code will look pretty similar to normal code. The compiler will do the Vectorization.
- **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.
  - There are also libraries which sometimes provide better SIMD support. For example, [Google's Highway](https://github.com/google/highway) for C++.
- There are also libraries which sometimes provide better SIMD support. For example, 
- **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.
- **Assembly** : Last but not least, you can simply write your vectorized code in Assembly itself.

Historically, 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.

For 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.

For lots of use-cases, Auto-Vectorization is sufficient, and its less-abstracted alternatives provide little advantage.

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.

## 

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.

That's why I've decided to demystify Auto-Vectorization.

In 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.

Auto-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.

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'll discuss them in future posts.

That 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.

### 

Using lookup tables in vectorized code is more restrictive than in scalar code.

- On Arm64, your lookup tables must be small enough to fit in 4 vectors at most.
  - So you can only afford up to 64 bytes (4 vectors, each 128 bits, which is 16 bytes) for a lookup table on Arm64.
- 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.

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.

That's why we'll have to say farewell to our lookup table, and welcome back our iffy `base64ValueToASCII` function.

### 

Let's take another look at what our Base64 value to ASCII code conversion function looks like:

```
/// Converts a Base64 value to its corresponding ASCII code based on the following table.
/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |
/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |
/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |
/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |
/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.
func base64ValueToASCII(_ value: UInt8) -> UInt8 {
    if value <= 25 { return value + 65 }
    if value <= 51 { return value + 71 }
    if value <= 61 { return value - 4 }
    if value == 62 { return 43 }
    // If the value is none of the above, it must be 63 then.
    return 47
}
```
There are many ways to take a peek at the Assembly for that function.

One of the best and simplest ways is to use Godbolt's [Compiler Explorer](https://godbolt.org/).

On x86-64, it looks like this with optimizations turned on:

```
output.base64ValueToASCII(Swift.UInt8) -> Swift.UInt8: # @"output.base64ValueToASCII(Swift.UInt8) -> Swift.UInt8"
        mov     eax, edi
        cmp     al, 25
        ja      .LBB1_2
        add     al, 65
        ret
.LBB1_2:
        cmp     al, 51
        ja      .LBB1_4
        add     al, 71
        ret
.LBB1_4:
        cmp     al, 61
        ja      .LBB1_6
        add     al, -4
        ret
.LBB1_6:
        cmp     al, 62
        setne   al
        shl     al, 2
        or      al, 43
        ret
```
For 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.

Generally 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.

In Swift terms, the Assembly code is equivalent to the following:

```
if value > 25 {
    if value > 51 {
        if value > 61 {
            // A clever way to return 43 if value == 62, otherwise 47.
            // 43 is `0b101011`, and 47 is `0b101111`.
            // The only difference is the third least significant bit.
            // So this code turns on the third least significant bit if `value != 62`.
            let isNot62: UInt8 = (value == 62) ? 0 : 1
            // `0b0` when `value == 62`, otherwise `0b100`.
            let shifted: UInt8 = isNot62 << 2
            // `0b101011` (43 == '+') when `value == 62`, otherwise `0b101111` (47 == '/').
            return shifted | 43
        } else {
            return value - 4
        }
    } else {
        return value + 71
    }
} else {
    return value + 65
}
```
The only interesting note is that you can see the compiler optimizing those inner bits of the code for choosing between 43 and 47.

In this case, LLVM's cost model has decided that this function is better off being branchy than being branchless.

It could have very well decided that a branchless function will likely be worth it.

As a matter of fact, this function does compile to branchless code on Arm64 already.

But how can we push LLVM to make this function branchless everywhere?

What hints can we give it so its cost model deems branchless code worthy, so Auto-Vectorization can kick in?

### 

x86-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.

We just need to get LLVM on board with our decision to not emit branchy code for our `if` conditions.

**If-Conversion** is the process of eliminating branches by converting them into conditional instructions.

How can we consistently convince the compiler to apply If-Conversion to our code?

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.

Has 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?

The answer is that neither of them is superior to the other in a general setting.

They are situational. Sometimes branchless code is faster and sometimes branchy code.

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's what compilers accept and it's how you can squeeze maximum performance out of SIMD instructions.

But when is branchless code better and when is branchy code better?

It all depends on how *well-predicted* a branch will be.

If a branch is well-predicted, you're much better off letting it be.

If it's a frequently mispredicted branch, then you should consider performing an If-Conversion and making it branchless.

What even is a well-predicted or mispredicted branch?

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.

This 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.

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.

But 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.

Branchless 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".

With 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.

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.

Let's reiterate.

The advantage of branchy code is that when the branch is well-predicted, only the right code path is executed, commonly ahead of time.

The win is in executing less instructions, faster.

We 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.

At 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.

### 

The trick is to calculate all the values upfront so LLVM is much more inclined to produce branchless code:

```
/// Converts a Base64 value to its corresponding ASCII code based on the following table.
/// | Base64 Value | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |
/// | ASCII Codes  | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |
/// | Formula      | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |
/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.
func base64ValueToASCII_branchless_v1(_ value: UInt8) -> UInt8 {
    let compare25 = value <= 25
    let compare51 = value <= 51
    let compare61 = value <= 61
    let compare62 = value == 62
    let plus65 = value &+ 65
    let plus71 = value &+ 71
    let minus4 = value &- 4
    if compare25 { return plus65 }
    if compare51 { return plus71 }
    if compare61 { return minus4 }
    if compare62 { return 43 }
    // If the value is none of the above, it must be 63 then.
    return 47
}
```
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't use any such overflowed results anyway.

Of 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.

Checked 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:

```
// WITH checked math
let number: UInt8 = 250 + 21 // CRASH
// WITH UNchecked math
let number: UInt8 = 250 &+ 21 // = 15 (logically (250 + 21) % 256)
```
Alright. Is it finally branchless? Let's consult Compiler Explorer:

```
output.base64ValueToASCII_branchless_v1(Swift.UInt8) -> Swift.UInt8: # @"output.base64ValueToASCII_branchless_v1(Swift.UInt8) -> Swift.UInt8"
        cmp     dil, 62
        setne   al
        lea     ecx, [rdi - 4]
        shl     al, 2
        or      al, 43
        cmp     dil, 62
        movzx   ecx, cl
        movzx   edx, al
        cmovb   edx, ecx
        cmp     dil, 26
        mov     eax, 65
        mov     ecx, 71
        cmovb   ecx, eax
        add     cl, dil
        cmp     dil, 52
        movzx   eax, cl
        cmovae  eax, edx
        ret
```
Nice! The `j`ump instructions have ceased to exist!

We can also see a few conditional-move instructions to implement our function as branchless.

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'll need to apply some more common tricks, such as utilizing *speculative writes*.

Luckily, we don't need that trick right now.

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.

After playing with it for a few minutes, it appears LLVM generates better code when we don't hoist the `value == 62` comparison:

```
/// Converts a Base64 value to its corresponding ASCII code based on the following table.
/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |
/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |
/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |
/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |
/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.
func base64ValueToASCII_branchless(_ value: UInt8) -> UInt8 {
    let compare25 = value <= 25
    let compare51 = value <= 51
    let compare61 = value <= 61
    let plus65 = value &+ 65
    let plus71 = value &+ 71
    let minus4 = value &- 4
    if compare25 { return plus65 }
    if compare51 { return plus71 }
    if compare61 { return minus4 }
    if value == 62 { return 43 }
    // If the value is none of the above, it must be 63 then.
    return 47
}
```
How does the Assembly look?

```
output.base64ValueToASCII_branchless(Swift.UInt8) -> Swift.UInt8: # @"output.base64ValueToASCII_branchless(Swift.UInt8) -> Swift.UInt8"
        cmp     dil, 26
        mov     eax, 65
        mov     ecx, 71
        cmovb   ecx, eax
        cmp     dil, 52
        mov     eax, 252
        cmovb   eax, ecx
        add     al, dil
        cmp     dil, 62
        setne   cl
        shl     cl, 2
        or      cl, 43
        cmp     dil, 62
        movzx   edx, al
        movzx   eax, cl
        cmovb   eax, edx
        ret
```
We shaved a single instruction, what a victory!

The 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.

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've tried that, and indeed this new function performs better by ~12%.

Very good. The code we wrote is now branchless. But is the whole loop actually branchless now? No.

### 

Some other common branchy operations in Swift are the collection subscripts.

In 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:

```
extension Span {
    /// Accesses the element at the specified index in the `Span`.
    ///
    /// - Parameter position: The offset of the element to access. `position`
    ///     must be greater or equal to zero, and less than `count`.
    ///
    /// - Complexity: O(1)
    public subscript(_ position: Index) -> Element {
        borrow {
            precondition((0..<count).contains(position), "Index out of bounds")
            return unsafe self[unchecked: position]
        }
    }
}
```
In 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.

However, 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>`.

We'll use the unchecked `Span` subscripts to dodge the preconditions being inserted into our code when subscripting `bytes`.

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'll skip those in this post.

`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.

The index calculations don't need any unchecked math operations. They're light work for the compiler to optimize.

At last, let's put our branchless code together and see how it performs:

```
/// Generate Base64 encoded bytes from the given input bytes.
/// Writes to `output`.
/// Requires:
///   - `bytes.count` must be a multiple of 3.
///   - `output.count` must be at least `bytes.count / 3 * 4`.
package func encodeBytesToBase64(
    bytes: Span<UInt8>,
    into output: UnsafeMutableBufferPointer<UInt8>
) {
    precondition(bytes.count % 3 == 0, "Bytes count needs to be a multiple of 3")
    precondition(output.count >= bytes.count / 3 * 4, "Insufficient output capacity")
    let triples = bytes.count / 3
    for triple in 0..<triples {
        let index = triple * 3
        let outputIndex = triple * 4
        let byte1 = unsafe bytes[unchecked: index]
        let byte2 = unsafe bytes[unchecked: index + 1]
        let byte3 = unsafe bytes[unchecked: index + 2]
        let base64Values = bytesToBase64(byte1, byte2, byte3)
        let encodedYellow = base64ValueToASCII_branchless(base64Values.yellow)
        let encodedGreen = base64ValueToASCII_branchless(base64Values.green)
        let encodedBlue = base64ValueToASCII_branchless(base64Values.blue)
        let encodedPurple = base64ValueToASCII_branchless(base64Values.purple)
        unsafe output[outputIndex] = encodedYellow
        unsafe output[outputIndex + 1] = encodedGreen
        unsafe output[outputIndex + 2] = encodedBlue
        unsafe output[outputIndex + 3] = encodedPurple
    }
}
/// Receives 3 bytes, returns 4 base-64 values, each in range of 0 to 63.
func bytesToBase64(
    _ byte1: UInt8, _ byte2: UInt8, _ byte3: UInt8
) -> (yellow: UInt8, green: UInt8, blue: UInt8, purple: UInt8) {
    let yellow = byte1 >> 2
    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111
    let green = ((byte1 & 0x03) << 4) | (byte2 >> 4)
    let blue = ((byte2 & 0x0F) << 2) | (byte3 >> 6)
    // 0x3F == 0b0011_1111
    let purple = byte3 & 0x3F
    return (yellow, green, blue, purple)
}
/// Converts a Base64 value to its corresponding ASCII code based on the following table.
/// | Base64 Value     | 0 ... 25     | 26 ... 51     | 52 ... 61    | 62  | 63  |
/// | ASCII Characters | A ... Z      | a ... z       | 0 ... 9      |  +  |  /  |
/// | ASCII Codes      | 65 ... 90    | 97 ... 122    | 48 ... 57    | 43  | 47  |
/// | Formula          | +65 (65 - 0) | +71 (97 - 26) | -4 (48 - 52) |  -  |  -  |
/// Requires: `value` must be in range of 0 to 63. Higher values are invalid in Base64 encoding.
func base64ValueToASCII_branchless(_ value: UInt8) -> UInt8 {
    let compare25 = value <= 25
    let compare51 = value <= 51
    let compare61 = value <= 61
    let plus65 = value &+ 65
    let plus71 = value &+ 71
    let minus4 = value &- 4
    if compare25 { return plus65 }
    if compare51 { return plus71 }
    if compare61 { return minus4 }
    if value == 62 { return 43 }
    // If the value is none of the above, it must be 63 then.
    return 47
}
```
Let's benchmark:

```
$ swift package benchmark --target AutoVectorizationBenchs --filter '3_Auto_Vectorized.*'
3_Auto_Vectorized_Instructions
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Cycles (K) *              │       284 │       285 │       285 │       286 │       348 │       422 │       580 │     50000 │
├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Instructions (K) *        │      1105 │      1106 │      1106 │      1106 │      1116 │      1209 │      1575 │     50000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
3_Auto_Vectorized_Throughput
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Throughput (# / s) (#)    │     16140 │     16087 │     16007 │     15647 │     11959 │      7359 │      1557 │     50000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
```
Splendid! **16 GB/s**, up from 4.6 GB/s of the non-vectorized implementation.

But how can we tell whether it's actually Auto-Vectorized or not?

For one, the performance of the loop should lift your eyebrows. It's probably Auto-Vectorized, or it wouldn't be this fast.

But in general, there are multiple ways to tell a code is Auto-Vectorized. You can read the Assembly as an example.

However, there is a no-brainer way that requires no understanding of other representations of the code:

You can check the optimized LLVM IR representation of your code and simply search for `vector.body:`.

If there is such text in the generated IR, it means your code has indeed been Auto-Vectorized.

Let'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:

```
vector.body:
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ], !dbg !267
  %18 = shl i64 %index, 2, !dbg !269
```
There it is! The confirmation that our loop is truly vectorized.

This 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.

What if we could use our lookup table in combination with Vectorization? Let's take a brief look.

## 

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.

That means we can use a lookup table for our Base64 implementation. Just not with Auto-Vectorization. Not yet, at least.

Manually writing vectorized code will have to be the subject of a future post, but I'll give you a sneak peek of it.

Via 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):

```
/// Generate Base64 encoded bytes from the given input bytes.
/// Writes to `output`.
/// Requires:
///   - `bytes.count` must be a multiple of 3.
///   - `output.count` must be at least `bytes.count / 3 * 4`.
package func encodeBytesToBase64(
    bytes: Span<UInt8>,
    into output: UnsafeMutableBufferPointer<UInt8>
) {
    precondition(bytes.count % 3 == 0, "Bytes count needs to be a multiple of 3")
    precondition(output.count >= bytes.count / 3 * 4, "Insufficient output capacity")
    let bytesPerIteration = SIMDUInt8.laneCount * 3
    let outputBytesPerIteration = SIMDUInt8.laneCount * 4
    let iterations = bytes.count / bytesPerIteration
    withAlignedBase64Lut { base64Lut in
        for iteration in 0..<iterations {
            let index = iteration * bytesPerIteration
            let outputIndex = iteration * outputBytesPerIteration
            var byte1 = SIMDUInt8.zero()
            var byte2 = SIMDUInt8.zero()
            var byte3 = SIMDUInt8.zero()
            SIMDUInt8.loadInterleaved3(
                from: bytes.extracting(droppingFirst: index), &byte1, &byte2, &byte3
            )
            let base64Values = bytesToBase64_vectorized(byte1, byte2, byte3)
            let encodedYellow = base64ValueToASCII_vectorizedLookupTable(
                base64Values.yellow, base64Lut: base64Lut
            )
            let encodedGreen = base64ValueToASCII_vectorizedLookupTable(
                base64Values.green, base64Lut: base64Lut
            )
            let encodedBlue = base64ValueToASCII_vectorizedLookupTable(
                base64Values.blue, base64Lut: base64Lut
            )
            let encodedPurple = base64ValueToASCII_vectorizedLookupTable(
                base64Values.purple, base64Lut: base64Lut
            )
            unsafe SIMDUInt8.storeInterleaved4(
                encodedYellow, encodedGreen, encodedBlue, encodedPurple,
                to: output.baseAddress.unsafelyUnwrapped + outputIndex
            )
        }
    }
    /// The last bytes that weren't enough for a full `bytesPerIteration` iteration.
    let remainingBytes = bytes.extracting(droppingFirst: iterations * bytesPerIteration)
    let remainingOutput = unsafe UnsafeMutableBufferPointer(
        rebasing: output[(iterations * outputBytesPerIteration)...]
    )
    unsafe AutoVectorized().encodeBytesToBase64(bytes: remainingBytes, into: remainingOutput)
}
/// Receives 3 vectors of bytes, returns 4 vectors of base-64 values, each in range of 0 to 63.
func bytesToBase64_vectorized(
    _ byte1: SIMDUInt8.Vector,
    _ byte2: SIMDUInt8.Vector,
    _ byte3: SIMDUInt8.Vector
) -> (
    yellow: SIMDUInt8.Vector,
    green: SIMDUInt8.Vector,
    blue: SIMDUInt8.Vector,
    purple: SIMDUInt8.Vector
) {
    let yellow = SIMDUInt8.shiftedRight(byte1, by: 2)
    // 0x03 == 0b0000_0011, 0x0F == 0b0000_1111
    let green = SIMDUInt8.bitwiseOr(
        SIMDUInt8.shiftedLeft(
            SIMDUInt8.bitwiseAnd(byte1, SIMDUInt8.repeating(0x03)), by: 4
        ),
        SIMDUInt8.shiftedRight(byte2, by: 4)
    )
    let blue = SIMDUInt8.bitwiseOr(
        SIMDUInt8.shiftedLeft(
            SIMDUInt8.bitwiseAnd(byte2, SIMDUInt8.repeating(0x0F)), by: 2
        ),
        SIMDUInt8.shiftedRight(byte3, by: 6)
    )
    // 0x3F == 0b0011_1111
    let purple = SIMDUInt8.bitwiseAnd(byte3, SIMDUInt8.repeating(0x3F))
    return (yellow, green, blue, purple)
}
/// The Base64 Lookup Table (LUT) as an inline array.
static let base64Lut: InlineArray<64, UInt8> = [
    UInt8(ascii: "A"), UInt8(ascii: "B"), UInt8(ascii: "C"), UInt8(ascii: "D"),
    UInt8(ascii: "E"), UInt8(ascii: "F"), UInt8(ascii: "G"), UInt8(ascii: "H"),
    UInt8(ascii: "I"), UInt8(ascii: "J"), UInt8(ascii: "K"), UInt8(ascii: "L"),
    UInt8(ascii: "M"), UInt8(ascii: "N"), UInt8(ascii: "O"), UInt8(ascii: "P"),
    UInt8(ascii: "Q"), UInt8(ascii: "R"), UInt8(ascii: "S"), UInt8(ascii: "T"),
    UInt8(ascii: "U"), UInt8(ascii: "V"), UInt8(ascii: "W"), UInt8(ascii: "X"),
    UInt8(ascii: "Y"), UInt8(ascii: "Z"), UInt8(ascii: "a"), UInt8(ascii: "b"),
    UInt8(ascii: "c"), UInt8(ascii: "d"), UInt8(ascii: "e"), UInt8(ascii: "f"),
    UInt8(ascii: "g"), UInt8(ascii: "h"), UInt8(ascii: "i"), UInt8(ascii: "j"),
    UInt8(ascii: "k"), UInt8(ascii: "l"), UInt8(ascii: "m"), UInt8(ascii: "n"),
    UInt8(ascii: "o"), UInt8(ascii: "p"), UInt8(ascii: "q"), UInt8(ascii: "r"),
    UInt8(ascii: "s"), UInt8(ascii: "t"), UInt8(ascii: "u"), UInt8(ascii: "v"),
    UInt8(ascii: "w"), UInt8(ascii: "x"), UInt8(ascii: "y"), UInt8(ascii: "z"),
    UInt8(ascii: "0"), UInt8(ascii: "1"), UInt8(ascii: "2"), UInt8(ascii: "3"),
    UInt8(ascii: "4"), UInt8(ascii: "5"), UInt8(ascii: "6"), UInt8(ascii: "7"),
    UInt8(ascii: "8"), UInt8(ascii: "9"), UInt8(ascii: "+"), UInt8(ascii: "/"),
]
```
How does this perform?

```
$ swift package benchmark --target AutoVectorizationBenchs --filter '4_Vectorized_With_Lookup_Table.*'
4_Vectorized_With_Lookup_Table_Instructions
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Cycles (K) *              │       153 │       154 │       155 │       159 │       208 │       252 │       397 │     50000 │
├───────────────────────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼───────────┤
│ Instructions (K) *        │       522 │       522 │       522 │       522 │       523 │       569 │       762 │     50000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
4_Vectorized_With_Lookup_Table_Throughput
╒═══════════════════════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╤═══════════╕
│ Metric                    │        p0 │       p25 │       p50 │       p75 │       p90 │       p99 │      p100 │   Samples │
╞═══════════════════════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╪═══════════╡
│ Throughput (# / s) (#)    │     29667 │     29487 │     29199 │     28639 │     27439 │     19199 │      2843 │     50000 │
╘═══════════════════════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╧═══════════╛
```
On the cusp of **30 GB/s**, 90 times faster than our original naive loop!

What does **30 GB/s** even mean?

It's 30 billion bytes per second, or 30 bytes per nanosecond, or around 6 bytes per clock cycle, on average.

Think about it for a second. We're encoding 6 bytes to 8 Base64-encoded characters in each CPU cycle with this implementation.

## 

Here'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:

```
swift package benchmark --target AutoVectorizationBenchs
```
| Implementation | p50 | Instructions | Cycles | 
|---|---|---|---|
| Naive loop | 0.34 GB/s | 16600 K | 13800 K | 
| Lookup table | 4.6 GB/s | 8700 K | 980 K | 
| Auto-Vectorized | 16.0 GB/s | 1100 K | 285 K | 
| [Lemire (C++)](https://github.com/simdutf/simdutf) | 27.8 GB/s | 420 K | 165 K | 
| Vectorized + LUT | 29.2 GB/s | 520 K | 155 K | 

## 

As always, I'm open to any kinds of suggestions, be it technical or not.

If 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.

I'll be happy to know what parts of this post you'd like to know more about in the future.

Thank you for reading right through the end.
