Phase 4: SmallVec for State Positions Investigation

Executive Summary

Outcome: SmallVec optimization for State positions is NOT VIABLE ❌

After testing SmallVec sizes 4, 8, and 12, none provided universal performance improvements. The fundamental issue is that State size varies dramatically based on workload, making any fixed stack allocation size problematic.

Background

From Phase 3 profiling, State cloning was identified as the next bottleneck (21.73% of runtime). The initial hypothesis was that using SmallVec<[Position; N]> instead of Vec<Position> would reduce allocation overhead during State cloning.

Methodology

Tested three SmallVec sizes for State.positions:

• Size 4: Conservative, based on Phase 2 lessons about stack pressure
• Size 8: Moderate, hoping to cover most states
• Size 12: Aggressive, attempting to eliminate most heap allocations

Results Summary

SmallVec Size 4

Best Performance:

• Standard algorithm: -19.4% (excellent!)
• Insertions: -48.8% (excellent!)
• Deletions: -48.1% (excellent!)
• Worst case: -37.5%
• Mixed operations: -29.6%
• Query with distance: -20.8%

Worst Regressions:

• Distance 4: +27.3% (bad!)
• Small dict (100): +25.5% (bad!)
• Distance 3: +15.2% (bad!)
• Distance 1: +6.7%
• Query length benchmarks: +5-7%

SmallVec Size 8

Best Performance:

• Distance 4: -16.7% (better than size 4!)
• Transposition: -13.9%
• Distance 3: -8.4% (better than size 4!)
• Many results: -8.7%
• MergeAndSplit: -6.3%

Worst Regressions:

• Small dict (100): +9.1% (better than size 4)
• Query length 3: +7.3%
• Query length 7: +7.6%
• Insertions: +2.6% (much worse than size 4's -48%)
• Standard algorithm: +3.8% (much worse than size 4's -19%)

SmallVec Size 12

Almost Universal Regressions:

• Distance 4: +5.9%
• Distance 3: +6.3%
• Distance 2: +12.6%
• Small dict (100): +9.4%
• Large dict (5000): +8.4%
• Standard algorithm: +9.8%
• Transposition: +7.7%
• Insertions: +19.9%
• Deletions: +8.6%
• Query with distance: +10.2%

Only One Improvement:

• MergeAndSplit: -5.9%

Analysis

The Fundamental Problem

State size varies dramatically based on query characteristics:

Small States (Few Positions):

• Distance 0-1 queries
• Exact matches
• Short query terms
• Small dictionaries
• Benefit from: Small stack allocations (size 4)
• Hurt by: Large stack allocations (size 8-12)

Large States (Many Positions):

• Distance 3-4 queries
• Complex edit patterns
• Long query terms
• Dense trie structures
• Benefit from: Larger stack allocations (size 8)
• Hurt by: Small stack allocations (size 4)

Stack Pressure vs Heap Allocation Trade-off

Size 4: Minimal stack pressure, but frequent heap allocations for larger states

• Good: Operations with small states (insertions, deletions, Standard algorithm)
• Bad: High distance queries where states grow large

Size 8: Moderate stack pressure, covers more states

• Good: High distance queries (3-4) where states are larger
• Bad: Small state operations suffer from stack overhead

Size 12: Excessive stack pressure

• Bad: Almost everything - stack overhead dominates
• Even large-state workloads regress

Why No Size Works

The issue is workload variability:

• Small-state workloads need small inline size (or pure heap)
• Large-state workloads need large inline size
• Mixed workloads (most realistic scenarios) get the worst of both worlds

SmallVec's fixed size means we're always wrong for some portion of the workload.

Comparison to Phase 2

Phase 2 encountered similar issues with SmallVec<[Position; 8]> in transducer operations:

• Helped some workloads
• Hurt others
• No universal win

The lesson: SmallVec works when size is predictable; fails when size varies widely

Why the Profiling Prediction Failed

PROFILING_COMPARISON.md suggested:

"Option C: SmallVec for Positions

• Impact: Reduces allocation overhead (6.00%)
• Complexity: Low - just change type
• Risk: May have stack overhead (Phase 2 lesson!)"

The "Risk" warning was correct! We should have weighted the Phase 2 lessons more heavily.

Alternative Approaches Not Pursued

1. In-Place State Mutation (Option A from profiling doc)

Concept:

fn transition_state_mut(state: &mut State, ...) {
    epsilon_closure_mut(state, ...);
    // Reuse state's Vec allocation
}

Pros:

• Could eliminate 21.73% State cloning overhead entirely
• No stack pressure issues
• Deterministic benefit

Cons:

• Breaking API change
• Higher implementation complexity
• Would require refactoring transducer query logic

Verdict: Worth investigating if State cloning remains a bottleneck

2. Arc<Vec> for PathMapNode Paths (Option B)

Concept:

pub struct PathMapNode {
    map: Arc<RwLock<PathMap<()>>>,
    path: Arc<Vec<u8>>,  // Share paths, cheap clone
}

Target: 5.14% overhead from path cloning

Pros:

• Simple change
• No API impact
• Deterministic benefit

Cons:

• Extra indirection
• Reference counting overhead

Verdict: Lower priority but simpler win

3. Copy-on-Write (Cow) Pattern

Concept:

fn transition_state(state: Cow<State>, ...) -> Cow<State> {
    // Clone only when necessary
}

Pros:

• Reduces cloning in read-heavy paths

Cons:

• High complexity
• May not help if most paths mutate
• API ergonomics suffer

Verdict: Not recommended

Lessons Learned

1. Trust Phase 2 Lessons

When Phase 2 showed SmallVec had workload-dependent performance, we should have been more skeptical of using it again. The lesson transfers:

• SmallVec for transitions: Mixed results
• SmallVec for State: Mixed results
• Pattern: Size variability defeats SmallVec

2. Profiling Identifies What, Not How

Profiling said "State cloning is 21.73%" but didn't tell us:

• Why it's expensive (small frequent clones? large occasional clones?)
• When it happens (which workloads dominate?)
• What size states are typical

We jumped to SmallVec without understanding the distribution.

3. Benchmark Everything

The only way to discover the workload variability issue was to:

• Test multiple sizes
• Run comprehensive benchmarks
• Analyze the pattern of regressions

Micro-optimization assumptions fail in complex systems.

4. Revert Quickly

Once size 12 showed universal regressions, we reverted immediately. No sunk cost fallacy:

• Tested the hypothesis
• Gathered data
• Made evidence-based decision to revert
• Total time: ~1 hour to test and revert

Recommendations

Immediate: No Action Required

Current performance is already excellent from Phase 3:

• 15-50% improvements across all workloads
• Production-ready
• All tests passing

State cloning at 21.73% is acceptable given:

• No viable SmallVec solution
• Alternative solutions are complex
• Current performance meets goals

Future (If State Cloning Becomes Critical):

Priority 1: In-Place Mutation API

• Highest potential impact (eliminate 21.73% overhead)
• Well-understood implementation
• Clear trade-off: API complexity vs performance

Priority 2: Arc<Vec> for Paths

• Lower impact (5.14% overhead)
• Simple implementation
• No downside risk
• Quick win

Priority 3: Detailed State Size Profiling

• Instrument State size distribution by workload
• Identify if there's a "sweet spot" we missed
• Determine if bimodal (small + large) or continuous

Conclusion

SmallVec for State positions fails due to:

1. Workload variability - state size varies 2-12+ positions
2. Stack pressure - larger sizes hurt all small-state operations
3. No universal size - optimal size depends on workload

Final Decision: Revert to Vec<Position> and accept 21.73% State cloning overhead.

Current performance remains excellent. Further optimization requires different approaches (in-place mutation or path sharing).

---

Files Generated:

• benchmark_results_phase4_size4.txt - Size 4 benchmark results (deleted)
• benchmark_results_phase4_size8.txt - Size 8 benchmark results (deleted)
• benchmark_results_phase4_size12.txt - Size 12 benchmark results (deleted)
• PHASE4_SMALLVEC_INVESTIGATION.md - This document