Benchmarks and Performance Analysis

Performance benchmarks, measurements, and comparative analysis.

Contents

Cross-Language Benchmark Program

Measured comparisons between the Rust-backed language bindings and the legacy implementations they replace, plus a binding-overhead atlas against the pure Rust core. All arms run one normative protocol over one committed workload and must pass a correctness gate against a Rust oracle before any timing is accepted.

Results

Every measurement taken, with an explicit accounting of what was not measured and which figures are provisional. Start here.

Methodology

Strategy, procedure, integrity constraints, and how each is validated — including the procedure for re-measuring after a code change. Read before running or extending the program.

Java vs Java

Legacy liblevenshtein-java 3.0.0 against the Java 22 FFM binding, calibrated against a third implementation so the result is not misread.

C++ vs C++

Legacy liblevenshtein-cpp against the Rust-backed C++ facade, with the core / ABI / facade cost decomposition.

The normative harness contract (CLI surface, timed loop, checksum bit-layout, per-language clocks, fairness rules) lives separately in benchmarks/cross-language/harnesses/common/PROTOCOL.md.

Collection traversal and host-language protocols

The dictionary producer's collection traversal and binding protocol isolates owned Rust iteration, an allocation-reusing visitor, complete host materialization, bounded ABI batches, and early cancellation. The same-binary paired runner and deterministic analyzer live here because they reuse this repository's topology-aware admission and statistical contract:

• run-collection-traversal-experiment.sh
• prepare-collection-traversal-resume.py
• analyze-collection-traversal.py
• collection-traversal-sample.schema.json
• host-collection-traversal-sample.schema.json

Per-language package drivers emit the same checksum/work schema but time only their native collection view or closeable stream. Startup, construction, JIT warmup, and profiler instrumentation remain outside the admitted interval.

Backend Comparisons

Backend Performance Comparison

Comprehensive comparison of the dictionary backends:

• PathMap
• Dynamic DAWG (DynamicDawg — the current directed-acyclic-word-graph backend)
• Suffix Automaton
• Double Array Trie

Historical note. Earlier revisions of the linked report also benchmarked the classic static DawgDictionary and the arena-optimized OptimizedDawg. Both were removed in the 0.9.x line (backends extracted to libdictenstein); their roles are now covered by DynamicDawg and DoubleArrayTrie. Any such rows in the report are retained only as a historical baseline.

Final Backend Comparison

Final comprehensive backend benchmark results:

• Performance metrics for all operations
• Memory usage analysis
• Recommendations for backend selection

Backend Comparison Results

Detailed benchmark data and analysis:

• Construction time
• Query performance
• Memory footprint
• Use case recommendations

Double Array Trie (DAT) Analysis

DAT Optimization Results

Results from Double Array Trie optimization work:

• Optimization techniques applied
• Performance improvements measured
• Comparison with other backends

DAT Performance Analysis

In-depth performance analysis of Double Array Trie:

• Bottleneck identification
• Memory access patterns
• Cache efficiency

Double Array Trie Analysis

Comprehensive analysis of DAT implementation:

• Algorithm explanation
• Implementation details
• Performance characteristics

Algorithm-Specific Analysis

Optimization and Profiling Methodology

The end-to-end hypothesis, correctness, host-admission, statistical, headless-profiler, visualization, acceptance, and propagation contract for the Java-parity optimization campaign.

Java Performance-Parity Causal Analysis

Profile- and work-counter-backed explanation of the construction, native matching, and resource-boundary gaps against liblevenshtein-java, plus the ranked hypotheses that gate the optimization campaign.

Optimization Propagation Matrix

Backend-by-backend and query-surface-by-query-surface classification of every accepted parity optimization, including the generic invariant, specialized adaptations, explicit inapplicability reasons, and completion gates.

Academic Benchmark Reproduction

Repeatable commands for the UCR/UEA MSM archive benchmark and the CMUdict phonetic homophone benchmark:

• Scripted corpus preparation and cleanup
• Memory-capped execution with systemd-run
• Cargo aliases for already-prepared corpora
• Result artifact locations for repository scientific-ledger records

DAWG Optimization Analysis

Analysis of DAWG optimization techniques:

• Minimization algorithm
• Memory efficiency improvements
• Query performance optimization

Optimization Results

Overall optimization results across all components:

• Performance improvements by category
• Before/after comparisons
• Future optimization opportunities

Optimization Summary

High-level summary of optimization work:

• Key achievements
• Performance gains
• Lessons learned

Performance Analysis

General performance analysis and profiling results:

• Hotspot identification
• CPU and memory profiling
• Optimization recommendations

Raw Benchmark Data

The following files contain raw benchmark output:

• backend_comparison_6backends.txt - 6-backend comparison raw data
• backend_comparison_optimized.txt - Optimized backend comparison
• backend_comparison_results.txt - Detailed backend comparison results
• dat_benchmark_results.txt - DAT benchmark output
• dat_fuzzy_matching_results.txt - DAT fuzzy matching benchmarks
• dat_levenshtein_benchmark.txt - DAT Levenshtein distance benchmarks
• dat_optimized_benchmark.txt - Optimized DAT benchmark results

Benchmark Methodology

All benchmarks are run using Criterion.rs with:

• Statistical analysis to detect performance changes
• Warmup iterations to stabilize measurements
• Multiple samples for statistical significance

Related Documentation

• Research - Research that led to optimizations
• Developer Guide - Performance optimization guide