Profile-Guided Optimization (PGO) Impact Analysis

Summary

Conducted comprehensive benchmarking to measure the impact of Profile-Guided Optimization on liblevenshtein-rust. Results show mixed performance impact with improvements in some operations but regressions in others.

Overall Assessment: PGO provides modest improvements for targeted workloads (1-4% in key operations) but shows regressions in construction and minimization (2-6%). The profiling workload focused on dictionary lookup operations, which explains why those improved while construction suffered.

Methodology

Baseline Build (No PGO)

RUSTFLAGS="-C target-cpu=native" cargo build --release

• Build time: 15.36s
• No profile-guided optimizations

PGO Build

./pgo_build.sh

• Instrumented build: 34.40s
• Profiling run: 4.71s (queries) + 0.20s (contains)
• PGO-optimized build: 14.21s
• Total PGO workflow: ~53s

Profiling Workload

The profiling benchmark exercised:

• 10,000-word dictionary
• 5,000 fuzzy queries (edit distance 1-2)
• 1,000,000 contains() calls

Important: This workload emphasized lookup operations, which may not represent all use cases (e.g., construction-heavy workloads).

Benchmark Results

✅ PGO Improvements (Faster with PGO)

Benchmark	PGO Change	Baseline	PGO	Impact
dynamic_dawg_minimize/100	-4.24%	447.96 µs	427.97 µs	🔥 Significant
dawg_edge_iteration/500	-3.16%	2.0190 µs	1.9364 µs	✅ Good
dawg_contains/500	-2.88%	9.5380 µs	9.4045 µs	✅ Good
dawg_edge_lookup/500	-2.44%	14.053 µs	13.676 µs	✅ Good
dawg_contains/100	-1.26%	9.4230 µs	9.2983 µs	✅ Small
dawg_contains/1000	-1.16%	9.7632 µs	9.6097 µs	✅ Small
dawg_contains/5000	-1.09%	9.8161 µs	9.7103 µs	✅ Small

Best improvement: dynamic_dawg_minimize/100 at -4.24% Consistent wins: All dawg_contains benchmarks improved (1-3%)

❌ PGO Regressions (Slower with PGO)

Benchmark	PGO Change	Baseline	PGO	Impact
dawg_edge_iteration/100	+6.04%	2.0267 µs	2.1419 µs	⚠️ Regression
dawg_edge_lookup/5000	+5.10%	16.046 µs	16.451 µs	⚠️ Regression
dynamic_dawg_minimize/500	+4.65%	814.45 µs	833.35 µs	⚠️ Regression
dynamic_dawg_minimize/1000	+3.34%	1.9421 ms	2.0092 ms	⚠️ Regression
dawg_construction/100	+2.62%	95.761 µs	99.052 µs	⚠️ Small
dawg_edge_lookup/1000	+1.60%	15.995 µs	16.267 µs	📊 Noise

Biggest regression: dawg_edge_iteration/100 at +6.04% Pattern: Construction and minimization operations slower with PGO

📊 No Significant Change

Benchmark	PGO Change
dawg_edge_lookup/100	+0.77% (noise)
dynamic_dawg_insertion/*	0-1% (within noise)
dawg_edge_iteration/1000	-0.50% (noise)
dawg_edge_iteration/5000	-0.41% (noise)
dawg_construction/500	+1.43% (noise)
dawg_construction/1000	+1.24% (noise)
dawg_construction/5000	-0.58% (noise)

Analysis

Why PGO Helped

1. Dictionary Lookup Operations (+1-3%)

• The profiling workload performed 1M contains() calls
• PGO optimized the hot paths: edge lookup and node traversal
• Branch prediction improved based on actual usage patterns

2. Edge Iteration for 500-term dictionaries (+3.2%)

• Medium-sized dictionaries benefited from better code layout
• Cache locality improved for common traversal patterns

3. Minimization for small dictionaries (+4.2%)

• 100-term minimization improved significantly
• Suggests hot paths in minimization aligned with profiling data

Why PGO Hurt

1. Construction Operations (-1-3%)

• Profiling workload built DAWG only once
• Construction wasn't a hot path in profiling
• PGO may have de-prioritized construction code paths

2. Edge Iteration for small dictionaries (-6%)

• 100-term iteration regressed significantly
• PGO optimized for larger dictionary patterns (from profiling)
• Small-dictionary code paths may have been de-optimized

3. Minimization for medium/large dictionaries (-3-5%)

• Only 100-term minimization improved
• Larger minimizations weren't profiled enough
• Code layout may favor lookup over minimization

Key Insight: Profiling Workload Matters

The profiling benchmark emphasized:

• ✅ Lookups (1M calls) → PGO optimized these well
• ❌ Construction (1 call) → PGO de-prioritized this
• ❌ Minimization (limited) → Mixed results

Recommendation: For applications that heavily construct DAWGs, PGO may not help or could hurt performance.

PGO Value Proposition

When PGO Helps 🎯

• Lookup-heavy workloads (e.g., spell checkers, fuzzy search services)
• Medium-sized dictionaries (500-1000 terms)
• Long-running applications where 1-3% lookup improvement matters

When PGO Doesn't Help ❌

• Construction-heavy workloads (building many DAWGs)
• Small dictionaries (<100 terms) - mixed results
• Development/testing - 53s PGO build time adds friction

Verdict

PGO provides marginal value for liblevenshtein-rust:

• ✅ 1-4% improvement in lookup operations
• ❌ 2-6% regression in construction/minimization
• ⚠️ 53s build overhead vs 15s baseline

Recommendation:

• Use PGO for production deployments of lookup-heavy applications
• Skip PGO for general-purpose library builds
• Consider multiple profiling workloads if targeting diverse use cases

Better Optimization Targets

Based on profiling (flame graphs), Arc reference counting overhead (41% of execution time) is a much bigger optimization target than PGO's 1-3% gains.

Priority ranking:

1. Arc overhead reduction → 15-30% potential improvement
2. Adaptive edge lookup tuning → 5-10% potential improvement
3. PGO → 1-4% improvement (lookup-heavy workloads only)

Conclusion

PGO is working as designed but provides limited value for liblevenshtein-rust:

• Optimizes what was profiled (lookups: ✅)
• De-optimizes what wasn't profiled (construction: ❌)
• Net effect: Modest improvements for specific workloads

Next recommended optimization: Tackle the Arc overhead (41%) identified in flame graph analysis. This has 10x more potential than PGO's 1-3% gains.

Files

• benchmark_no_pgo.txt - Baseline benchmarks (no PGO)
• benchmark_with_pgo.txt - PGO-optimized benchmarks
• build_baseline_no_pgo.txt - Baseline build log
• pgo_build_log_v2.txt - PGO build log
• pgo_build.sh - Automated PGO workflow script