Date: 2025-10-30
Status: Research Complete - Decision Required
After prototyping with pulp and researching SIMD Levenshtein implementations, I've discovered that achieving significant SIMD speedups (20-30x) requires more sophisticated techniques than initially anticipated. This document presents the findings and recommendations.
Library: triple_accel
Performance: 20-30x speedup over scalar implementations
Techniques:
- AVX2 (256-bit) and SSE4.1 (128-bit) implementations
- Runtime CPU detection with automatic fallback
- Optimized for integer operations (not floats)
Based on research from Levenshtein Distance with SIMD, there are three main areas where SIMD helps:
- Compare 16-32 characters at once with AVX2
- Status: We already do this with
strip_common_affixes() - Impact: Major - eliminates unnecessary DP computation
- Fill DP row with initial values using SIMD
- Instead of:
for i in 0..n { row[i] = i; } - Use SIMD: Fill 8 usizes at once with AVX2
- Impact: Minor - only happens once per call
- Complexity: Low - straightforward vectorization
- Use SIMD min instructions instead of
a.min(b).min(c) - Eliminates branch prediction overhead
- Impact: Moderate - happens for every DP cell
- Complexity: Medium - requires proper SIMD types
- Process anti-diagonals of DP matrix in parallel
- Eliminates dependencies between cells
- Impact: High - true parallelism (8x potential)
- Complexity: Very High - complete algorithm restructuring
After prototyping, I discovered pulp is not ideal for our use case:
- Float-focused: Most operations optimized for f32/f64
- Limited integer support: Awkward API for u32/usize operations
- Abstraction overhead: Less control than raw intrinsics
- Documentation gaps: Integer SIMD operations poorly documented
- ✅ Safe, stable Rust
- ✅ Runtime CPU detection
- ✅ Cross-platform (x86, ARM)
- ✅ Great for float-heavy workloads
- Integer vector operations (u32/usize)
- Min operations on integer vectors
- Load/store for integer arrays
- Compare-and-select for character matching
What: Use raw x86 SIMD intrinsics directly
Example:
#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;
unsafe {
let a = _mm256_loadu_si256(ptr as *const __m256i);
let b = _mm256_loadu_si256(ptr2 as *const __m256i);
let min_result = _mm256_min_epu32(a, b);
}
Pros:
- ✅ Maximum performance (what triple_accel uses)
- ✅ Full control over every instruction
- ✅ No dependencies (built-in to std)
- ✅ Well-documented (Intel intrinsics guide)
- ✅ Proven approach (triple_accel: 20-30x speedup)
Cons:
- ⚠️ Requires unsafe code
- ⚠️ Platform-specific (separate AVX2, SSE, ARM implementations)
- ⚠️ Complex (manual alignment, pointer arithmetic)
- ⚠️ More error-prone
Recommendation: Best option for maximum performance
What: Learn from or integrate with triple_accel library
Pros:
- ✅ Proven performance (20-30x speedup)
- ✅ Already implemented Levenshtein + optimal string alignment (restricted Damerau)
- ✅ Runtime dispatch with fallbacks
- ✅ Open source (MIT license) - can study implementation
Cons:
- ⚠️ Dependency on external crate
- ⚠️ May not support merge-and-split distance
- ⚠️ Different API than our current interface
- ⚠️ Need to validate against our requirements
Recommendation: Study their implementation, possibly adopt patterns
What: Continue with pulp for simple optimizations only
Realistically achievable:
- Row initialization speedup (~1.1-1.2x)
- Cleaner runtime CPU detection
Performance expectation: 1.2-1.5x (not the 2-4x initially hoped)
Why so limited?:
- pulp's integer SIMD support is minimal
- Can't efficiently do the DP inner loop
- Most gains already captured in Phase 2
Recommendation: Not worth the complexity for limited gains
What: Ship current Phase 2 optimizations, tackle SIMD separately
Benefits:
- ✅ Immediate value (15-39% improvement from Phase 2)
- ✅ Production-tested (all tests passing)
- ✅ Low risk (safe Rust, backward compatible)
- ✅ More time to properly implement SIMD later
Timeline if proceeding with SIMD later:
- 1-2 days: Study triple_accel implementation
- 2-3 days: Implement AVX2 version with std::arch
- 1-2 days: Implement SSE4.1 fallback
- 1-2 days: Testing and validation
- Total: 5-9 days for proper SIMD implementation
Recommendation: Best pragmatic choice
| Approach | Performance | Complexity | Time | Risk | Recommendation |
|---|
| A. std::arch intrinsics | ⭐⭐⭐⭐⭐ (20-30x) | High | 5-9 days | Medium | ⭐⭐⭐⭐⭐ |
| B. triple_accel patterns | ⭐⭐⭐⭐⭐ (20-30x) | Medium | 3-5 days | Low | ⭐⭐⭐⭐ |
| C. Limited pulp | ⭐⭐ (1.2-1.5x) | Medium | 2-3 days | Medium | ⭐⭐ |
| D. Ship Phase 2 now | ⭐⭐⭐ (current) | Low | 0 days | Low | ⭐⭐⭐⭐⭐ |
// Standard DP recurrence
curr_row[j] = min3(
prev_row[j] + 1, // deletion
curr_row[j-1] + 1, // insertion ← depends on curr_row[j-1]!
prev_row[j-1] + cost // substitution
);
The insertion cost depends on curr_row[j-1], which must be computed first. This creates a sequential dependency that prevents naive vectorization.
Process cells along anti-diagonals, where all cells can be computed in parallel:
Matrix indices:
(0,0)
(0,1) (1,0)
(0,2) (1,1) (2,0)
(0,3) (1,2) (2,1) (3,0)
...
Cells on the same anti-diagonal have no dependencies and can be SIMD-parallelized.
Challenge: Complex indexing, memory access patterns, edge cases
Used by: triple_accel (likely)
Only vectorize operations that don't have dependencies:
- Deletion costs:
prev_row[j] + 1 ✅ Can vectorize - Substitution costs:
prev_row[j-1] + cost ✅ Can vectorize - Insertion costs:
curr_row[j-1] + 1 ❌ Keep scalar
Performance: ~2-3x speedup (not 20-30x)
Used by: Simpler SIMD implementations
Rationale:
- Phase 2 provides 15-39% improvement - significant and production-ready
- SIMD for Levenshtein is more complex than anticipated
- Proper SIMD needs 5-9 days of focused work
- Should use std::arch intrinsics (not pulp) for maximum performance
- Can implement SIMD as separate future effort
Action Items:
- ✅ Commit Phase 2 changes
- ✅ Tag release:
v0.3.1-phase2-optimizations - 📋 Create issue: "Phase 3: SIMD Optimization with std::arch"
- 📋 Document: Link to triple_accel as reference implementation
Approach:
- Study triple_accel source code for anti-diagonal approach
- Implement AVX2 version with
std::arch::x86_64 intrinsics - Add SSE4.1 fallback for older CPUs
- Feature flag: Make SIMD optional (
simd feature) - Benchmark thoroughly on multiple CPUs
Timeline: 5-9 days
Expected performance: 10-30x speedup (depending on string length)
- Analyze triple_accel implementation
- Understand anti-diagonal approach
- Design data structures for SIMD
- Plan memory layout
- Use
std::arch::x86_64 intrinsics - Implement anti-diagonal DP with
__m256i - Handle edge cases and alignment
- Runtime CPU detection
- 128-bit vectors for older CPUs
- Same algorithm, different vector width
- Test on systems without AVX2
- Property-based testing with proptest
- Benchmark on multiple CPUs
- Validate correctness
- Performance regression tests
- Document SIMD implementation
- Add usage examples
- Update benchmarks
- Write PHASE3_RESULTS.md
Total: 5-9 days for production-ready SIMD
- pulp is great for floats, not ideal for integer DP algorithms
- Levenshtein SIMD requires anti-diagonal processing for best performance
- triple_accel proves 20-30x is achievable with proper implementation
- std::arch intrinsics are the way to go for maximum performance
- SIMD for DP is a substantial undertaking, not a quick optimization
Recommendation: Ship Phase 2 now, implement SIMD later with std::arch
Phase 2 delivered solid, production-ready improvements (15-39% faster). SIMD optimization is worthwhile but requires:
- More sophisticated techniques (anti-diagonal processing)
- Raw SIMD intrinsics (std::arch, not pulp)
- Significant development time (5-9 days)
The pragmatic approach: Deploy Phase 2 gains immediately, tackle SIMD as a dedicated future effort with proper planning and reference implementations.
- Remove pulp dependency (optional, or keep for future use)
- Commit Phase 2 changes
- Create GitHub issue for SIMD implementation
- Document triple_accel as reference for future work
- Study triple_accel implementation in detail
- Start Phase 3.1: Design anti-diagonal approach
- Budget 5-9 days for complete implementation
- Use std::arch intrinsics, not pulp
Research Date: 2025-10-30
Status: Awaiting Decision
Recommendation: Ship Phase 2, implement SIMD later