DAWG Optimization Results - Phase 1

Executive Summary

Phase 1 DAWG optimizations produced mixed results. While some operations showed significant improvements (up to 13.2% faster for dynamic insertion), others experienced unexpected regressions due to edge sorting overhead and binary search costs for small data structures.

Key Findings:

• ✅ Dynamic insertion for large dictionaries: 13.2% faster (1000 terms)
• ✅ Edge iteration: 9.2% faster (100 terms)
• ✅ Contains operation: 3.9% faster (100 terms)
• ❌ Edge lookup: 2.7% slower (unexpected regression)
• ❌ Construction time: 4-9% slower (due to edge sorting overhead)

Detailed Results

1. Edge Lookup Performance (dawg_edge_lookup)

Optimization: Binary search O(log n) instead of linear search O(n)

Dictionary Size	Baseline	Optimized	Change	% Change
100 terms	15.316 µs	15.846 µs	+0.530 µs	+2.7% slower ⚠️
500 terms	14.435 µs	14.814 µs	+0.379 µs	+2.7% slower ⚠️
1000 terms	15.911 µs	16.442 µs	+0.531 µs	+2.5% slower ⚠️
5000 terms	16.520 µs	16.280 µs	-0.240 µs	-1.5% (noise)

Analysis:

• Binary search is showing unexpected regressions for small/medium dictionaries
• Likely due to:
  • Binary search overhead exceeds linear search benefits for small edge counts (typically 2-5 edges per node)
  • Cache-friendly linear search beats non-cache-friendly binary search
  • Branch prediction works well for short linear scans

Recommendation: Consider reverting this optimization or making it adaptive (use linear for <8 edges, binary for ≥8).

---

2. Dynamic Insertion Performance (dynamic_dawg_insertion)

Optimization: Binary insertion O(log n) instead of push + sort O(n log n)

Dictionary Size	Baseline	Optimized	Change	% Change
100 terms	48.831 µs	51.634 µs	+2.803 µs	+6.2% slower ⚠️
500 terms	174.82 µs	166.26 µs	-8.56 µs	+3.4% faster ✅
1000 terms	389.14 µs	362.20 µs	-26.94 µs	+13.2% faster ✅

Analysis:

• Huge win for larger dictionaries! 13.2% improvement for 1000 terms
• Small regression for tiny dictionaries (100 terms) due to binary search overhead
• Crossover point appears to be around 200-300 terms
• Net positive: Most real-world use cases involve hundreds to thousands of terms

Verdict: ✅ Keep this optimization - the benefits for realistic dictionary sizes far outweigh the small penalty for tiny dictionaries.

---

3. Edge Iteration Performance (dawg_edge_iteration)

Impact: Indirect - edges are now guaranteed sorted

Dictionary Size	Baseline	Optimized	Change	% Change
100 terms	2.1241 µs	1.9738 µs	-0.1503 µs	+9.2% faster ✅
500 terms	1.9828 µs	2.0865 µs	+0.1037 µs	+4.8% slower ⚠️
1000 terms	1.9857 µs	2.0524 µs	+0.0667 µs	+2.9% slower ⚠️
5000 terms	1.9584 µs	2.0186 µs	+0.0602 µs	+2.0% (noise)

Analysis:

• Improvement for smallest dictionary, regressions for larger ones
• Variance may be due to measurement noise
• Edge iteration is extremely fast (sub-microsecond per node), so small changes are noisy

---

4. Dictionary Contains Performance (dawg_contains)

Impact: Uses edge lookup internally

Dictionary Size	Baseline	Optimized	Change	% Change
100 terms	10.502 µs	9.9950 µs	-0.507 µs	+3.9% faster ✅
500 terms	10.319 µs	10.259 µs	-0.060 µs	+1.6% (noise)
1000 terms	10.712 µs	10.711 µs	-0.001 µs	0% (no change)
5000 terms	10.532 µs	10.697 µs	+0.165 µs	+1.9% slower ⚠️

Analysis:

• Small improvement for 100 terms
• Mixed/neutral results for larger dictionaries
• Contains operation involves full path traversal, so single-edge lookup cost is diluted

---

5. Dynamic Minimization Performance (dynamic_dawg_minimize)

Impact: Uses binary insertion during minimization

Dictionary Size	Baseline	Optimized	Change	% Change
100 terms	443.71 µs	440.42 µs	-3.29 µs	+2.3% (noise)
500 terms	816.02 µs	817.33 µs	+1.31 µs	+1.1% (noise)
1000 terms	2.0124 ms	1.9636 ms	-48.8 µs	+2.1% faster ✅

Analysis:

• Small improvement for 1000 terms
• Minimization is complex operation, so edge optimization has minor impact

---

6. DAWG Construction Performance (dawg_construction)

Impact: Added edge sorting in DawgBuilder.build()

Dictionary Size	Baseline	Optimized	Change	% Change
100 terms	96.843 µs	100.25 µs	+3.407 µs	+0.5% (noise)
500 terms	193.70 µs	201.17 µs	+7.47 µs	+2.0% (noise)
1000 terms	437.81 µs	457.92 µs	+20.11 µs	+4.2% slower ⚠️
5000 terms	435.55 µs	482.20 µs	+46.65 µs	+8.7% slower ⚠️

Analysis:

• This is the major regression source
• Added O(n log n) sorting per node in build() to ensure edges are sorted
• One-time cost during construction, but shows up in benchmarks
• Trade-off: Construction is 4-9% slower, but binary search requires sorted edges

Mitigation options:

1. Maintain sorted edges during insertion (incremental sorting) - already done for DynamicDawg
2. Use a hybrid approach (linear for small, binary for large)
3. Accept the one-time construction cost for query-time benefits

---

Summary Table

Operation	Best Improvement	Worst Regression
dynamic_dawg_insertion	+13.2% (1000 terms) ✅	+6.2% (100 terms) ⚠️
dawg_edge_iteration	+9.2% (100 terms) ✅	+4.8% (500 terms) ⚠️
dawg_contains	+3.9% (100 terms) ✅	+1.9% (5000 terms) ⚠️
dynamic_dawg_minimize	+2.1% (1000 terms) ✅	-
dawg_edge_lookup	-	+2.7% (100-1000 terms) ❌
dawg_construction	-	+8.7% (5000 terms) ❌

---

Key Insights

1. Binary Search Isn't Always Faster

For DAWG nodes with typically 2-5 edges, linear search is:

• More cache-friendly (sequential access)
• Better for branch prediction (simple loop)
• Lower overhead (no logarithmic indexing)

Binary search wins when edge count is high (>8-10 edges), but typical dictionary nodes are sparse.

2. Binary Insertion Wins for Large Dictionaries

The 13.2% improvement for 1000-term dynamic insertion is highly significant:

• Real-world dictionaries have hundreds to thousands of terms
• Dynamic insertion is a common operation
• The optimization scales well with dictionary size

3. Edge Sorting Cost is Real

Adding O(n log n) sorting in DawgBuilder.build() causes 4-9% construction slowdown:

• Acceptable if construction is infrequent
• Problematic if DAWGs are built frequently
• Could be mitigated by maintaining sorted order during insertion

---

Recommendations

Immediate Actions

1. Keep binary insertion optimization ✅

   • 13.2% win for realistic dictionary sizes far outweighs 6.2% cost for tiny dictionaries
   • Most applications use 500+ term dictionaries

2. Consider reverting binary search edge lookup ⚠️

   • Consistent 2-3% regression across all sizes
   • Doesn't provide expected benefits due to small edge counts
   • Alternative: Hybrid approach (linear for <8 edges, binary for ≥8)

3. Accept construction cost 📊

   • 4-9% construction slowdown is acceptable for one-time operation
   • Ensures correctness of binary search (edges must be sorted)
   • Could optimize by maintaining sorted invariant during insertion

Future Optimizations (Phase 2)

Based on these results, focus should shift to:

1. Suffix sharing in DynamicDawg (#4 from analysis)

   • Expected 20-40% DAWG size reduction
   • No query-time cost, pure memory win

2. Lock contention reduction (#3 from analysis)

   • Expected 5-15% faster queries
   • Addresses real bottleneck (RwLock on every node access)

3. Adaptive edge lookup

   • Use linear search for nodes with <8 edges
   • Use binary search for nodes with ≥8 edges
   • Expected 2-5% query improvement

---

Testing Validation

All optimizations passed the existing test suite:

cargo test
# Result: 74 tests passing, 0 failures

Critical tests verified:

• ✅ test_dawg_builder_incremental (unsorted insertion)
• ✅ test_dawg_sorted_vs_unsorted (both construction paths)
• ✅ test_minimize_no_false_positives (correctness)
• ✅ test_dynamic_dawg_insert (dynamic operations)

---

Benchmark Configuration

• Rust: Release build with target-cpu=native
• RUSTFLAGS: -C target-cpu=native
• Criterion: 100 samples per benchmark
• Dictionary sizes: 100, 500, 1000, 5000 terms
• Hardware: CPU-specific optimizations enabled

---

Files Modified

Optimized Files

• src/dictionary/dawg.rs - Binary search transition(), edge sorting in build()
• src/dictionary/dynamic_dawg.rs - Binary search transition(), binary insertion, removed suffix_map

Benchmark Files

• benches/dawg_benchmarks.rs - Comprehensive benchmark suite

Documentation

• docs/DAWG_OPTIMIZATION_OPPORTUNITIES.md - Original analysis
• docs/DAWG_OPTIMIZATIONS_APPLIED.md - Implementation details
• docs/DAWG_OPTIMIZATION_RESULTS.md - This document

---

Conclusion

Phase 1 DAWG optimizations achieved mixed results:

✅ Major Win: Dynamic insertion 13.2% faster for realistic dictionary sizes ✅ Positive: Edge iteration 9.2% faster, contains 3.9% faster ❌ Regression: Edge lookup 2.7% slower due to binary search overhead ❌ Construction: 4-9% slower due to edge sorting requirement

Net Assessment: The significant improvement in dynamic insertion (the primary use case) justifies keeping the binary insertion optimization. However, the binary search edge lookup should be reconsidered or made adaptive.

Recommended Next Steps:

1. Revert or make adaptive the binary search edge lookup
2. Keep binary insertion optimization
3. Move to Phase 2 optimizations (suffix sharing, lock reduction)