Distance Calculation Optimizations

Overview

This document details the performance optimizations applied to Levenshtein distance implementations, including space optimization, SIMD acceleration, caching strategies, and early exit techniques.

These optimizations can provide 2-18× speedup depending on input characteristics.

These techniques build on the classic dynamic-programming formulation of Wagner & Fischer [3]; the early-termination strategies are instances of the bounded-distance cutoff analysed by Ukkonen [4], while the diagonal structure exploited by the SIMD path mirrors Myers' $\mathcal{O}(ND)$ difference algorithm [5].

Optimization Categories

1. Space Optimization (Row-Based DP)

2. Common Prefix/Suffix Stripping

3. SIMD Vectorization (AVX2/SSE4.1)

4. Memoization and Caching

5. Early Exit Techniques

6. SmallVec for Character Storage

---

1. Space Optimization (Row-Based DP)

Problem

Traditional DP stores full $m \times n$ matrix:

Memory: O(m×n) = 1000×1000 = 4 MB (for usize = 4 bytes)

Solution

Store only 2-3 rows instead of full matrix.

// Instead of:
let mut dp = vec![vec![0; n+1]; m+1];  // O(m×n)

// Use:
let mut prev_row = vec![0; n+1];  // O(n)
let mut curr_row = vec![0; n+1];  // O(n)
// Total: O(2n)

Implementation

pub fn standard_distance_impl(source: &str, target: &str) -> usize {
    // ...
    let mut prev_row = vec![0; n + 1];
    let mut curr_row = vec![0; n + 1];

    for (j, item) in prev_row.iter_mut().enumerate().take(n + 1) {
        *item = j;
    }

    for i in 1..=m {
        curr_row[0] = i;

        for j in 1..=n {
            // Compute curr_row[j] using prev_row
            curr_row[j] = (prev_row[j] + 1)
                .min(curr_row[j - 1] + 1)
                .min(prev_row[j - 1] + cost);
        }

        // Efficient swap: O(1) instead of O(n) copy
        std::mem::swap(&mut prev_row, &mut curr_row);
    }

    prev_row[n]
}

Source: src/distance/mod.rs:260-287

Results

String Size	Full Matrix	Two-Row	Savings
100×100	40 KB	800 bytes	50×
500×500	1 MB	4 KB	250×
1000×1000	4 MB	8 KB	500×

Impact: 50-500× memory reduction

---

2. Common Prefix/Suffix Stripping

Problem

Many real-world strings share common prefixes/suffixes:

• URLs: http://example.com/page1 vs http://example.com/page2
• File paths: /home/user/docs/file1.txt vs /home/user/docs/file2.txt
• Code identifiers: getUserName vs getUserId

Computing distance on full strings is wasteful.

Solution

Strip common prefix and suffix before recursion.

pub fn strip_common_affixes(a: &str, b: &str) -> (usize, usize, usize) {
    let a_chars: SmallVec<[char; 32]> = a.chars().collect();
    let b_chars: SmallVec<[char; 32]> = b.chars().collect();

    let len_a = a_chars.len();
    let len_b = b_chars.len();

    // Find common prefix
    let mut prefix_len = 0;
    let min_len = len_a.min(len_b);
    while prefix_len < min_len && a_chars[prefix_len] == b_chars[prefix_len] {
        prefix_len += 1;
    }

    if prefix_len == min_len {
        return (prefix_len, len_a - prefix_len, len_b - prefix_len);
    }

    // Find common suffix (don't overlap with prefix)
    let mut suffix_len = 0;
    while suffix_len < (min_len - prefix_len)
        && a_chars[len_a - 1 - suffix_len] == b_chars[len_b - 1 - suffix_len]
    {
        suffix_len += 1;
    }

    (
        prefix_len,
        len_a - prefix_len - suffix_len,
        len_b - prefix_len - suffix_len,
    )
}

Source: src/distance/mod.rs:111-147

Example

Input:
  a = "http://example.com/page1"  (26 chars)
  b = "http://example.com/page2"  (26 chars)

Strip:
  Prefix: "http://example.com/page"  (23 chars)
  Suffix: ""                         (0 chars)

Remaining:
  a' = "1"  (1 char)
  b' = "2"  (1 char)

Distance computation: O(1×1) = 1 operation
Without stripping:    O(26×26) = 676 operations

Speedup: 676×!

Results

Prefix Overlap	Speedup (Recursive)
0%	1.0× (no benefit)
25%	1.4×
50%	2.6×
75%	6.0×
90%	18.0×

Impact: 1.4-18× speedup depending on overlap

---

3. SIMD Vectorization

Problem

Scalar DP processes one cell at a time. Modern CPUs can process 4-8 values in parallel using SIMD instructions.

Solution

Vectorize DP operations using AVX2 (256-bit) or SSE4.1 (128-bit) intrinsics.

#[cfg(target_arch = "x86_64")]
pub fn standard_distance_simd(source: &str, target: &str) -> usize {
    // Short strings: SIMD overhead dominates, use scalar
    let source_len = source.chars().count();
    let target_len = target.chars().count();

    if source_len < 16 && target_len < 16 {
        return standard_distance_impl(source, target);
    }

    // Runtime CPU feature detection
    if is_x86_feature_detected!("avx2") {
        unsafe { standard_distance_avx2(source, target) }
    } else if is_x86_feature_detected!("sse4.1") {
        unsafe { standard_distance_sse41(source, target) }
    } else {
        standard_distance_impl(source, target)
    }
}

Source: src/distance/simd.rs:25-44

AVX2 Implementation (256-bit Vectors)

Process 8 u32 values (DP cells) in parallel:

#[target_feature(enable = "avx2")]
unsafe fn standard_distance_avx2(source: &str, target: &str) -> usize {
    // ... initialization ...

    let one_vec = _mm256_set1_epi32(1);  // Vector of eight 1s

    for i in 1..=m {
        curr_row[0] = i as u32;
        let source_char = source_chars[i - 1] as u32;

        let mut j = 1;
        while j + 8 <= n {
            // Load 8 target characters
            let target_vec = _mm256_loadu_si256(/* ... */);

            // Broadcast source character to all 8 lanes
            let source_vec = _mm256_set1_epi32(source_char);

            // Compare: source == target (vectorized)
            let eq_mask = _mm256_cmpeq_epi32(source_vec, target_vec);

            // Compute cost: 0 if equal, 1 if different
            let cost_vec = _mm256_andnot_si256(eq_mask, one_vec);

            // Load prev_row, curr_row values (8 at a time)
            let prev_vec = _mm256_loadu_si256(/* prev_row[j..j+8] */);
            let left_vec = _mm256_loadu_si256(/* curr_row[j-1..j+7] */);
            let diag_vec = _mm256_loadu_si256(/* prev_row[j-1..j+7] */);

            // Compute min(prev+1, left+1, diag+cost) vectorized
            let del_vec = _mm256_add_epi32(prev_vec, one_vec);
            let ins_vec = _mm256_add_epi32(left_vec, one_vec);
            let sub_vec = _mm256_add_epi32(diag_vec, cost_vec);

            let min1 = _mm256_min_epu32(del_vec, ins_vec);
            let result_vec = _mm256_min_epu32(min1, sub_vec);

            // Store 8 results
            _mm256_storeu_si256(/* curr_row[j..j+8] */, result_vec);

            j += 8;
        }

        // Handle remaining columns (< 8) with scalar code
        for j in j..=n {
            // Scalar computation
        }

        std::mem::swap(&mut prev_row, &mut curr_row);
    }

    prev_row[n] as usize
}

Source: src/distance/simd.rs:53-150 (simplified)

Runtime CPU Feature Detection

if is_x86_feature_detected!("avx2") {
    // Use AVX2 (8-wide vectors)
} else if is_x86_feature_detected!("sse4.1") {
    // Use SSE4.1 (4-wide vectors)
} else {
    // Fall back to scalar
}

Benefit: No compile-time CPU targeting required. Binary runs optimally on any CPU.

Results

String Length	Scalar (µs)	AVX2 (µs)	Speedup
10×10	0.8	1.2	0.67× (overhead)
50×50	18.5	8.3	2.23×
100×100	72.3	28.4	2.54×
500×500	1,820	512	3.55×

Impact: 2-4× speedup for long strings (>16 chars)

Threshold: SIMD disabled for strings <16 chars due to overhead.

---

4. Memoization and Caching

Symmetric Pair Deduplication

Exploit $d(a,b) = d(b,a)$:

struct SymmetricPair {
    first: Arc<str>,   // Lexicographically smaller
    second: Arc<str>,  // Lexicographically larger
}

impl SymmetricPair {
    fn new(a: &str, b: &str) -> Self {
        // Always order: first <= second
        if a <= b {
            Self { first: Arc::from(a), second: Arc::from(b) }
        } else {
            Self { first: Arc::from(b), second: Arc::from(a) }
        }
    }
}

Impact:

• ("test", "best") and ("best", "test") use same cache key
• 50% cache size reduction for bidirectional queries

Arc-Based String Storage

first: Arc<str>,
second: Arc<str>,

Benefits:

• Efficient cloning: $\mathcal{O}(1)$ reference count increment
• Shared memory: Multiple cache entries can reference same string
• Memory reduction: ~16 bytes per Arc vs full string copy

Thread-Safe Cache Implementations

DashMap (Lock-Free)

#[cfg(feature = "eviction-dashmap")]
pub struct MemoCache {
    cache: DashMap<SymmetricPair, usize>,
}

Pros: No locks, high concurrency throughput Cons: ~24 bytes overhead per entry

RwLock + FxHashMap (Fast Hash)

#[cfg(not(feature = "eviction-dashmap"))]
pub struct MemoCache {
    cache: RwLock<FxHashMap<SymmetricPair, usize>>,
}

Pros: Faster hash (FxHash), lower overhead (~16 bytes/entry) Cons: Read/write locks (still very fast for read-heavy workloads)

Cache Hit Performance

Scenario	Time	Speedup
Cold cache	72µs	1×
Warm cache (exact match)	150ns	480×
Symmetric query	150ns	480×

Impact: 100-500× speedup for cache hits

---

5. Early Exit Techniques

Early Exit on distance=0

Return immediately when remaining distance is 0:

if a == b {
    distance = standard_distance_recursive(s, t, cache);

    // If remaining distance is 0, total distance is 0
    if distance == 0 {
        cache.insert(cache_key, 0);
        return 0;  // Early exit!
    }
}

Example:

Input: "test" vs "test"
First chars match: 't' == 't'
Recurse: distance("est", "est")
  First chars match: 'e' == 'e'
  Recurse: distance("st", "st")
    First chars match: 's' == 's'
    Recurse: distance("t", "t")
      First chars match: 't' == 't'
      Recurse: distance("", "")
        → Return 0 (base case)
      ← Early exit: return 0
    ← Early exit: return 0
  ← Early exit: return 0
← Early exit: return 0

Impact: 2-3× speedup for identical or near-identical strings

Early Exit on first operation = 0

// Deletion
distance = standard_distance_recursive(s, &t_remaining, cache);
if distance == 0 {
    cache.insert(cache_key, 1);
    return 1;  // Early exit: 1 deletion + 0 remaining
}

Impact: Saves 2/3 of recursive calls when first operation succeeds

---

6. SmallVec for Character Storage

Problem

chars().collect() allocates on heap for every string, even short ones.

Solution

Use SmallVec<[char; 32]> for stack allocation of short strings:

use smallvec::SmallVec;

let source_chars: SmallVec<[char; 32]> = source.chars().collect();
let target_chars: SmallVec<[char; 32]> = target.chars().collect();

Behavior:

• Strings $\le 32$ chars: Stack allocation (zero-cost)
• Strings $> 32$ chars: Heap allocation (same as Vec)

Benefits

String Length	Vec (heap)	SmallVec (stack)	Speedup
5 chars	80ns	12ns	6.67×
10 chars	85ns	15ns	5.67×
20 chars	95ns	22ns	4.32×
50 chars	Heap	Heap	~1×

Impact: 4-7× faster for short strings (<32 chars)

---

Combined Optimization Impact

Example: URL Distance

a = "https://example.com/docs/guide/intro"
b = "https://example.com/docs/guide/overview"

Optimization	Time	Cumulative Speedup
Baseline (no opts)	1,200µs	1×
+ Space optimization	1,180µs	1.02×
+ SmallVec	980µs	1.22×
+ Prefix stripping	120µs	10.0×
+ Memoization (cache)	8µs	150×
+ Early exit	4µs	300×

Total speedup: 300×

---

Benchmarking Methodology

Test Environment

• CPU: Intel Core i7-9750H (2.6 GHz base, 4.5 GHz boost)
• RAM: 16 GB DDR4-2666
• OS: Linux 6.17.5-arch1-1
• Compiler: rustc 1.85.0-nightly
• Flags: -C target-cpu=native (enables AVX2)

Benchmark Tool

cargo bench --bench real_world_benchmark

Source: benches/real_world_benchmark.rs

Test Cases

1. Random strings: No common prefix, worst case
2. URL-like: 70% common prefix
3. Code identifiers: 50% common prefix
4. Identical strings: 100% overlap

---

Optimization Decision Tree

                ┌─────────────────────┐
                │ Distance Query      │
                └──────────┬──────────┘
                           │
         ┌─────────────────┼─────────────────┐
         │                 │                 │
    ┌────▼─────┐    ┌──────▼──────┐   ┌─────▼─────┐
    │ One-off  │    │  Repeated   │   │  Batch    │
    │ query    │    │  queries    │   │ processing│
    └────┬─────┘    └──────┬──────┘   └─────┬─────┘
         │                 │                 │
    ┌────▼────┐       ┌────▼────┐      ┌────▼─────┐
    │ Iterative│      │Recursive│      │Recursive +│
    │ DP       │      │+ memo   │      │ memo      │
    │          │      │         │      │ (shared)  │
    └────┬─────┘      └────┬────┘      └────┬──────┘
         │                 │                 │
    ┌────▼────┐       ┌────▼────┐      ┌────▼──────┐
    │ Space   │       │ Prefix  │      │ All opts  │
    │ opt     │       │ strip   │      │ enabled   │
    └────┬────┘       └────┬────┘      └────┬──────┘
         │                 │                 │
    ┌────▼────┐       ┌────▼────┐      ┌────▼──────┐
    │ SIMD    │       │ Early   │      │ Result    │
    │ (long   │       │ exit    │      │           │
    │  strs)  │       │         │      │           │
    └─────────┘       └─────────┘      └───────────┘

---

Related Documentation

• Iterative DP - Space-optimized algorithm
• Recursive Memoization - Caching strategy
• Layer 4 README - Distance calculation overview

References

1. Intel Intrinsics Guide: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/
2. SmallVec crate: https://docs.rs/smallvec/
3. Wagner, R. A., & Fischer, M. J. (1974). "The String-to-String Correction Problem". Journal of the ACM, 21(1), 168-173. DOI: 10.1145/321796.321811
4. Ukkonen, E. (1985). "Algorithms for approximate string matching". Information and Control, 64(1-3), 100-118. DOI: 10.1016/S0019-9958(85)80046-2
5. Myers, E. W. (1986). "An $\mathcal{O}(ND)$ Difference Algorithm and Its Variations". Algorithmica, 1(1-4), 251-266. DOI: 10.1007/BF01840446
6. Source code:
   • src/distance/mod.rs:111-147 (prefix stripping)
   • src/distance/simd.rs (SIMD implementations)
7. Benchmark data from benches/real_world_benchmark.rs