SIMD Optimization Layer

Navigation: ← Distance Calculation | Back to Algorithms | Zipper Navigation →

Overview

The SIMD (Single Instruction, Multiple Data) Optimization Layer provides vectorized acceleration for critical hotspots in fuzzy matching. By processing multiple data elements simultaneously, SIMD instructions can provide 2-4x speedups for edge label scanning and state transitions.

Characteristic vector: one SIMD compare turns a block of edge labels into a match bitmask.

What is SIMD?

SIMD allows a single CPU instruction to operate on multiple data elements in parallel:

Scalar (normal) operation:
  compare('a', 'a') → true   (1 comparison)
  compare('b', 'a') → false  (1 comparison)
  compare('c', 'a') → false  (1 comparison)
  compare('d', 'a') → false  (1 comparison)
  Total: 4 instructions

SIMD operation (AVX2):
  compare(['a','b','c','d'], 'a') → [true, false, false, false]
  Total: 1 instruction (4x throughput)

Where SIMD Helps

liblevenshtein applies SIMD to these bottlenecks:

1. Edge Label Scanning: Finding matching edges in dictionary nodes
2. State Component Operations: Processing (position, distance) pairs
3. Intersection Tests: Checking state overlaps

SIMD Instruction Sets

Supported ISAs

ISA	Year	Width	Elements	Availability
SSE4.1	2006	128-bit	16× u8 or 4× u32	$\ge 99\%$ of CPUs
AVX2	2013	256-bit	32× u8 or 8× u32	$\ge 95\%$ of CPUs
AVX-512	2016	512-bit	64× u8 or 16× u32	High-end Intel/AMD

liblevenshtein supports SSE4.1 and AVX2 with runtime detection. On x86_64 this is fully automatic — no Cargo feature flag is required to enable SIMD; the fastest available implementation (AVX2, then SSE4.1, then scalar) is chosen per call via is_x86_feature_detected!. On non-x86_64 targets the scalar path runs.

Runtime Detection

#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;

pub fn has_avx2() -> bool {
    #[cfg(target_arch = "x86_64")]
    {
        is_x86_feature_detected!("avx2")
    }
    #[cfg(not(target_arch = "x86_64"))]
    {
        false
    }
}

pub fn has_sse41() -> bool {
    #[cfg(target_arch = "x86_64")]
    {
        is_x86_feature_detected!("sse4.1")
    }
    #[cfg(not(target_arch = "x86_64"))]
    {
        false
    }
}

At runtime, the library selects the best available implementation:

if has_avx2() → use AVX2 version (32 chars at once)
else if has_sse41() → use SSE4.1 version (16 chars at once)
else → use scalar version (1 char at a time)

Edge Label Scanning

The Problem

Dictionary nodes have edges labeled with characters. During traversal, we need to find edges matching a target character:

// Find edge labeled 'e' among many edges
fn find_edge_scalar(edges: &[char], target: char) -> Option<usize> {
    for (i, &edge_label) in edges.iter().enumerate() {
        if edge_label == target {
            return Some(i);
        }
    }
    None
}

Performance: $\mathcal{O}(N)$ comparisons, 1 char per cycle

SIMD Solution

Process multiple edge labels per instruction:

#[target_feature(enable = "avx2")]
unsafe fn find_edge_avx2(edges: &[char], target: char) -> Option<usize> {
    let target_vec = _mm256_set1_epi32(target as i32);  // Broadcast target

    for (chunk_idx, chunk) in edges.chunks(8).enumerate() {
        // Load 8 chars (32 bytes)
        let edge_vec = _mm256_loadu_si256(chunk.as_ptr() as *const __m256i);

        // Compare all 8 at once
        let cmp_result = _mm256_cmpeq_epi32(edge_vec, target_vec);

        // Check if any matched
        let mask = _mm256_movemask_ps(_mm256_castsi256_ps(cmp_result));

        if mask != 0 {
            // Found a match! Determine which one
            let offset = mask.trailing_zeros() as usize;
            return Some(chunk_idx * 8 + offset);
        }
    }

    None
}

Performance: Process 8 chars per iteration (8x throughput)

Byte-Level Optimization

For u8 edges (byte-level dictionaries), we can do even better:

#[target_feature(enable = "avx2")]
unsafe fn find_edge_u8_avx2(edges: &[u8], target: u8) -> Option<usize> {
    let target_vec = _mm256_set1_epi8(target as i8);  // Broadcast

    for (chunk_idx, chunk) in edges.chunks(32).enumerate() {
        // Load 32 bytes at once
        let edge_vec = _mm256_loadu_si256(chunk.as_ptr() as *const __m256i);

        // Compare all 32
        let cmp_result = _mm256_cmpeq_epi8(edge_vec, target_vec);

        // Convert to bitmask
        let mask = _mm256_movemask_epi8(cmp_result);

        if mask != 0 {
            let offset = mask.trailing_zeros() as usize;
            return Some(chunk_idx * 32 + offset);
        }
    }

    None
}

Performance: Process 32 bytes per iteration (32x throughput)

Benchmark Results

Edge Scanning Performance

Find edge in list of 100 labels:

Scalar (1 char/iteration):      342ns
SSE4.1 (16 chars/iteration):    89ns   (3.8x faster)
AVX2 (32 bytes/iteration):      47ns   (7.3x faster)

Find edge in list of 20 labels:

Scalar:                         68ns
SSE4.1:                         24ns   (2.8x faster)
AVX2:                           16ns   (4.3x faster)

Insight: SIMD provides consistent 3-7x speedup for edge scanning.

Impact on End-to-End Queries

Fuzzy search "test" (distance 2) in 10K-term dict:

Without SIMD:                   28.4µs
With SIMD:                      16.3µs  (1.7x faster)

Edge scanning share of time:
  Without SIMD: ~40% of total
  With SIMD: ~15% of total

Overall speedup: 1.7-2x for typical fuzzy queries

State Component Operations

The Problem

Automaton states contain vectors of (position, distance) pairs:

type State = Vec<(usize, usize)>;

fn has_accepting_component(state: &State, query_len: usize, max_dist: usize) -> bool {
    for &(pos, dist) in state {
        if pos == query_len && dist <= max_dist {
            return true;
        }
    }
    false
}

SIMD Solution

Process multiple components simultaneously:

#[target_feature(enable = "avx2")]
unsafe fn has_accepting_component_avx2(
    positions: &[usize],
    distances: &[usize],
    query_len: usize,
    max_dist: usize,
) -> bool {
    let query_len_vec = _mm256_set1_epi64x(query_len as i64);
    let max_dist_vec = _mm256_set1_epi64x(max_dist as i64);

    for i in (0..positions.len()).step_by(4) {
        // Load 4 positions and 4 distances
        let pos_vec = _mm256_loadu_si256(positions[i..].as_ptr() as *const __m256i);
        let dist_vec = _mm256_loadu_si256(distances[i..].as_ptr() as *const __m256i);

        // Check: pos == query_len
        let pos_match = _mm256_cmpeq_epi64(pos_vec, query_len_vec);

        // Check: dist <= max_dist
        let dist_ok = _mm256_cmpgt_epi64(
            _mm256_add_epi64(max_dist_vec, _mm256_set1_epi64x(1)),
            dist_vec
        );

        // Combine: pos_match AND dist_ok
        let result = _mm256_and_si256(pos_match, dist_ok);

        if _mm256_movemask_epi8(result) != 0 {
            return true;
        }
    }

    false
}

Performance: Check 4 components per iteration

Practical Usage

Automatic SIMD Selection

The library automatically uses the best available SIMD:

use libdictenstein::double_array_trie::DoubleArrayTrie;
use liblevenshtein::transducer::{Algorithm, Transducer};

let dict = DoubleArrayTrie::from_terms(vec![/* ... */]);

// SIMD automatically used if available (runtime AVX2/SSE4.1 detection)
let transducer = Transducer::new(dict, Algorithm::Standard);
let results: Vec<String> = transducer.query("test", 2).collect();
// ↑ Internally uses AVX2/SSE4.1 if CPU supports it

No special configuration needed!

Disabling SIMD

For testing or compatibility:

// Set environment variable to disable SIMD
std::env::set_var("LIBLEVENSHTEIN_NO_SIMD", "1");

// Or use scalar path explicitly (internal API)
#[cfg(feature = "simd-internals")]
{
    use liblevenshtein::transducer::simd::find_edge_label_scalar;
    find_edge_label_scalar(edges, target);
}

Compile-Time Configuration

Build with specific SIMD support:

# Enable AVX2 at compile time (requires CPU support at runtime)
RUSTFLAGS="-C target-cpu=native" cargo build --release

# Force SSE4.1 only
RUSTFLAGS="-C target-feature=+sse4.1" cargo build --release

# Disable SIMD entirely
RUSTFLAGS="-C target-feature=-avx2,-sse4.1" cargo build --release

Implementation Details

Memory Alignment

SIMD loads perform best with aligned memory:

// Aligned allocation for edge labels
#[repr(align(32))]  // AVX2 alignment
struct AlignedEdges {
    data: Vec<u8>,
}

impl AlignedEdges {
    fn new(edges: Vec<u8>) -> Self {
        // Ensure capacity is multiple of 32
        let mut data = edges;
        let remainder = data.len() % 32;
        if remainder != 0 {
            data.reserve(32 - remainder);
        }
        Self { data }
    }
}

Handling Partial Chunks

Last chunk may have fewer elements than SIMD width:

unsafe fn find_edge_avx2_with_tail(edges: &[u8], target: u8) -> Option<usize> {
    let chunks = edges.len() / 32;
    let remainder = edges.len() % 32;

    // Process full chunks with AVX2
    for i in 0..chunks {
        let chunk = &edges[i * 32..(i + 1) * 32];
        if let Some(offset) = find_in_chunk_avx2(chunk, target) {
            return Some(i * 32 + offset);
        }
    }

    // Process remainder with scalar
    if remainder > 0 {
        let tail = &edges[chunks * 32..];
        for (i, &edge) in tail.iter().enumerate() {
            if edge == target {
                return Some(chunks * 32 + i);
            }
        }
    }

    None
}

Portability

SIMD code is architecture-specific:

#[cfg(target_arch = "x86_64")]
fn find_edge_optimized(edges: &[u8], target: u8) -> Option<usize> {
    if is_x86_feature_detected!("avx2") {
        unsafe { find_edge_avx2(edges, target) }
    } else if is_x86_feature_detected!("sse4.1") {
        unsafe { find_edge_sse41(edges, target) }
    } else {
        find_edge_scalar(edges, target)
    }
}

#[cfg(target_arch = "aarch64")]
fn find_edge_optimized(edges: &[u8], target: u8) -> Option<usize> {
    // Use ARM NEON instructions
    unsafe { find_edge_neon(edges, target) }
}

#[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
fn find_edge_optimized(edges: &[u8], target: u8) -> Option<usize> {
    // Fallback to scalar
    find_edge_scalar(edges, target)
}

Performance Tuning

When SIMD Helps Most

✅ SIMD is beneficial when:

• Nodes have many children (>8 edges)
• High branching factor in dictionary
• Edge labels are bytes (u8) not chars
• CPU supports AVX2

⚠️ SIMD may not help when:

• Nodes have few children (<4 edges)
• Low branching factor
• Cache misses dominate (SIMD can't fix this)

Profiling SIMD Impact

# Profile with perf
RUSTFLAGS="-C target-cpu=native" cargo build --release
perf record --call-graph dwarf ./target/release/my_benchmark
perf report

# Look for time spent in:
# - find_edge_label_simd
# - find_edge_label_scalar
# - _mm256_* intrinsics

Measuring Speedup

use std::time::Instant;

let edges: Vec<u8> = (0..100).collect();
let target = 99u8;

// Benchmark scalar
let start = Instant::now();
for _ in 0..100_000 {
    find_edge_scalar(&edges, target);
}
let scalar_time = start.elapsed();

// Benchmark SIMD
let start = Instant::now();
for _ in 0..100_000 {
    find_edge_simd(&edges, target);
}
let simd_time = start.elapsed();

println!("Scalar: {:?}", scalar_time);
println!("SIMD: {:?}", simd_time);
println!("Speedup: {:.2}x", scalar_time.as_nanos() as f64 / simd_time.as_nanos() as f64);

Advanced Topics

Auto-Vectorization vs Intrinsics

Auto-vectorization: Compiler automatically generates SIMD code

// May auto-vectorize
fn find_edge_auto(edges: &[u8], target: u8) -> Option<usize> {
    edges.iter().position(|&e| e == target)
}

Intrinsics: Explicit SIMD instructions

// Guaranteed SIMD
#[target_feature(enable = "avx2")]
unsafe fn find_edge_intrinsics(edges: &[u8], target: u8) -> Option<usize> {
    // Explicit _mm256_* calls
}

Trade-offs:

• Auto-vectorization: Simpler, less control, may not vectorize
• Intrinsics: Complex, full control, guaranteed behavior

liblevenshtein uses intrinsics for critical paths.

Cache Line Awareness

AVX2 loads 32 bytes (half a cache line):

Cache line (64 bytes):
[───────────── 32 bytes ─────────────][───────────── 32 bytes ─────────────]
 ↑ First AVX2 load                      ↑ Second AVX2 load

Scalar would need 32 loads (32 cache line accesses)
AVX2 needs 2 loads (2 cache line accesses)

This improves cache efficiency by 16x.

Prefetching

Hint CPU to load data early:

use std::arch::x86_64::*;

unsafe fn find_edge_with_prefetch(edges: &[u8], target: u8) -> Option<usize> {
    // Prefetch next chunk
    if edges.len() >= 64 {
        _mm_prefetch(edges[32..].as_ptr() as *const i8, _MM_HINT_T0);
    }

    // Process current chunk
    find_edge_avx2(&edges[..32.min(edges.len())], target)
}

Impact: 5-10% improvement for large edge lists.

Platform Support

x86-64 (Intel/AMD)

• ✅ SSE4.1: Universal support (2006+)
• ✅ AVX2: 95%+ support (2013+)
• ⚠️ AVX-512: Limited (high-end only)

ARM64

• ✅ NEON: Universal on ARM64
• ⚠️ SVE: Limited (server CPUs)

liblevenshtein uses NEON on ARM64.

Other Architectures

• ❌ RISC-V: No SIMD support yet
• ❌ 32-bit x86: Not supported

Fallback to scalar on unsupported platforms.

Related Documentation

• Intersection Layer - Where SIMD is applied
• Performance Guide - Benchmarking and profiling
• Dictionary Layer - Edge structures

References

Intel Intrinsics

1. Intel Intrinsics Guide
   • 📄 https://www.intel.com/content/www/us/en/docs/intrinsics-guide/
   • Official reference for x86 SIMD intrinsics

Rust SIMD

2. std::arch documentation

   • 📄 https://doc.rust-lang.org/std/arch/
   • Rust's platform-specific intrinsics

3. Rust SIMD Working Group

   • 📄 https://github.com/rust-lang/portable-simd
   • Portable SIMD API (experimental)

Performance Guides

4. Lemire, D. (2018). "Faster UTF-8 validation with AVX2"
   • 📄 Blog post on practical SIMD techniques
   • https://lemire.me/blog/

Academic Papers

5. Fog, A. (2023). "Optimizing software in C++"
   • 📄 https://www.agner.org/optimize/
   • Comprehensive optimization manual including SIMD

Next Steps

• Profiling: Learn to measure SIMD impact
• Traversal: See Intersection Layer
• Benchmarking: Check Performance Guide

---

Navigation: ← Distance Calculation | Back to Algorithms | Zipper Navigation →