Date: 2025-10-30 Status: Research Phase Goal: 2-4x additional speedup on medium/long strings
SIMD (Single Instruction, Multiple Data) vectorization can provide significant speedups for dynamic programming algorithms like Levenshtein distance by processing multiple cells of the DP matrix in parallel.
Target Performance:
pulp (RECOMMENDED) ⭐⭐⭐⭐⭐Crate: pulp = "0.21.5"
Pros:
Cons:
Best for: Production code that needs portable, safe SIMD on stable Rust
wide ⭐⭐⭐⭐Crate: wide = "0.8.1"
Pros:
std::simdCons:
pulp (more manual work)Best for: Projects that compile for specific CPU targets
std::arch intrinsics ⭐⭐⭐Built-in: No external dependencies
Pros:
Cons:
Best for: Expert-level optimization where every nanosecond counts
std::simd (Nightly only) ⭐⭐Status: Nightly-only (unstable feature portable_simd)
Pros:
Cons:
Best for: Experimental/personal projects that can use nightly
pulpFor this project, I recommend pulp because:
The inner loop of Levenshtein distance is embarrassingly parallel:
// Current scalar code (processes 1 cell at a time)
for j in 1..=n {
let cost = if source_chars[i - 1] == target_chars[j - 1] { 0 } else { 1 };
curr_row[j] = min3(
prev_row[j] + 1, // deletion
curr_row[j - 1] + 1, // insertion
prev_row[j - 1] + cost // substitution
);
}
SIMD approach: Process 8 cells at once (with AVX2)
// SIMD vectorized (processes 8 cells at once)
for j in (1..=n).step_by(8) {
// Load 8 cells from prev_row, curr_row
let prev = load_u32x8(&prev_row[j..]);
let curr_left = load_u32x8(&curr_row[j-1..]);
let diag = load_u32x8(&prev_row[j-1..]);
// Compute costs (vectorized character comparison)
let costs = compute_costs_simd(&source_chars[i-1], &target_chars[j-1..j+7]);
// Parallel min operations
let deletion = prev + splat_u32x8(1);
let insertion = curr_left + splat_u32x8(1);
let substitution = diag + costs;
let result = min(min(deletion, insertion), substitution);
// Store 8 cells to curr_row
store_u32x8(&mut curr_row[j..], result);
}
Problem: Need to compare source[i] with 8 characters target[j..j+8]
Solution:
// Create vector of same character repeated 8 times
let src_char_vec = splat_u32x8(source[i] as u32);
let tgt_char_vec = load_u32x8(&target_chars[j..j+8]);
// Vectorized comparison
let matches = src_char_vec.simd_eq(tgt_char_vec);
// Convert bool mask to 0/1 costs
let costs = matches.select(splat_u32x8(0), splat_u32x8(1));
Problem: String length may not be multiple of 8
Solution: Process remainder with scalar code
// SIMD loop (multiple of 8)
for j in (1..n_simd).step_by(8) {
// ... SIMD code ...
}
// Scalar remainder (< 8 cells)
for j in n_simd..=n {
// ... scalar code ...
}
Problem: curr_row[j] depends on curr_row[j-1] (sequential dependency)
Solution: Use wavefront/anti-diagonal approach or accept limited parallelism
Recommendation: Use Approach 2 - Even with dependency, SIMD provides significant speedup for the other operations (deletion, substitution).
Tasks:
pulp dependency to Cargo.tomlsimd for optional SIMD supportDeliverable: Working SIMD prototype showing speedup potential
standard_distance() (Days 2-3)Tasks:
standard_distance_simd() functionCode structure:
#[cfg(feature = "simd")]
pub fn standard_distance(source: &str, target: &str) -> usize {
if source.len() < 16 || target.len() < 16 {
// Too small for SIMD benefit
return standard_distance_scalar(source, target);
}
pulp::Arch::new().dispatch(|| {
standard_distance_simd(source, target)
})
}
#[cfg(not(feature = "simd"))]
pub fn standard_distance(source: &str, target: &str) -> usize {
standard_distance_scalar(source, target)
}
Deliverable: Working SIMD implementation for standard distance
Tasks:
transposition_distance()merge_and_split_distance() (may be too complex for SIMD)Deliverable: SIMD support for all applicable distance functions
Tasks:
Success criteria:
Deliverable: Benchmarked, validated SIMD implementation
Tasks:
Deliverable: Complete documentation
Short (< 10 chars): 94-96ns
Medium (10-20): 374-492ns
Long (> 20): ~2-5µs
Short (< 10 chars): 94-96ns (no change, too small for SIMD)
Medium (10-20): 150-200ns (2-3x faster)
Long (> 20): ~500ns-1µs (3-5x faster)
Why 2-4x speedup?
For longer strings, better cache utilization may push this to 3-4x.
Risk: SIMD code is more complex and error-prone
Mitigation:
pulp API (not raw intrinsics)Risk: SIMD code is harder to maintain
Mitigation:
Risk: SIMD overhead may negate benefits for short strings
Mitigation:
std::archIf pulp doesn't provide sufficient performance, we can fall back to manual SIMD with std::arch:
Pros:
Cons:
Recommendation: Try pulp first. Only use std::arch if pulp doesn't meet performance targets.
| Phase | Duration | Deliverable |
|---|---|---|
| 3.1: Setup | 4-6 hours | Working prototype |
| 3.2: Implement standard_distance | 1-2 days | SIMD for standard distance |
| 3.3: Extend to other algorithms | 0.5-1 day | SIMD for all algorithms |
| 3.4: Testing & benchmarking | 1 day | Validated implementation |
| 3.5: Documentation | 0.5 day | Complete docs |
| Total | 3-5 days | Production-ready SIMD |
pulp is the best optionSIMD vectorization is feasible and should provide 2-4x speedup for medium/long strings. Using pulp provides a good balance of:
Recommendation: Proceed with pulp-based implementation.
Research Date: 2025-10-30 Status: Ready to implement Estimated effort: 3-5 days
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |