Liking cljdoc? Tell your friends :D

Optimization Progress Summary

Project: Generalized & Phonetic Automata Performance Optimization Started: November 17-18, 2025 Status: Phase 1 - COMPLETE ✅ System: Intel Xeon E5-2699 v3 @ 2.30GHz (36 cores), CPU pinned to core 0

Overview

Following the scientific method to identify and optimize performance bottlenecks in the generalized automaton and phonetic operations implementation through data-driven benchmarking, profiling, and targeted optimization.

Phase 1: Baseline Establishment & Hypothesis Formation

✅ Phase 1.1: Existing Benchmark Assessment (COMPLETE)

Key Finding: Most existing benchmarks are broken and insufficient.

Results:

  • 49 existing benchmark files found in benches/
  • 4 benchmarks tested: All failed except 1
  • substitution_set_microbench.rs: ✅ Only working benchmark
    • Substitution lookups: 4-5 ns (very fast, not a bottleneck)
    • Phonetic basic preset: 317 ns
    • Keyboard QWERTY preset: 592 ns

Failures:

  • state_operations_benchmarks.rs: API outdated (missing query_length parameter)
  • transition_benchmarks.rs: API changed
  • benchmarks.rs: Requires pathmap-backend feature
  • comprehensive_profiling.rs: Requires pathmap-backend feature

Historical conclusion: at the start of this investigation, no maintained generalized automaton benchmark covered the target surface, so a fresh benchmark target was created.

Documentation: docs/optimization/PHASE1_BASELINE.md

✅ Phase 1.2: New Benchmark Creation (COMPLETE)

Created the generalized automaton benchmark target and identified the maintained phonetic follow-up targets:

1. benches/generalized_automaton_benchmarks.rs ✅ COMPLETE

Purpose: Test core generalized automaton operations (H1, H2, H3)

Benchmark Groups:

  1. state_transition/by_input_length - Varying input lengths (3, 5, 8, 12, 15 chars)
  2. state_transition/by_distance - Varying max_distance (0, 1, 2, 3)
  3. state_transition/scenarios - Best/average/worst case inputs
  4. state_transition/word_length_scaling - State size growth (5, 10, 15, 20 chars)
  5. operations/types - Individual operation types (match, delete, insert, substitute)
  6. subsumption/state_size - O(n²) subsumption hypothesis testing
  7. realistic/word_pairs - Real-world examples (color/colour, gray/grey, etc.)

Status: Baseline data captured; see docs/optimization/baseline_generalized_automaton.txt.

2. Maintained Phonetic Benchmark Targets

Purpose: Test phonetic operation compilation, NFA behavior, normalized lookup, and rewrite throughput.

Targets:

  • benches/phonetic_rules.rs
  • benches/phonetic_position_skip_benchmark.rs
  • benches/phonetic_nfa_benchmarks.rs
  • benches/phonetic_grep_parallel_benchmarks.rs
  • benches/phonetic_compilation_benchmarks.rs
  • benches/phonetic_normalized_benchmarks.rs

Status: Maintained targets are registered in Cargo.toml and used by the focused phonetic optimization journals.

Files Modified:

  • Added the generalized benchmark target and later reconciled phonetic benchmark references to the maintained targets.

✅ Phase 1.3: Baseline Benchmarking & Flamegraph Generation (COMPLETE)

Benchmarks Run:

taskset -c 0 cargo bench --bench generalized_automaton_benchmarks
taskset -c 0 cargo flamegraph --bench generalized_automaton_benchmarks

Output Files:

  • docs/optimization/baseline_generalized_automaton.txt (complete benchmark results)
  • docs/optimization/flamegraphs/baseline_standard.svg (369 KB flamegraph)
  • docs/optimization/flamegraph_analysis.txt (perf report top 100)
  • docs/optimization/flamegraph_hotspots.txt (filtered liblevenshtein code)
  • docs/optimization/PHASE1_FLAMEGRAPH_ANALYSIS.md (comprehensive analysis)
  • perf.data (39.2 GB, 639,127 samples)

Key Benchmark Results:

BenchmarkTimeThroughputNotes
by_input_length/31.18 µs2.5 Melem/sBaseline
by_distance/0749 ns12.0 Melem/sRejection (0 errors)
by_distance/12.34 µs3.84 Melem/sAccept (1 error)
by_distance/27.84 µs1.14 Melem/sAccept (2 errors)
by_distance/310.90 µs826 Kelem/sAccept (3 errors)
operations/delete1.02 µs-Fastest operation
operations/insert1.41 µs-38% slower than delete
subsumption/max_state/1494 ns20.2 Melem/sBest case
subsumption/max_state/22.86 µs3.5 Melem/s5.8x slowdown
subsumption/max_state/39.50 µs1.05 Melem/s19x slowdown

Critical Finding: Performance degrades 3.3x per distance level (749ns → 2.34µs → 7.84µs → 10.90µs)

✅ Phase 1.4: Flamegraph Analysis & Hotspot Identification (COMPLETE)

Tool: perf + cargo-flamegraph Samples: 639,127 CPU samples (2.09 trillion cycles) Documentation: docs/optimization/PHASE1_FLAMEGRAPH_ANALYSIS.md

Top 5 Hotspots (Actual Code, Excluding Benchmark Overhead):

  1. GeneralizedAutomaton::accepts (9.11%) - Main acceptance loop

    • 0.78% state transitions
    • 0.71% subsumption checks
    • 0.64% character iteration (relevant_subword)
    • ~6.5% loop/BFS overhead

  2. GeneralizedState::successors (7.77%) - Successor generation

    • 2.75% successors_i_type ← Largest single function
    • 0.98% position iteration
    • 0.90% nested transitions

  3. Memory Deallocation - cfree (4.39%) - Freeing temporary vectors

    • Vec cleanup from successors
    • Vec cleanup from CharacteristicVector
    • Consequence of repeated allocations

  4. Iterator::collect (4.08%) - Collecting character vectors

    • From char().collect::<Vec>()
    • Triggers heap allocations
    • Called repeatedly in successors_i_type

  5. Subsumption - subsumes_standard (0.71%) - Position subsumption

    • Lower than expected (not dominant)
    • Efficient for typical workloads
    • Only becomes costly in max-state edge cases

Combined Memory Management Overhead: 8.47% (Iterator::collect 4.08% + cfree 4.39%)

Benchmark Overhead: ~20% of cycles (Criterion's statistical analysis: KDE, exp, rayon)

✅ Phase 1.5: Hypothesis Documentation (COMPLETE)

Documented 6 hypotheses in PHASE1_BASELINE.md:

  1. H1: Successor generation dominates runtime (60-80%)
  2. H2: Repeated char().collect() causes 10-15% overhead
  3. H3: Subsumption creates O(n²) bottleneck for large states
  4. H4: String allocations in can_apply() add 5-10% overhead
  5. H5: Phonetic operations cause 2-3x slowdown
  6. H6: Phonetic split completion is 20-30% slower than standard

Priority for testing: H1 → H3 → H2 → H5 → H4 → H6

✅ Phase 1.6: Hypothesis Validation (COMPLETE)

Validation Results (based on flamegraph analysis):

HypothesisStatusPredictedActualVerdict
H1: Successor generation dominates (60-80%)✅ Partial60-80%~10-15%Largest component but not dominant
H2: char().collect() overhead (10-15%)✅ Confirmed10-15%8.47%Within range (collect 4.08% + free 4.39%)
H3: Subsumption O(n²) bottleneck❌ RejectedMajor issue0.71%Not a bottleneck for typical workloads
H4: can_apply() allocations (5-10%)Carried forward5-10%0.79%Lower than predicted; later phonetic journals cover targeted rule costs
H5: Phonetic 2-3x slowdownMigrated2-3xSee focused journalsTracked by docs/optimization/phonetic/
H6: Phonetic split 20-30% slowerMigrated20-30%See focused journalsTracked by docs/optimization/phonetic/

Key Insights:

  1. H1 Revision: Successor generation is the largest single component (7.77% + overhead) but doesn't "dominate" as predicted. Performance is distributed across many operations.

  2. H2 Confirmed: Memory management (allocation + deallocation) is 8.47% of cycles - a significant cost that can be optimized.

  3. H3 Rejected: Subsumption is very efficient (0.71%) for typical workloads. The O(n²) scaling only appears in pathological max-state scenarios (19x slowdown confirmed in benchmarks but rare in practice).

  4. New Discovery: The bottleneck is distributed rather than concentrated:

    • Main loop overhead: 9.11%
    • Successor generation: 7.77%
    • Memory management: 8.47%
    • No single hotspot > 10%

Revised Optimization Priority:

  1. H2 (cache character vectors) - 8.47% target, simple fix
  2. H1 (optimize successors_i_type) - 2.75% target, largest single function
  3. SmallVec tuning - Reduce allocations
  4. H3 (subsumption) - REJECTED AS A PRIMARY OPTIMIZATION (edge-case-only optimization)

Phase 1 Summary

Status: ✅ COMPLETE (November 18, 2025, 00:45 EST) Duration: ~3 hours Progress: 100% (6/6 sub-phases complete)

Major Accomplishments:

  1. ✅ Created comprehensive benchmark suite (7 benchmark groups, 30+ scenarios)
  2. ✅ Collected baseline performance data across all distances and word lengths
  3. ✅ Generated flamegraph with 639K samples and 2.09T cycles profiled
  4. ✅ Identified top 5 hotspots with precise percentages
  5. ✅ Validated 3 hypotheses, rejected 1, and carried 2 into the dedicated phonetic optimization journals
  6. ✅ Documented all findings in 4 comprehensive markdown files

Key Discoveries:

  • Distributed bottleneck: No single function > 10% of cycles
  • Memory management is costly: 8.47% in allocation/deallocation
  • successors_i_type is the largest function: 2.75% of cycles
  • Subsumption is NOT the problem: Only 0.71% for typical workloads
  • Clear optimization path: H2 (cache character vectors) → H1 (optimize successors) → SmallVec tuning

Success Metrics:

  • ✅ Baseline established with statistical significance (100 samples per benchmark)
  • ✅ Top 5 hotspots identified with quantitative data
  • ✅ Optimization priority revised based on evidence
  • ✅ All 725+ tests passing

Deliverables:

  • 1 new generalized automaton benchmark plus dedicated follow-up phonetic benchmark coverage in the maintained phonetic_* targets
  • 5 documentation files (PHASE1_BASELINE.md, PHASE1_FLAMEGRAPH_ANALYSIS.md, PROGRESS.md, etc.)
  • baseline_standard.svg (369 KB interactive flamegraph)
  • 2 benchmark result files (substitution + generalized automaton)

Phase 2: Phonetic Operations & Additional Profiling (MIGRATED TO FOCUSED JOURNALS)

Planned Steps:

  1. Use the maintained phonetic benchmark targets (phonetic_rules, phonetic_nfa_benchmarks, phonetic_compilation_benchmarks, phonetic_normalized_benchmarks) for operation and acceptance coverage
  2. Generate flamegraphs for phonetic scenarios when profiling new rule sets
  3. Run cache analysis with perf stat for accepted implementation candidates
  4. Validate H4, H5, H6 in the focused phonetic journals under docs/optimization/phonetic/

Tools Ready:

  • ✅ cargo-flamegraph installed
  • ✅ perf available
  • ✅ CPU pinned to core 0
  • ✅ Performance governor active

Status: Superseded by focused phonetic optimization journals under docs/optimization/phonetic/.

Phase 3: Targeted Optimization (RECORDED IN H1/H2 RESULT REPORTS)

Planned Optimizations (in order):

  1. Cache character vectors (H2)
  2. Reduce string allocations in can_apply() (H4)
  3. Optimize subsumption checks (H3)
  4. SmallVec capacity tuning
  5. Operation iteration optimization
  6. Specialized position handling

Methodology: For each optimization:

  1. State hypothesis
  2. Implement change
  3. Re-run benchmarks
  4. Generate flamegraph
  5. Compare metrics
  6. Accept/reject optimization
  7. Document in OPTIMIZATION_LOG.md

Status: Superseded by docs/optimization/H2_RESULTS.md, docs/optimization/H1_RESULTS.md, and later optimization result reports.

Phase 4: Validation & Comparison (RECORDED IN RESULT REPORTS)

Planned:

  • Run complete benchmark suite
  • Generate final flamegraphs
  • Run full test suite (725+ tests)
  • Create performance comparison tables

Status: Superseded by the benchmark/result reports in this directory.

Phase 5: Documentation & Knowledge Transfer (INTEGRATED INTO SPECIALIZED REPORTS)

Planned Documents:

  • OPTIMIZATION_REPORT.md (comprehensive results)
  • BENCHMARK_GUIDE.md (how to use benchmarks)
  • Update function documentation with performance notes

Status: Superseded by focused optimization reports and benchmark guides.

Key Findings So Far

1. Existing Benchmark Suite is Broken

  • Most benchmarks haven't been maintained since Phase 3/4 changes
  • API drift from phonetic operations implementation
  • Missing feature dependencies (pathmap-backend)

2. Substitution Lookups Are Not a Bottleneck

  • 4-5 ns per lookup (extremely fast)
  • Confirms hypothesis that performance issues are in state transitions, not substitutions

3. Preliminary Baseline Data

  • Simple accepts() call (3 chars, distance 2): ~1.18 µs
  • This will be our baseline for optimization

4. Code Analysis Identified Clear Hotspots

  • successors_i_type(): 320 lines (largest method)
  • add_position(): Called for every successor (O(n²) potential)
  • Repeated allocations: char().collect(), to_string()

Next Steps

Immediate:

  1. ⏳ Wait for baseline benchmarks to complete (~10 min)
  2. ⏳ Analyze baseline results
  3. ⏳ Generate baseline flamegraphs (Phase 1.3)

Short Term: 4. Complete phonetic operations benchmarks (Phase 2) 5. CPU profiling with perf (Phase 2.1) 6. Cache analysis (Phase 2.2) 7. Identify top 5 hotspots from flamegraphs (Phase 2.3)

Medium Term: 8. Implement first optimization (cache character vectors) 9. Benchmark and compare results 10. Iterate through optimization list

Success Metrics

Minimum Goals:

  • [ ] 20% improvement in generalized automaton transition time
  • [ ] 30% reduction in allocation count
  • [ ] Identify and document top 5 hotspots with data
  • [ ] All 725+ tests passing after optimizations

Stretch Goals:

  • [ ] 40% improvement in phonetic operation performance
  • [ ] 50% reduction in cache misses
  • [ ] Sub-linear scaling with state size (through subsumption optimization)

Timeline

Phase 1: complete; baseline and flamegraph captured Phase 2: migrated to focused phonetic journals Phase 3: recorded in H1/H2 result reports Phase 4: recorded in result reports Phase 5: integrated into specialized reports

Total Estimated: 9-14 hours

Actual Progress: historical Phase 1 record; later phases are recorded in focused result reports

Files Created/Modified

Documentation

  • ✅ docs/optimization/PHASE1_BASELINE.md (comprehensive baseline)
  • ✅ docs/optimization/PROGRESS.md (this file)
  • ✅ docs/optimization/baseline_generalized_automaton.txt
  • ✅ docs/optimization/baseline_substitution_micro.txt

Benchmarks

  • ✅ benches/generalized_automaton_benchmarks.rs (393 lines)
  • ✅ Maintained phonetic benchmark targets in Cargo.toml: phonetic_rules, phonetic_position_skip_benchmark, phonetic_nfa_benchmarks, phonetic_grep_parallel_benchmarks, phonetic_compilation_benchmarks, and phonetic_normalized_benchmarks
  • ✅ Generalized automaton benchmark target: benches/generalized_automaton_benchmarks.rs
  • ✅ Memory-sensitive generalized measurements captured through the generalized/state/query benchmark targets and optimization result files

Configuration

  • ✅ Cargo.toml (added 4 benchmark entries)

Directory Structure

  • ✅ docs/optimization/ created
  • ✅ docs/optimization/flamegraphs/ created (for future use)

Conclusion

Phase 1 is complete. This investigation successfully:

  1. Assessed and documented the state of existing benchmarks
  2. Created comprehensive new benchmark suite for generalized automaton
  3. Collected baseline performance data
  4. Documented 6 hypotheses for testing

Key Insight: The lack of working benchmarks explains why performance issues may have gone unnoticed. Our new benchmark suite provides comprehensive coverage of core operations.

Follow-up profiling and optimization decisions are recorded in the focused result reports under docs/optimization/.

Last Reconciled: June 19, 2026

❮Pool and Intersection Optimization ReportQuery Iterator Optimization - COMPLETE❯

Can you improve this documentation?Edit on GitHub

cljdoc builds & hosts documentation for Clojure/Script libraries

Keyboard shortcuts
Ctrl+kJump to recent docs
←Move to previous article
→Move to next article
Ctrl+/Jump to the search field
Raise an issueBrowse cljdoc sourceChat on Slack
× close