Liking cljdoc? Tell your friends :D

UTF-8 Dictionary & Fuzzy Query Optimization Status

Date: 2025-11-04 Status: COMPREHENSIVE ANALYSIS COMPLETE Overall Assessment: ✅ Highly Optimized - Diminishing Returns

Executive Summary

The liblevenshtein-rust codebase has undergone extensive optimization work through multiple phases, achieving excellent performance for both byte-level and character-level (UTF-8) operations. The documented ~5-10% overhead for character-level dictionaries is inherent to Unicode scalar value processing and represents an acceptable trade-off for correctness.

Key Findings:

  • ✅ SIMD, arena allocation, state pooling all implemented
  • ✅ 20-64% SIMD performance gains achieved
  • ✅ Comprehensive benchmarking infrastructure (950+ lines of docs)
  • ⚠️ Limited further optimization potential (diminishing returns)
  • 🔴 One high-impact opportunity: Fix suffix sharing bug (20-40% memory)

The ~5-10% UTF-8 Overhead Explained

What It Represents

The overhead comes from character-level operations during dictionary traversal:

  1. UTF-8 Decoding: Converting bytes → Unicode scalar values (char)

    • Variable-length sequences (1-4 bytes per character)
    • Sequential dependencies (continuation byte validation)

  2. Storage Overhead: 4 bytes per char vs 1 byte per u8

    • Edge labels: SmallVec<[(char, usize); 4]> vs SmallVec<[(u8, usize); 4]>
    • 4x memory for edge labels

  3. NOT a SIMD Opportunity:

    • Variable-length sequences cannot be vectorized
    • Sequential dependencies prevent parallel processing
    • Already using LLVM-optimized std::str::chars() where possible

Why It's Acceptable

  • Correctness: Proper Unicode semantics (café → cafe = 1 edit, not 2)
  • Necessity: Required for multi-language applications
  • Relative Cost: 5-10% vs incorrect behavior = acceptable
  • Alternative: PathMapChar and DynamicDawgChar provide the capability where needed

Already Optimized ✅ (No Further Potential)

1. SIMD Distance Computation (Phase 3 Complete)

Location: src/distance/simd.rs Achievement: 20-64% performance gains

Implementation Details:

// Line 98-108: AVX2 vectorized comparison
let target_vec = _mm256_loadu_si256(target_buf.as_ptr() as *const __m256i);
let source_vec = _mm256_set1_epi32(source_char as i32);
let eq_mask = _mm256_cmpeq_epi32(source_vec, target_vec);
// Process 8 characters simultaneously

Performance:

  • Short strings (< 16 chars): Scalar (SIMD overhead not worth it)
  • Medium strings (16-64 chars): 20-35% faster
  • Large strings (64+ chars): 45-64% faster

Already Handles Unicode: Works on char arrays (u32 values)

2. Arena Allocation (OptimizedDawg)

Location: src/dictionary/dawg_optimized.rs Achievement: 20-25% faster construction, 30% smaller memory

Implementation:

  • All edges in contiguous memory
  • 8-byte nodes (edge_offset:u32 + edge_count:u8 + is_final:bool)
  • Sequential memory access = excellent cache locality

3. State Pooling

Achievement: 6-10% allocation reduction

Implementation:

  • StatePool for automaton state reuse
  • SmallVec<[Position; 8]> for typical states
  • Arc sharing for query strings

4. SmallVec Throughout

Locations: Throughout codebase

Benefits:

  • DynamicDawgChar: SmallVec<[(char, usize); 4]> - no heap for ≤4 edges
  • Query states: SmallVec<[Position; 8]> - typical state size
  • Avoids allocations for common cases (80-90% of nodes)

5. Adaptive Binary Search

Implementations:

DynamicDawgChar (dynamic_dawg_char.rs:1360-1370):

let child_idx = if self.edges.len() < 16 {
    // Linear search - cache-friendly for small counts
    self.edges.iter().find(|(c, _)| *c == label).map(|(_, idx)| *idx)
} else {
    // Binary search - efficient for large edge counts
    self.edges.binary_search_by_key(&label, |(c, _)| *c)
        .ok().map(|i| self.edges[i].1)
}?;

OptimizedDawg (dawg_optimized.rs:95-97):

  • Threshold: 4 edges (empirically tuned)

6. DoubleArrayTrie (Recommended Default)

Location: src/dictionary/double_array_trie.rs

Performance:

  • O(1) transition time (array lookup)
  • 3x faster queries than PathMap
  • 30x faster contains() checks
  • 8 bytes per state

Unicode Variant: DoubleArrayTrieChar available with same O(1) properties

7. Query Optimization (Phase 4 Complete)

Location: src/transducer/query.rs

Achievements:

  • Adaptive sorting for ordered results
  • Buffer pre-sizing
  • 0.7% faster for distance 1 queries
  • Up to 30% faster for distance 3+ queries
  • Lazy evaluation throughout

8. Bloom Filters

Location: src/dictionary/dynamic_dawg.rs:153-219

Achievement: 10x faster negative lookups

Implementation:

  • Probabilistic membership test
  • Avoids full DAWG traversal for non-members
  • Low false positive rate (configurable)

9. UTF-8 Decoding

Current Approach:

  • DoubleArrayTrieChar/DynamicDawgChar: Use std::str::chars() (LLVM-optimized)
  • PathMapChar: Manual decoding (necessary for byte-level storage)

Why Already Optimal:

  • Standard library uses LLVM optimizations
  • Manual decoding only where necessary (PathMapChar)
  • Sequential dependencies prevent vectorization

10. Cache Locality

Techniques Used:

  • Arena allocation (OptimizedDawg)
  • Sequential access patterns
  • SmallVec for inline storage
  • Double-array structure for contiguous memory

Optimization Opportunities 🎯

🔴 HIGH IMPACT (20-40% potential gains)

1. Fix DynamicDawgChar Suffix Sharing Bug ⚠️

Location: src/dictionary/dynamic_dawg_char.rs:829-867

Current Status: Implemented but DISABLED due to correctness bugs

Problem:

Inserting "j" into ["kb", "jb"] causes "k" to be marked as valid
Root cause: Shared suffix nodes incorrectly marked as final
When both 'j' and 'k' edges point to same node, marking it final affects both paths

Code Comments:

// Line 386-402: "Phase 2.1: Suffix sharing - DISABLED"
// "This optimization shares common suffixes but has bugs"

Potential Impact:

  • Memory: 20-40% reduction for natural language dictionaries
  • Correctness: CRITICAL - must not introduce invalid terms

Implementation Approach:

  1. Analyze suffix sharing semantics
  2. Determine if shared nodes can be final
  3. Possible solutions:
    • Reference counting for final states
    • Copy-on-write for shared suffixes
    • Different sharing strategy (prefix vs suffix)

Risk: HIGH - complex correctness issue, previous attempt failed

Effort: 3-5 days of careful debugging and comprehensive testing

Recommendation: Attempt if time permits, but ensure thorough testing

🟡 MEDIUM IMPACT (5-10% potential gains)

2. PathMapChar UTF-8 Decoder Batch Validation

Location: src/dictionary/pathmap_char.rs:374-491

Problem: Lock acquisition per continuation byte in hot path

Current Implementation (lines 414-454):

for seq_idx in 1..seq_len {
    let map_read = self.map.read().unwrap(); // ← LOCK PER BYTE!
    // ... validate continuation byte
}

Improvement:

  1. Collect all child bytes with single lock
  2. Batch validate UTF-8 sequences
  3. Build char->path mappings in one pass

Potential Impact:

  • Performance: 5-10% faster edge iteration
  • Lock contention: Reduced by 66-75% (1-4 bytes per char)

Risk: LOW - localized change, clear correctness criteria

Effort: 1-2 days

Recommendation: Good incremental improvement, low risk

3. SSE4.1 Fallback Implementation

Location: src/distance/simd.rs:38-44

Current Status: Completed - runtime dispatch now uses AVX2, then SSE4.1, then scalar fallback.

Current implementation:

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 {
    crate::distance::standard_distance_impl(source, target)
}

Implementation:

  • Port AVX2 logic to SSE4.1 (128-bit instead of 256-bit)
  • Process 4 characters at a time instead of 8
  • Same algorithm, different intrinsics

Potential Impact:

  • Performance: 1.5-2x speedup on CPUs without AVX2
  • Compatibility: Better performance on older hardware
  • Modern CPUs: No change (already using AVX2)

Risk: LOW - straightforward port, SSE4.1 well-documented

Effort: 2-3 days (implementation + testing)

Recommendation: Good for compatibility, low risk

🟢 LOW IMPACT (1-5% potential gains)

4. Investigate minimize() vs compact() Discrepancy

Historical Location: src/dictionary/dynamic_dawg_char.rs:1625

Current Status: Historical note. The referenced dynamic_dawg_char.rs path is no longer present in the current source tree, so this is not an active code marker.

Original note:

// Investigate why minimize() and compact() produce different node counts.

Issue: Two minimization methods yield different results

Potential Scenarios:

  1. Correctness issue: One method has subtle bug
  2. Different algorithms: Both correct, different trade-offs
  3. Memory savings: One more aggressive than other

Risk: MEDIUM - could reveal subtle bugs

Effort: 2-3 days of investigation

Recommendation: Investigate for correctness, potential memory savings

5. SIMD Batch Edge Lookup (Speculative)

Concept: Use AVX2 gather instructions for parallel lookups in DoubleArrayTrie

Challenge:

  • Irregular memory access patterns
  • Gather instructions have high latency
  • May not actually be faster due to cache misses

Potential Impact: 5-10% for nodes with many edges (IF it works)

Risk: HIGH - may not vectorize well, complex implementation

Effort: 5-7 days (experimentation + benchmarking)

Recommendation: LOW PRIORITY - uncertain payoff, high complexity

6. Optimize SIMD Short String Threshold

Location: src/distance/simd.rs:27-33

Current: SIMD disabled for strings < 16 characters

Improvement: Fine-tune threshold with micro-benchmarks

Potential Impact: 2-5% for 10-15 character queries

Effort: 1 day (benchmarking)

Recommendation: Low priority, minor gains

7. Add #[inline] Hints to Hot Paths

Locations: transition() and value access methods throughout

Potential Impact: 1-3% (compiler likely already inlines)

Effort: 0.5 days

Recommendation: Very low priority

What Has NO Further Potential ❌

1. Manual UTF-8 Decoding

Why: Sequential dependencies prevent SIMD

  • Variable-length sequences (1-4 bytes)
  • Continuation byte validation requires previous bytes
  • Branch on first-byte patterns

Already Optimal: stdlib chars() uses LLVM optimizations

2. SIMD for Dictionary Traversal

Why Not Vectorizable:

  • Sparse graph structure
  • Pointer chasing (each edge points to arbitrary node)
  • Conditional branches per node
  • Non-uniform work per edge

Current Approach: Already optimal (adaptive search, cache-friendly)

3. Batch Processing for Queries

Already Explored: docs/analysis/fuzzy-maps/04_PROFILING_ANALYSIS.md

Finding: Value-filtering does NOT prune search space

  • Still explores all children regardless of filter
  • Only saves string materialization
  • Slower than post-filtering except at >50% selectivity

Conclusion: No benefit from batch predicate evaluation

4. Further Cache Optimization

Already Excellent:

  • Arena allocation (contiguous memory)
  • SmallVec (inline storage)
  • Double-array structure
  • Sequential access patterns

Conclusion: No further optimization possible without changing algorithms

Performance Characteristics by Backend

DoubleArrayTrieChar

Overhead: ~10-15% slower than byte-level

Source:

  • 4x memory for char labels
  • chars() iterator during construction
  • O(1) transitions (no algorithmic difference)

Trade-off: Acceptable for correct Unicode semantics

DynamicDawgChar

Overhead: ~5-10% slower than byte-level

Source:

  • 4x memory for SmallVec<[(char, usize); 4]>
  • Adaptive search (same algorithm, larger labels)
  • Suffix sharing disabled (20-40% memory cost)

Optimizations Present:

  • Bloom filter for negative lookups
  • SmallVec to avoid heap allocation
  • Adaptive binary search (< 16 edges: linear, ≥ 16: binary)

PathMapChar

Overhead: ~10-15%

Source:

  • Manual UTF-8 decoding in hot path (lines 374-491)
  • Lock acquisition per continuation byte
  • Heap allocation per edges() call

Unique Approach:

  • Stores UTF-8 bytes internally
  • Decodes on-the-fly during traversal
  • Minimal storage overhead

Optimization Opportunity: Batch validation (see above)

Performance Benchmarks

UTF-8 vs Byte-Level Comparison (10,000 words)

Construction:
  DoubleArrayTrie:      3.2ms
  DoubleArrayTrieChar:  3.5ms (+9%)

Exact Match:
  DoubleArrayTrie:      6.6µs
  DoubleArrayTrieChar:  7.4µs (+12%)

Contains (100):
  DoubleArrayTrie:      0.22µs
  DoubleArrayTrieChar:  0.25µs (+14%)

Fuzzy Distance 1:
  DoubleArrayTrie:      12.9µs
  DoubleArrayTrieChar:  14.2µs (+10%)

Fuzzy Distance 2:
  DoubleArrayTrie:      16.3µs
  DoubleArrayTrieChar:  17.9µs (+10%)

Conclusion: ~10% overhead is consistent and acceptable

Risk Assessment

Low Risk, Good ROI ✅

  • SSE4.1 fallback (compatibility win, implemented)
  • PathMapChar batch validation (localized change, measurable gain)
  • Inline hints (trivial, compiler may already do it)

Medium Risk, High Potential ROI ⚠️

  • Fix suffix sharing bug (complex, 20-40% memory if successful)
  • Re-evaluate any remaining minimization/compaction discrepancies against the current dictionary backends before treating the historical DAWG note as active

High Risk, Uncertain ROI ⛔

  • SIMD batch lookups (may not vectorize, complex implementation)

Recommendations by Use Case

Priority: Correctness 🎯

  1. Fix suffix sharing bug in DynamicDawgChar
  2. Re-run minimization/compaction checks only for dictionary backends still present in src/dictionary
  3. Add comprehensive correctness tests
  4. Verify all edge cases for Unicode handling

Priority: Compatibility 🌐

  1. Maintain SSE4.1 fallback coverage
  2. Test on wider range of CPU architectures
  3. Add CPU feature detection warnings
  4. Document performance on different hardware

Priority: Performance ⚡

  1. PathMapChar batch validation (proven bottleneck)
  2. Fine-tune SIMD thresholds with production workloads
  3. Profile real-world usage patterns
  4. Only pursue if profiling shows specific bottlenecks

Priority: Stability 🛡️

  1. Document current optimization state (this document)
  2. Add performance regression tests
  3. Consider optimization "complete" (diminishing returns)
  4. Focus on correctness and API stability

Overall Recommendation

Current State: ✅ Highly Optimized

The codebase has undergone extensive, high-quality optimization work:

  • Multiple optimization phases completed (Phase 1-4 documented)
  • Comprehensive benchmarking infrastructure (950+ lines)
  • SIMD, arena allocation, state pooling all implemented
  • 168 tests passing, well-tested codebase

Focus: 🎯 Correctness & Completeness over Micro-optimization

Top 3 Priorities:

  1. ✅ Fix suffix sharing bug (if time permits - correctness + memory)
  2. ✅ Maintain SSE4.1 fallback tests and architecture coverage
  3. ✅ Document optimization status (this document)

Skip:

  • Micro-optimizations without proven bottlenecks
  • Speculative SIMD work (batch lookups)
  • Further UTF-8 decoding optimization (already optimal)

The Bottom Line

The ~5-10% UTF-8 overhead is acceptable and represents an inherent trade-off for Unicode correctness. Further optimization shows diminishing returns unless production profiling reveals specific bottlenecks.

Focus on:

  • Correctness (fix suffix sharing bug)
  • Completeness (keep AVX2/SSE4.1/scalar dispatch covered)
  • Stability (comprehensive testing)
  • Documentation (this analysis)

Avoid:

  • Premature optimization
  • Micro-optimizations with <1% gains
  • Complex changes with uncertain payoff

References

Optimization Documentation

  • docs/research/simd-optimization/phase3-results.md - SIMD achievements
  • docs/benchmarks/DAWG_OPTIMIZATION_ANALYSIS.md - Arena allocation
  • docs/benchmarks/DOUBLE_ARRAY_TRIE_ANALYSIS.md - DAT performance
  • docs/optimization/QUERY_OPTIMIZATION_COMPLETE.md - Query work
  • docs/analysis/fuzzy-maps/04_PROFILING_ANALYSIS.md - Value-filtering analysis

Implementation Files

  • src/distance/simd.rs - AVX2 vectorization
  • src/dictionary/dawg_optimized.rs - Arena allocation
  • src/dictionary/double_array_trie_char.rs - Unicode DAT
  • src/dictionary/dynamic_dawg_char.rs - Unicode dynamic DAWG
  • src/dictionary/pathmap_char.rs - PathMap with UTF-8 decoding
  • src/transducer/query.rs - Query iterator optimization

Last Updated: 2025-11-04 Next Review: After production profiling or when new optimization opportunities identified

❮Position Transition Function Optimization Reportflamegraph_analysis❯

Can you improve this documentation?Edit on GitHub

cljdoc builds & hosts documentation for Clojure/Script libraries

Keyboard shortcuts
Ctrl+kJump to recent docs
←Move to previous article
→Move to next article
Ctrl+/Jump to the search field
Raise an issueBrowse cljdoc sourceChat on Slack
× close