SIMD-Backed String Data Structures

Overview

Most string libraries treat SIMD as an acceleration layer: the string lives in a conventional byte buffer, and specific operations (search, comparison, case conversion) temporarily load chunks into vector registers, process them, and write results back. This approach incurs repeated conversion overhead—data moves between scalar memory and SIMD registers on every operation.

A SIMD-backed string inverts this design. The string is a SIMD vector. All character data resides permanently inside a single hardware vector register (or its memory-mapped equivalent), and every operation executes directly on that vector without marshalling bytes in or out. The tradeoff is a hard size cap: strings cannot exceed the vector width (16 bytes on SSE, 32 on AVX2, 64 on AVX-512). Within that constraint, operations like case conversion, character replacement, and substring search become branchless single-instruction sequences that complete in hundreds of picoseconds rather than tens of nanoseconds.

This pattern is particularly relevant for hot-path string processing in tokenizers, lexers, symbol tables, short identifier comparison, and any workload where strings are known to be small and processed in tight loops. The technique demonstrates a broader systems design principle: when a data structure fits entirely within a hardware primitive, the primitive becomes the data structure, eliminating abstraction overhead entirely.

Core Concepts

Vector-Native Storage

In a SIMD-backed string, the backing store is a fixed-width SIMD vector (e.g., Simd<u8, 32> for a 32-byte AVX2 register). The string occupies the low bytes of the vector, with remaining bytes zeroed as NUL padding. This is analogous to NUL-terminated C strings, but the termination is implicit in the vector width rather than requiring a sentinel scan. The entire string can be loaded, compared, hashed, or transformed in a single instruction or short instruction sequence.

Branchless Mask-and-Select Operations

Traditional string algorithms use conditional branches to decide per-character behavior: “if this byte is uppercase, subtract 32.” Branches are expensive on modern CPUs due to pipeline stalls on misprediction. SIMD-backed strings replace branches with mask-and-select: a comparison instruction produces a bitmask identifying which lanes satisfy a condition, and a select (blend) instruction applies the transformation only to those lanes. The result is a constant-time, branchless operation regardless of string content.

Width Constraints and the Small-String Assumption

The fundamental limitation is that strings must fit within a single vector register. On current hardware, this means a maximum of 16 bytes (SSE/NEON), 32 bytes (AVX2), or 64 bytes (AVX-512). This makes the pattern unsuitable for arbitrary-length text but ideal for identifiers, tokens, short keys, enum names, and other bounded-length strings common in systems programming. Many real-world workloads have string length distributions where 90%+ of values fit within 32 bytes.

How It Works

Constructing a SIMD String

Construction copies bytes from a source slice into a zeroed SIMD vector. The Rust portable-simd API provides Simd::from_array for this. Any bytes beyond the string length remain zero (NUL), which simplifies length computation and comparison.

use std::simd::prelude::*;

const N: usize = 32; // AVX2 width
type SimdStr = Simd<u8, N>;

fn from_bytes(src: &[u8]) -> SimdStr {
    assert!(src.len() <= N);
    let mut buf = [0u8; N];
    buf[..src.len()].copy_from_slice(src);
    Simd::from_array(buf)
}

Case Conversion via Mask-and-Select

To convert uppercase ASCII to lowercase, the algorithm identifies bytes in the range [A, Z] (65–90) using two lane-wise comparisons, combines the results into a mask, and conditionally adds 32 (the ASCII distance between upper and lower case) only to masked lanes.

fn to_lowercase(s: SimdStr) -> SimdStr {
    let a = Simd::splat(b'A');
    let z = Simd::splat(b'Z');
    let diff = Simd::splat(b'a' - b'A'); // 32

    // Lanes where byte is in [A..=Z]
    let is_upper = s.simd_ge(a) & s.simd_le(z);

    // Add 32 only to uppercase lanes; leave others unchanged
    is_upper.select(s + diff, s)
}

This executes in 3–5 SIMD instructions regardless of string content. No branch, no loop, no per-character dispatch.

Character Replacement

Replacing all occurrences of a character is a single equality comparison followed by a select:

fn replace_char(s: SimdStr, from: u8, to: u8) -> SimdStr {
    let mask = s.simd_eq(Simd::splat(from));
    mask.select(Simd::splat(to), s)
}

Length Computation

Because unused lanes are zeroed, string length equals the count of non-zero bytes. A SIMD comparison against zero produces a bitmask, and a popcount (or trailing-zeros) on that mask yields the length without scanning byte-by-byte:

fn len(s: SimdStr) -> usize {
    let zero = Simd::splat(0u8);
    let nonzero_mask = s.simd_ne(zero);
    nonzero_mask.to_bitmask().count_ones() as usize
}

Practical Applications

Tokenizer Hot Paths

BPE and WordPiece tokenizers spend significant time comparing, hashing, and normalizing short token strings. When the vocabulary consists of subword units (typically 1–15 bytes), every token fits in a SIMD vector. Case-folding, prefix matching, and equality checks during vocabulary lookup become single-instruction operations. In high-throughput inference pipelines tokenizing thousands of requests per second, this can eliminate tokenization as a bottleneck.

Symbol Tables and Identifier Lookup

Compilers, interpreters, and query engines maintain symbol tables mapping short identifier strings to metadata. A hash map keyed by SIMD-backed strings benefits twice: the hash function processes the entire key in one instruction (e.g., using AES-NI on the vector), and equality comparison during probe is a single simd_eq plus a reduction. This is substantially faster than byte-by-byte memcmp for keys under 32 bytes.

Log Parsing and Field Extraction

Structured log formats (JSON, logfmt, CSV) contain many short field names and enum-like values. A SIMD-backed string set can accelerate field-name matching in parsers, replacing hash lookups with direct vector comparisons when the field set is small and known at compile time.

Network Protocol Headers

HTTP method names (GET, POST, PUT, DELETE), status codes, and header field names are all short, bounded strings processed on every request. SIMD-backed comparison allows a parser to identify the method in a single instruction rather than a chain of strcmp calls or a trie traversal.

Implementation Patterns

Portable SIMD Abstraction

Rust’s std::simd (nightly, as of 2026) provides a portable abstraction over SSE, AVX2, AVX-512, and ARM NEON. The same Simd<u8, N> type compiles to the optimal instruction set for the target. This avoids writing separate intrinsic-based implementations per architecture. The key pattern is parameterizing on N (the lane count), letting the type system enforce the width constraint at compile time.

// Generic over SIMD width: works on SSE (16), AVX2 (32), AVX-512 (64)
use std::simd::{prelude::*, LaneCount, SupportedLaneCount};

struct SStr<const N: usize>
where
    LaneCount<N>: SupportedLaneCount,
{
    data: Simd<u8, N>,
}

impl<const N: usize> SStr<N>
where
    LaneCount<N>: SupportedLaneCount,
{
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data
    }
}

Fallback for Long Strings

A practical string type uses an enum that distinguishes inline (SIMD-backed) and heap-allocated variants, similar to the small-string optimization (SSO) in C++. Strings up to the vector width live in the SIMD path; longer strings fall back to a conventional Vec<u8>. The branch is taken once at construction, not on every operation.

Alignment and Memory Layout

SIMD loads and stores are fastest when the memory address is aligned to the vector width (32-byte alignment for AVX2). Allocators and struct layouts should ensure SIMD-backed string fields are properly aligned. In Rust, #[repr(align(32))] on a wrapper struct achieves this. Misaligned access still works on modern x86 but incurs a latency penalty when crossing cache-line boundaries.

Performance Considerations

• Sub-nanosecond operations: Benchmarks on AVX2 hardware show replace completing in ~741 picoseconds versus ~27 nanoseconds for a standard String::replace—a 36x speedup. Case conversion (to_uppercase) achieves ~382 picoseconds versus ~16.6 nanoseconds (43x speedup). These gains come from eliminating loops, branches, and memory indirection.
• Cache efficiency: A 32-byte SIMD string fits in half a cache line. Operations never touch memory beyond the vector, so there are no cache misses during processing. For workloads that scan arrays of short strings, the entire working set may fit in L1 cache.
• Register pressure: Each SIMD string occupies one vector register. On AVX2, only 16 YMM registers are available. Functions operating on many SIMD strings simultaneously may spill registers to the stack, negating the performance advantage. Profile to ensure the hot loop doesn’t exceed the register file.
• Startup cost: Loading a string from memory into a SIMD register has a fixed latency (~4–7 cycles). For one-shot operations on a single string, this setup cost may dominate. The pattern pays off in loops processing many strings or performing multiple operations on the same string.
• Width portability: Code written for AVX2 (32 bytes) may be too narrow for some use cases and unnecessarily wide for others. Using Rust’s generic LaneCount lets the compiler select the optimal width, but the programmer must reason about the maximum string length their application guarantees.

Common Pitfalls

• Assuming arbitrary string lengths: The most common mistake is applying this pattern to strings that can exceed the vector width. A 33-byte string silently truncates or panics at construction. Always validate that the domain guarantees a length bound matching the chosen SIMD width.
• NUL bytes in content: The length-computation trick relies on zero bytes being unused padding. If the string legitimately contains NUL bytes (binary data, certain encodings), the length calculation returns incorrect results and operations may silently corrupt data. This pattern is safe for ASCII and UTF-8 text (which never contains internal NULs) but not for arbitrary binary.
• Non-ASCII text: Multi-byte UTF-8 characters span multiple SIMD lanes. Operations like to_lowercase that assume one byte per character produce incorrect results for non-ASCII input. Either restrict the type to ASCII-only or implement UTF-8-aware SIMD algorithms (significantly more complex).
• Benchmarking with cold caches: Microbenchmarks that operate on a single string in a loop measure best-case performance with the data already in registers. Real-world performance depends on whether the string is in cache when the operation starts. Measure with realistic access patterns.
• Ignoring alignment: Storing SIMD-backed strings in a Vec or hash map without ensuring alignment forces the CPU to perform unaligned loads. On x86 this works but adds latency; on some ARM targets it may fault. Always use aligned storage.