In-Place State Mutation API - Detailed Analysis

Executive Summary

The in-place mutation API would eliminate the 21.73% State cloning overhead by reusing State allocations instead of cloning. This requires significant API changes and refactoring but provides deterministic performance gains.

Complexity: High Impact: High (21.73% overhead → 0%) Breaking Change: Yes Estimated Effort: 2-3 days implementation + testing

---

Current Architecture (Cloning-Based)

The Bottleneck (From Profiling)

State cloning: 21.73% of runtime

• State::clone: 7.60% (Vec allocation + copy)
• PathMapNode::clone: 6.70% (path Vec clones)
• Intersection creation: Remaining overhead

Current Code Flow

1. State Transition (src/transducer/transition.rs:203)

pub fn transition_state(
    state: &State,              // ← Borrowed
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
    algorithm: Algorithm,
) -> Option<State> {           // ← Returns new State
    let expanded_state = epsilon_closure(state, ...);  // ← CLONE #1

    let mut next_state = State::new();
    for position in expanded_state.positions() {
        // ... compute next positions ...
        next_state.insert(next_pos);
    }
    Some(next_state)            // ← Return new allocation
}

2. Epsilon Closure (src/transducer/transition.rs:193)

fn epsilon_closure(state: &State, ...) -> State {
    let mut result = state.clone();  // ← CLONE #2
    epsilon_closure_mut(&mut result, ...);
    result
}

3. Query Iterator (src/transducer/query.rs:83)

fn queue_children(&mut self, intersection: &Box<Intersection<N>>) {
    for (label, child_node) in intersection.node.edges() {
        if let Some(next_state) = transition_state(
            &intersection.state,     // ← Borrow current state
            label, query, max_distance, algorithm
        ) {
            // Create new Intersection with new State
            let child = Box::new(Intersection::with_parent(
                label,
                child_node,
                next_state,          // ← Move new State
                parent_box,
            ));
            self.queue.push(child);
        }
    }
}

Total Clones Per Edge:

1. epsilon_closure clones the input state
2. transition_state creates new state
3. Intersection::with_parent takes ownership

For a typical query with 100 state transitions → 200+ State clones

---

Proposed Architecture (In-Place Mutation)

Core Concept: State Reuse Pool

Instead of cloning States, reuse allocations from a pool.

API Changes Required

1. New State Pool Structure

// New: State allocation pool
pub struct StatePool {
    // Recycled states ready for reuse
    pool: Vec<State>,

    // Statistics
    allocations: usize,
    reuses: usize,
}

impl StatePool {
    pub fn new() -> Self {
        Self {
            pool: Vec::with_capacity(16), // Start with small pool
            allocations: 0,
            reuses: 0,
        }
    }

    /// Get a state (from pool or allocate new)
    pub fn acquire(&mut self) -> State {
        if let Some(mut state) = self.pool.pop() {
            state.clear();      // Clear positions but keep allocation
            self.reuses += 1;
            state
        } else {
            self.allocations += 1;
            State::new()
        }
    }

    /// Return a state to the pool for reuse
    pub fn release(&mut self, state: State) {
        if self.pool.len() < 32 {  // Cap pool size
            self.pool.push(state);
        }
    }
}

2. Modified Transition API

Before (current):

pub fn transition_state(
    state: &State,
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
    algorithm: Algorithm,
) -> Option<State>

After (in-place mutation):

pub fn transition_state_pooled(
    state: &State,                    // Input (still borrowed)
    pool: &mut StatePool,             // ← NEW: Pool for allocations
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
    algorithm: Algorithm,
) -> Option<State>                    // Returns pooled state

Implementation:

pub fn transition_state_pooled(
    state: &State,
    pool: &mut StatePool,
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
    algorithm: Algorithm,
) -> Option<State> {
    let window_size = max_distance + 1;
    let query_length = query.len();

    // Get a state from pool (reuses allocation!)
    let mut expanded_state = pool.acquire();

    // In-place epsilon closure (no clone!)
    epsilon_closure_into(state, &mut expanded_state, query_length, max_distance);

    // Get another state from pool
    let mut next_state = pool.acquire();

    let mut cv_buffer = [false; 8];
    for position in expanded_state.positions() {
        let offset = position.term_index;
        let cv = characteristic_vector(dict_char, query, window_size, offset, &mut cv_buffer);
        let next_positions = transition_position(position, cv, query_length, max_distance, algorithm);

        for next_pos in next_positions {
            next_state.insert(next_pos);
        }
    }

    // Return expanded_state to pool (no longer needed)
    pool.release(expanded_state);

    if next_state.is_empty() {
        pool.release(next_state);
        None
    } else {
        Some(next_state)
    }
}

3. New Epsilon Closure Helper

/// Compute epsilon closure into a target state (no allocation)
fn epsilon_closure_into(
    source: &State,
    target: &mut State,
    query_length: usize,
    max_distance: usize,
) {
    // Copy positions from source to target
    for pos in source.positions() {
        target.insert(pos.clone());  // Position is small (Copy?)
    }

    // Apply epsilon closure in-place
    epsilon_closure_mut(target, query_length, max_distance);
}

4. State API Extensions

impl State {
    /// Clear all positions (keeps allocation)
    pub fn clear(&mut self) {
        self.positions.clear();  // Vec::clear keeps capacity
    }

    /// Copy positions from another state
    pub fn copy_from(&mut self, other: &State) {
        self.positions.clear();
        for pos in other.positions() {
            self.positions.push(pos.clone());
        }
    }
}

5. Query Iterator Integration

Current:

fn queue_children(&mut self, intersection: &Box<Intersection<N>>) {
    for (label, child_node) in intersection.node.edges() {
        if let Some(next_state) = transition_state(
            &intersection.state,
            label, &self.query, self.max_distance, self.algorithm
        ) {
            let child = Box::new(Intersection::with_parent(
                label, child_node, next_state, parent_box
            ));
            self.queue.push(child);
        }
    }
}

Modified:

// Add pool to CandidateIterator
pub struct CandidateIterator<'a, D, N>
where
    D: Dictionary<Node = N>,
    N: DictionaryNode,
{
    // ... existing fields ...
    state_pool: StatePool,  // ← NEW
}

fn queue_children(&mut self, intersection: &Box<Intersection<N>>) {
    for (label, child_node) in intersection.node.edges() {
        if let Some(next_state) = transition_state_pooled(
            &intersection.state,
            &mut self.state_pool,  // ← Pass pool
            label, &self.query, self.max_distance, self.algorithm
        ) {
            // ... rest same ...
        }
    }

    // When intersection is done, return its state to pool
    // (requires additional lifecycle management)
}

---

Implementation Challenges

1. State Lifecycle Management

Problem: When can we return a State to the pool?

Currently, Intersection owns its State:

pub struct Intersection<N: DictionaryNode> {
    pub state: State,  // Owned
    // ...
}

Solution A: Reference Counting

pub struct Intersection<N: DictionaryNode> {
    pub state: Rc<State>,  // Shared ownership
    // ...
}

• States are returned to pool when Rc drops to 0
• Adds runtime overhead for reference counting
• Complicates API (no longer plain State)

Solution B: Explicit Lifecycle

impl Drop for Intersection<N> {
    fn drop(&mut self) {
        // Problem: Can't access pool from here!
        // Would need global pool or different approach
    }
}

• Difficult to implement correctly
• Requires global state or complex passing

Solution C: Pool Per Query (Recommended)

• Create StatePool when query starts
• Pool lives for entire query duration
• States are reused across traversal
• Pool destroyed when query completes
• No complex lifetime management needed!

2. Breaking API Changes

Public API Changes:

// Old (current)
pub fn transition_state(
    state: &State,
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
    algorithm: Algorithm,
) -> Option<State>

// New (with pool)
pub fn transition_state_pooled(
    state: &State,
    pool: &mut StatePool,  // ← NEW PARAMETER
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
    algorithm: Algorithm,
) -> Option<State>

Migration Strategy:

1. Keep old transition_state as deprecated wrapper
2. Add new transition_state_pooled
3. Migrate internal usage to pooled version
4. Eventually remove old version in breaking release

3. Position Cloning

Even with State pooling, we still clone Position objects:

for pos in source.positions() {
    target.insert(pos.clone());  // ← Still cloning
}

Optimization: Make Position Copy

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Position {
    pub term_index: usize,    // 8 bytes
    pub num_errors: usize,    // 8 bytes
    pub is_special: bool,     // 1 byte
}                             // Total: ~17 bytes → good for Copy

If Position is Copy, then:

target.insert(*pos);  // Bitwise copy, no allocation

---

Expected Performance Impact

Profiling Data Breakdown

State::clone: 21.73% total

• Vec allocation: 6.00%
• Position copies: 7.44%
• PathMapNode clones: 6.70%
• Misc overhead: 1.59%

Optimizations Achieved

1. Eliminate Vec Allocations (6.00%)

• Pool reuses existing Vec allocations
• Vec::clear() keeps capacity
• Zero allocation cost for pooled states

2. Reduce Position Copies (7.44% → ~2%)

• Making Position Copy reduces overhead
• Still need to copy data, but no allocation
• Estimated 5.44% savings

3. Orthogonal to PathMapNode (6.70%)

• Path cloning still happens
• Could combine with Arc<Vec> optimization
• Total potential: 21.73% - 6.70% = 15% improvement

Conservative Estimate

Realistic improvement: 10-15% overall performance gain

• Best case (small states): 15%
• Worst case (large states, less reuse): 10%
• No workload should regress

---

Implementation Plan

Phase 1: Foundation (Day 1)

1. ✅ Create StatePool structure
2. ✅ Implement acquire() and release()
3. ✅ Make Position Copy (if possible)
4. ✅ Add State::clear() and helpers
5. ✅ Write unit tests for pool

Phase 2: Integration (Day 2)

1. ✅ Add transition_state_pooled()
2. ✅ Implement epsilon_closure_into()
3. ✅ Integrate pool into CandidateIterator
4. ✅ Update queue_children() to use pool
5. ✅ Add pool statistics/debugging

Phase 3: Testing & Benchmarking (Day 3)

1. ✅ Run full test suite
2. ✅ Benchmark against baseline
3. ✅ Profile to verify State::clone reduction
4. ✅ Measure pool efficiency (reuse rate)
5. ✅ Test edge cases (empty pools, large queries)

Phase 4: Cleanup (If Successful)

1. ✅ Update documentation
2. ✅ Deprecate old transition_state
3. ✅ Migration guide for users
4. ✅ Consider making pooled version default

---

Risks & Mitigation

Risk 1: Pool Overhead

Risk: StatePool management adds overhead

Mitigation:

• Inline critical pool operations
• Use Vec for O(1) push/pop
• Benchmark pool overhead in isolation
• If overhead > savings, abort

Risk 2: Memory Bloat

Risk: Pool grows indefinitely

Mitigation:

• Cap pool size (e.g., 32 states max)
• Release excess states
• Monitor pool size in benchmarks

Risk 3: Complexity

Risk: Code becomes harder to maintain

Mitigation:

• Thorough documentation
• Clear separation of pooled vs non-pooled APIs
• Comprehensive tests
• Consider reverting if complexity > benefit

Risk 4: Thread Safety

Risk: StatePool is not thread-safe

Current State: Queries are single-threaded Mitigation:

• Document pool is per-query
• If parallel queries needed: thread-local pools
• Or use lock-free pool structure

---

Comparison to Alternatives

Approach	Complexity	Impact	Breaking	Risk
In-Place Mutation	High	10-15%	Yes	Medium
SmallVec (Phase 4)	Low	Mixed	No	Proven failed
Arc<Vec> paths	Low	5%	No	Low
Copy-on-Write	Very High	Unknown	Yes	High

Verdict: In-place mutation is the highest-impact option remaining, but requires significant work.

---

Recommendation

Proceed If:

1. Current 15-50% improvement is insufficient
2. Willing to introduce breaking API change
3. Have 3+ days for implementation/testing
4. Can revert if benchmarks don't show gains

Skip If:

1. Current performance meets requirements ✅ (This is the case!)
2. API stability is critical
3. Risk tolerance is low
4. Alternative (Arc<Vec>) provides enough gain

My Recommendation: Not Worth It (Yet)

Reasons:

1. ✅ Current performance is excellent (15-50% gains from Phase 3)
2. ✅ Production-ready with no regressions
3. ⚠️ High complexity for 10-15% further improvement
4. ⚠️ Breaking API change requires major version bump
5. ⚠️ Diminishing returns - already optimized major bottleneck

Alternative: Try Arc<Vec<u8>> for paths first (5% gain, no API break, low risk)

---

Conclusion

The in-place mutation API is technically feasible and would provide 10-15% performance improvement by eliminating State cloning overhead. However, it requires:

• Significant API refactoring
• Breaking changes to public interfaces
• 2-3 days implementation effort
• Careful lifecycle management

Given current performance is already excellent, this optimization should only be pursued if:

• Performance requirements increase
• Breaking API changes are acceptable
• Simpler optimizations (Arc paths) have been exhausted

Status: Design complete, awaiting decision to implement.