Phase 3: Optimization Results - can_apply_at() Helper

Date: 2025-11-18 23:45 Optimization: Added can_apply_at() helper to eliminate wasteful allocations in find_first_match()

Implementation Summary

Changes Made:

1. Added can_apply_at() helper function - checks rule applicability without allocating
2. Added can_apply_at_char() for character-level variant
3. Modified find_first_match() to use can_apply_at() instead of apply_rule_at().is_some()
4. Modified find_first_match_char() similarly

Lines Changed: ~50 lines added (helper functions + documentation) Test Results: ✅ All 87 tests passing (0 failures)

---

Performance Results

Before vs After Comparison

Input Size	Before (ns)	After (ns)	Speedup	% Improvement
5 phones	1,132	823	1.38×	27% faster
10 phones	2,677	1,880	1.42×	30% faster
20 phones	8,425	6,247	1.35×	26% faster
50 phones	42,997	31,346	1.37×	27% faster

Performance per Phone

Input Size	Before (ns/phone)	After (ns/phone)	Improvement
5 phones	226	165	27% faster
10 phones	268	188	30% faster
20 phones	421	312	26% faster
50 phones	860	627	27% faster

---

Analysis

Success: Consistent Speedup Across All Input Sizes

Positive Findings:

• ✅ Consistent 27-30% speedup across all input sizes
• ✅ No regressions for small inputs
• ✅ All tests passing (correctness maintained)
• ✅ Allocation overhead eliminated as designed

Measured Impact:

• Total speedup: 1.37× for 50-phone case (42,997 ns → 31,346 ns)
• Saved: 11,651 ns per operation (~27% reduction)

Unexpected: Degradation Pattern Persists

Degradation Analysis:

• Before optimization: 50 phones at 860 ns/phone vs 5 phones at 226 ns/phone = 3.80× degradation
• After optimization: 50 phones at 627 ns/phone vs 5 phones at 165 ns/phone = 3.80× degradation

Critical Finding: The superlinear scaling pattern remains unchanged!

Ratio Preserved:

Before: 860 / 226 = 3.80×
After:  627 / 165 = 3.80×

This indicates:

• ✅ Allocation overhead was real and removed (27% speedup achieved)
• ⚠️ Another source of degradation remains (still 3.80× superlinear)
• The optimization improved the constant factor but not the scaling characteristic

---

Hypothesis Re-evaluation

H1: Vec Reallocation Overhead ✅ PARTIALLY CONFIRMED

Evidence:

• Achieved 27-30% speedup by eliminating allocations in find_first_match()
• Consistent across all input sizes

Conclusion: Allocation overhead was ~27% of total time, not 284% as initially estimated

• Initial calculation overestimated allocation count (not all positions trigger allocations)
• Pattern matching fails early for most positions, reducing actual allocations

Remaining Degradation Source (NEW HYPOTHESIS H5)

H5: Iteration Count Increases with Input Size

Theory: Number of rule applications (iterations) increases superlinearly with input size

Evidence:

• 50-phone case still shows 3.80× degradation after allocation fix
• Larger inputs may require more transformation iterations to reach fixed point
• apply_rules_seq() complexity: O(iterations × rules × n)

Testable Prediction:

• Instrument code to count actual iteration count for each input size
• If iterations scale superlinearly, this explains the degradation

---

Further Investigation Required

Next Steps to Address Remaining Degradation

Option 1: Profile Iteration Counts

// Add instrumentation to apply_rules_seq()
let mut iteration_count = 0;
loop {
    iteration_count += 1;
    // ... rest of loop
}
println!("Input size: {}, iterations: {}", s.len(), iteration_count);

Expected Finding:

• 5 phones: ~2-3 iterations
• 50 phones: ~8-12 iterations (superlinear growth)

Option 2: Optimize Pattern Matching

• Current: O(pattern_len) per position check
• Potential: Precompute pattern start characters for quick rejection

Option 3: Early Termination Heuristics

• Skip positions where no rule can possibly match
• Use character-based lookahead to avoid unnecessary context checks

---

Performance Targets

Current State (After Optimization 1)

Metric	Value	Status
50-phone time	31,346 ns	✅ Improved
Degradation ratio	3.80×	⚠️ Unchanged
Per-phone (50)	627 ns	✅ Better than baseline

Target State (After Further Optimization)

Metric	Target	Required Improvement
50-phone time	~8,250 ns	3.80× further speedup
Degradation ratio	~1.0× (linear)	Eliminate superlinear growth
Per-phone (50)	~165 ns	Match 5-phone performance

Gap Analysis:

• Current speedup: 1.37× ✅
• Required additional speedup: 3.80× to achieve linear scaling
• Total target: 5.2× from original baseline (1.37× × 3.80×)

---

Optimization Decision

Recommendation: Investigate Iteration Counts

Data-Driven Next Step:

1. Add iteration count instrumentation
2. Run benchmarks to measure iterations vs input size
3. Determine if iterations scale superlinearly (confirm H5)
4. If confirmed, optimize iteration count (reduce rule applications)

Alternative: Accept 27% improvement and move forward

• Current performance is significantly better than baseline
• Further optimization may have diminishing returns
• Document as "good enough" for v0.8.0

---

Conclusion

Optimization Success ✅

Achieved:

• 27-30% speedup across all input sizes
• Eliminated allocation overhead in find_first_match()
• Maintained 100% test coverage (87/87 passing)
• No regressions for small inputs

Validated:

• H1 (Vec reallocation) was a real but ~27% overhead (not 284%)
• Code analysis correctly identified the allocation pattern
• Optimization was effective and safe

Further Work Identified ⚠️

Remaining Issue:

• 3.80× superlinear degradation persists
• Likely due to iteration count increase (H5)
• Requires additional investigation and optimization

Options:

1. Continue optimization: Target 3.80× further speedup to achieve linear scaling
2. Accept current state: 27% improvement is significant, move to v0.8.0
3. Hybrid approach: Document findings, defer further optimization to v0.9.0

---

Optimization 1 Complete: ✅ Performance Gain: 27-30% speedup Tests Passing: 87/87 ✅ Further Investigation Required: Yes (H5 - iteration count)