BTreeSet vs SmallVec Comparison for Universal Transducers

Question

Would it be better to use the parameterized transducer's unsubsumption method (SmallVec with online subsumption) for Universal transducers instead of the current BTreeSet with error-based early termination?

Implementation Status

✅ Both approaches implemented and tested

Branch: master - BTreeSet with Error-Based Early Termination

Data Structure:

pub struct UniversalState<V: PositionVariant> {
    positions: BTreeSet<UniversalPosition<V>>,
    max_distance: u8,
}

Key Features:

• Custom Ord implementation sorts by (errors, offset)
• Early termination via take_while() based on error count
• Positions with errors ≤ new.errors skip subsumption check
• Positions with errors < new.errors checked via take_while()

add_position() Logic:

pub fn add_position(&mut self, pos: UniversalPosition<V>) {
    let pos_errors = pos.errors();

    // Step 1: Remove subsumed (with early termination)
    self.positions.retain(|p| {
        if p.errors() <= pos_errors {
            true  // Cannot be subsumed
        } else {
            !subsumes(&pos, p, self.max_distance)
        }
    });

    // Step 2: Check if subsumed (with early termination)
    let is_subsumed = self.positions.iter()
        .take_while(|p| p.errors() < pos_errors)  // Early exit!
        .any(|p| subsumes(p, &pos, self.max_distance));

    if !is_subsumed {
        self.positions.insert(pos);  // O(log n)
    }
}

Test Results: All 473 tests passing ✓

---

Branch: experiment/universal-smallvec - SmallVec with Online Subsumption

Data Structure:

pub struct UniversalState<V: PositionVariant> {
    positions: SmallVec<[UniversalPosition<V>; 8]>,
    max_distance: u8,
}

Key Features:

• Stack allocation for ≤8 positions
• Contiguous memory (excellent cache locality)
• Online subsumption (like parameterized transducers)
• Binary search + insert for sorted order

add_position() Logic:

pub fn add_position(&mut self, pos: UniversalPosition<V>) {
    // Check if subsumed by existing
    for existing in &self.positions {
        if subsumes(existing, &pos, self.max_distance) {
            return;  // Early exit if subsumed
        }
    }

    // Remove subsumed positions
    self.positions
        .retain(|p| !subsumes(&pos, p, self.max_distance));

    // Insert in sorted position
    let insert_pos = self.positions
        .binary_search(&pos)
        .unwrap_or_else(|pos| pos);
    self.positions.insert(insert_pos, pos);  // O(n)
}

Test Results: All 473 tests passing ✓

---

How to Run Benchmarks

Option 1: Using the benchmark harness

# Benchmark BTreeSet (master)
git checkout master
RUSTFLAGS="-C target-cpu=native" cargo bench --bench universal_state_comparison 2>&1 | tee /tmp/btreeset_results.txt

# Benchmark SmallVec (experiment)
git checkout experiment/universal-smallvec
RUSTFLAGS="-C target-cpu=native" cargo bench --bench universal_state_comparison 2>&1 | tee /tmp/smallvec_results.txt

# Return to master
git checkout master

# Compare results
diff /tmp/btreeset_results.txt /tmp/smallvec_results.txt

Option 2: Using the provided script

chmod +x scripts/benchmark_universal_approaches.sh
./scripts/benchmark_universal_approaches.sh

This will:

1. Benchmark master (BTreeSet)
2. Benchmark experiment (SmallVec)
3. Save results to /tmp/
4. Return to master branch

---

Expected Trade-offs

BTreeSet Advantages

1. Error-based early termination

   • take_while(|p| p.errors() < pos_errors) skips positions
   • Can skip large portions of the state when errors differ significantly
   • Optimal when error distribution is sparse

2. Automatic sorting maintenance

   • No manual insertion position calculation
   • Tree rebalancing ensures O(log n) operations

3. Better for varied state sizes

   • Consistent O(log n) performance regardless of size
   • No reallocation overhead for growth

SmallVec Advantages

1. Stack allocation (≤8 positions)

   • No heap allocations for typical states
   • Zero allocator overhead

2. Excellent cache locality

   • Contiguous memory layout
   • Better CPU cache utilization
   • Sequential memory access patterns

3. Simpler code

   • No custom Ord implementation needed
   • Standard Vec-like API
   • Easier to understand and maintain

4. Proven for parameterized

   • Already validated as 3.3x faster than batch approaches
   • 90% of parameterized states fit in 8 positions

Complexity Comparison

Operation	BTreeSet	SmallVec
add_position (best)	O(log n)	O(1) if subsumed immediately
add_position (avg)	O(k log n) where k << n	O(k*n) where k << n
add_position (worst)	O(n log n)	O(n²)
Memory (≤8 pos)	Heap	Stack
Memory (>8 pos)	Heap + tree nodes	Heap + Vec
Cache locality	Good (tree)	Excellent (contiguous)

---

Key Questions for Benchmark Analysis

When analyzing benchmark results, focus on:

1. State Size Distribution

• What percentage of states have ≤8 positions?
• How does performance change at the 8-position threshold?

2. Early Termination Effectiveness

• How often does BTreeSet's take_while() skip positions?
• Is the error distribution sparse enough for this to matter?

3. Insertion Overhead

• BTreeSet: O(log n) tree insertion
• SmallVec: O(n) element shifting
• Which dominates in practice?

4. Cache Effects

• Does SmallVec's contiguous memory offset the O(n) insertion cost?
• Are the states small enough that cache misses are rare?

5. Real-World Performance

• End-to-end query performance on actual dictionaries
• State construction time during automaton traversal

---

Prediction

Based on the analysis:

If Universal states are typically small (≤8 positions):

• SmallVec likely wins due to stack allocation and cache locality
• Similar to parameterized transducers (90% ≤8 positions)

If Universal states are larger or vary significantly:

• BTreeSet likely wins due to error-based early termination
• O(log n) operations scale better than O(n) shifts

The benchmark will empirically determine which assumption holds.

---

Implementation Details

Commits

• master (d80c0df): BTreeSet with comprehensive documentation
• experiment/universal-smallvec (435345a): SmallVec implementation
• Both have benchmark configuration in Cargo.toml

Files Modified

BTreeSet (master):

• src/transducer/universal/state.rs: BTreeSet + error-based early termination
• src/transducer/universal/position.rs: Custom Ord for (errors, offset) sorting
• All tests passing

SmallVec (experiment):

• src/transducer/universal/state.rs: SmallVec + online subsumption
• Same API surface, internal implementation change only
• All tests passing

Benchmark File

benches/universal_state_comparison.rs (present in master, to be created if needed):

• Compares state construction with varying position counts
• Tests both Standard and Transposition algorithms
• Measures throughput and latency

---

Next Steps

1. Run benchmarks on both branches
2. Analyze results focusing on the key questions above
3. Profile if benchmarks are inconclusive (flamegraphs, perf)
4. Measure real-world performance with actual dictionary queries
5. Document findings and make recommendation

---

References

• Parameterized subsumption analysis: docs/optimization/SUBSUMPTION_OPTIMIZATION_REPORT.md
• Java comparison: docs/research/universal-levenshtein/SUBSUMPTION_COMPARISON_JAVA_VS_RUST.md
• BTreeSet optimization: docs/research/universal-levenshtein/SUBSUMPTION_OPTIMIZATION.md
• Parameterized decision: docs/research/universal-levenshtein/PARAMETERIZED_SUBSUMPTION_DECISION.md

---

Conclusion

Both implementations are:

• ✅ Correct (all tests passing)
• ✅ Well-documented
• ✅ Ready for benchmarking

The benchmark comparison will provide empirical data to make the final decision.

Current Status: Awaiting benchmark execution and analysis.