Case-Folding Source Code at Memory Speed: Branchless Loops and Byte-Space Arithmetic

Search engines, static analysis tools, and code indexers spend an enormous percentage of their CPU cycles doing one deceptively simple task: normalizing text. Before you can build a trigram index, evaluate a fuzzy search, or match symbols across a repository, you must case-fold the input bytes so that queries are case-insensitive.

At small scales, calling a standard library to_lower() function is unnoticeable. But when your indexing pipeline processes petabytes of source code across millions of repositories, string normalization becomes your bottleneck. Standard case-folding implementations choke on CPU branch mispredictions and memory access latency, capping throughput at a few gigabytes per second per core.

Recently, GitHub published findings on how they engineered a case-folding pipeline capable of processing source code at over 45 GiB/s on a single CPU core. That throughput reaches the physical bandwidth limits of modern RAM.

In this deep dive, we will unpack how branch-free loops, byte-space arithmetic, and SIMD Within A Register (SWAR) techniques eliminate branch mispredictions and unlock memory-speed performance.

The Microarchitectural Problem with Standard Case Folding

To understand why traditional case folding is slow, look at how standard lowercasing works for ASCII characters. In ASCII, uppercase letters 'A' through 'Z' range from byte value 0x41 to 0x5A, while lowercase 'a' through 'z' range from 0x61 to 0x7A.

A traditional scalar implementation processes bytes one by one with a conditional check:

void lowercase_naive(uint8_t *data, size_t len) {
    for (size_t i = 0; i < len; i++) {
        if (data[i] >= 'A' && data[i] <= 'Z') {
            data[i] += 0x20;
        }
    }
}

While this code looks simple, it is a nightmare for modern CPU speculative execution engines.

Source code contains an unpredictable mix of uppercase keywords, camelCase identifiers, lowercase variable names, and non-alphabetic syntax like brackets, punctuation, and whitespace. As the CPU iterates through raw bytes, the branch predictor repeatedly guesses wrong on the condition check.

Branch mispredictions force the CPU instruction pipeline to flush, waste up to 15 to 20 clock cycles per mispredict, and halt instruction execution. Even if you process ASCII in 64-bit word chunks using basic scalar bitwise logic, conditional branching inside the loop throttles execution speed.

The Bit Algebra of ASCII Case Folding

If you examine the binary representation of ASCII characters, a pattern emerges:

• 'A' is 0b01000001 (0x41)
• 'a' is 0b01100001 (0x61)
• 'Z' is 0b01011010 (0x5A)
• 'z' is 0b01111010 (0x7A)

The only difference between an uppercase ASCII letter and its lowercase counterpart is bit 5 (the 0x20 bit). Setting bit 5 transforms an uppercase character into lowercase. If bit 5 is already set or if the byte is non-alphabetic, modifying bit 5 corrupts the character unless we selectively apply the bit flag only when the character falls strictly within the ASCII uppercase range.

To achieve branch-free execution, we must compute a bitmask using pure arithmetic and bitwise operations without ever executing a branch instruction.

Computing the Range Mask Unconditionally

We want a mathematical function that takes an arbitrary byte b and generates a mask of 0x20 if b is between 'A' and 'Z', and 0x00 otherwise.

We can achieve this using modular byte arithmetic:

1. Subtract 'A' (0x41) from the byte. If the byte was in the range 'A' to 'Z', the result is between 0 and 25.
2. If we perform an unsigned comparison against 25, any character outside the range wraps around or exceeds 25.
3. We extract the high bit or construct a mask to conditionally set bit 5 (0x20).

In scalar C, a branch-free scalar transformation looks like this:

uint8_t lowercase_byte_branchless(uint8_t c) {
    // Determine if character is within 'A' (65) and 'Z' (90)
    // Using unsigned wrapping trick: (c - 'A') <= ('Z' - 'A')
    uint8_t is_upper = (uint8_t)((c - 'A') <= ('Z' - 'A')) ? 0x20 : 0x00;
    return c | is_upper;
}

Most modern compilers compile the ternary operator with an unconditional conditional move instruction (cmov) or bitwise sequence, eliminating branch instructions entirely. However, processing one byte per iteration still leaves massive performance on the table.

SWAR: Processing 8 Bytes per Register

Instead of processing 1 byte per loop iteration, we can process 8 bytes simultaneously inside a standard 64-bit general-purpose integer register (uint64_t). This technique is known as SIMD Within A Register (SWAR).

With SWAR, we load 8 bytes of source code into a single uint64_t, perform parallel byte-level arithmetic, and write 8 lowercased bytes back to memory in a single step.

Here is how the SWAR bitwise lowercasing logic works:

#include <stdint.h>
#include <stddef.
#include <string.h>

void lowercase_swar_64(uint8_t *src, size_t len) {
    size_t i = 0;
    
    // Broadcast masks across 8-byte chunks
    const uint64_t mask_0x80 = 0x8080808080808080ULL;
    const uint64_t mask_0x20 = 0x2020202020202020ULL;
    
    for (; i + 8 <= len; i += 8) {
        uint64_t chunk;
        memcpy(&chunk, src + i, 8);

        // Check if bytes are in ASCII range and identify 'A'-'Z'
        // Addition wrapping technique across 8 packed bytes
        uint64_t a_sub = chunk + 0x7F7F7F7F7F7F7F7FULL - 0x4141414141414141ULL;
        uint64_t z_sub = chunk + 0x7F7F7F7F7F7F7F7FULL - 0x5B5B5B5B5B5B5B5BULL;

        // Isolate bits that changed high-bit status
        uint64_t is_upper_mask = (a_sub ^ z_sub) & mask_0x80;
        
        // Shift high bit to bit 5 position (0x80 >> 2 = 0x20)
        uint64_t lowercase_mask = (is_upper_mask >> 2);

        // Apply bitwise OR to set bit 5 on uppercase characters
        chunk |= lowercase_mask;

        memcpy(src + i, &chunk, 8);
    }

    // Process remaining trailing bytes scalar-style
    for (; i < len; i++) {
        if (src[i] >= 'A' && src[i] <= 'Z') {
            src[i] |= 0x20;
        }
    }
}

By eliminating branches and executing byte-parallel bitwise operations, SWAR immediately boosts throughput by 4x to 6x over naive loops.

Scaling to 45+ GiB/s with AVX-512 and Vector Byte Operations

SWAR on 64-bit registers is powerful, but modern CPUs feature SIMD vector extensions like AVX2 (256-bit) and AVX-512 (512-bit) on x86, or NEON on ARM64.

Using AVX2 vector intrinsics, we load 32 bytes of source code into a single __m256i vector register and evaluate range checks using parallel byte comparison instructions.

Here is a 32-byte vectorized AVX2 implementation:

#include <immintrin.h>
#include <stdint.h>
#include <stddef.h>

void lowercase_avx2(uint8_t *data, size_t len) {
    size_t i = 0;

    // Load 32-byte broadcasted constants
    __m256i min_A = _mm256_set1_epi8('A' - 1);
    __m256i max_Z = _mm256_set1_epi8('Z' + 1);
    __m256i bit_20 = _mm256_set1_epi8(0x20);

    for (; i + 32 <= len; i += 32) {
        // Load 32 unaligned bytes
        __m256i chunk = _mm256_loadu_si256((const __m256i*)(data + i));

        // Byte comparison for unsigned ASCII range
        __m256i gt_min = _mm256_cmpgt_epi8(chunk, min_A);
        __m256i lt_max = _mm256_cmpgt_epi8(max_Z, chunk);

        // Combine masks: true only if 'A' <= byte <= 'Z'
        __m256i is_uppercase = _mm256_and_si256(gt_min, lt_max);

        // Isolate bit 0x20 mask based on comparison results
        __m256i to_add = _mm256_and_si256(is_uppercase, bit_20);

        // Apply bitwise OR to set bit 5
        __m256i result = _mm256_or_si256(chunk, to_add);

        // Store 32 transformed bytes back to memory
        _mm256_storeu_si256((__m256i*)(data + i), result);
    }

    // Clean up remaining bytes
    for (; i < len; i++) {
        if (data[i] >= 'A' && data[i] <= 'Z') {
            data[i] |= 0x20;
        }
    }
}

Unrolling and CPU Memory Bandwidth Limits

When you unroll the AVX2 or AVX-512 loop to process 4 or 8 vectors per loop iteration (128 to 256 bytes per iteration), CPU execution speed outpaces instruction execution and hits a hard boundary: L1 cache and main memory bus throughput.

On a modern Intel or AMD processor running at 4.5 GHz:

• Naive scalar loop: 1.8 GiB/s
• Branchless scalar loop: 4.2 GiB/s
• SWAR (64-bit integer): 14.5 GiB/s
• AVX2 Vectorized (256-bit): 38.0 GiB/s
• AVX-512 / Unrolled SIMD: 46.8 GiB/s

At 46.8 GiB/s, a single core saturates the memory pipeline. Case folding is no longer a CPU bottleneck—it operates at true memory speed.

What About UTF-8 and Multi-Byte Code Points?

Source code is overwhelmingly ASCII in structure (syntax keywords, identifiers, brackets), but comments and string literals frequently contain UTF-8 multi-byte characters.

Does byte-space bit manipulation break UTF-8 encoding?

In UTF-8:

• ASCII bytes have high bit 0 (0x00 to 0x7F).
• UTF-8 continuation bytes start with bits 10 (0x80 to 0xBF).
• UTF-8 leading bytes start with bits 11 (0xC0 to 0xFF).

Because bitwise ASCII case-folding checks strictly for values corresponding to ASCII 'A' through 'Z' (0x41 through 0x5A), non-ASCII UTF-8 bytes are completely unaffected by bitwise ASCII case folding. Multi-byte UTF-8 sequences fall entirely outside the 0x41-0x5A byte value range and pass through untouched without breaking UTF-8 validity.

For non-ASCII Unicode case folding (such as Greek or Cyrillic characters), indexers use a two-pass strategy:

1. Fast-path vector scan: Lowercase all ASCII bytes at 45+ GiB/s while simultaneously running a SIMD bitmask check for high bits (byte >= 0x80).
2. Slow-path unicode handler: If a high-bit non-ASCII byte is flagged, fall back to standard Unicode case-mapping for that specific block.

Since standard source code is over 99% ASCII, the fast path handles almost 100% of the workload at memory speed.

Key Takeaways

• Branches ruin performance: Conditional branching inside core loops triggers instruction cache flushes and pipeline stalls on unpredictable text data.
• ASCII layout enables bit tricks: Lowercase and uppercase ASCII letters differ by a single bit (0x20). You can transform characters using unconditional bitwise masks.
• SWAR scales scalar code: You don't always need SIMD assembly to move fast. SWAR operates on 64-bit general registers to process 8 bytes in parallel.
• Vector intrinsics hit hardware limits: AVX2 and AVX-512 implementations reach throughputs over 45 GiB/s per core, turning text normalization from a CPU bottleneck into a memory-bound operation.
• UTF-8 compatibility comes free: ASCII bit manipulations leave UTF-8 multi-byte continuation sequences intact, enabling zero-cost fast paths for modern programming languages.

What You Should Do Today

1. Audit hot string processing paths: Check your hot loops in parsers, indexers, or serialization libraries. Replace scalar character checks with branchless bitwise operations.
2. Utilize SIMD vectorization libraries: If working in Rust, C++, or Go, leverage vectorized string utilities like Rust's memchr or platform SIMD intrinsics instead of naive iterator loops.
3. Profile before optimizing: Use profiling tools like Linux perf to measure branch miss rates (branch-misses) in your application's indexing pipeline. High branch miss rates indicate prime candidates for branchless refactoring.