Skip to content

benchmarks.md

Latest commit

 

History

History
122 lines (79 loc) · 5.9 KB

benchmarks.md

File metadata and controls

122 lines (79 loc) · 5.9 KB
Raw

Benchmarks

The benchmark suite measures the standalone crate's public semantics. It does not inspect graph nodes or add benchmark-only library hooks.

Comparison rules

A benchmark comparison must answer one specific question. The suite follows these rules:

  1. Use the same public operation trace. Structural-growth cases start from the same extensional value and apply the same pushes, merges, pops, and weight assignments to each representation.
  2. Keep conversion separate from structural evolution. from_stacks benchmarks intentionally begin with complete concrete vectors and are labelled from_explicit_entries; they measure import cost, not general scalability.
  3. Exclude harness preparation. Constructor inputs are cloned in Criterion setup batches, outside the timed routine. Criterion also drops constructed results outside the timed interval.
  4. Compare equivalent output. Owned-output cases produce complete concrete (stack, weight) values. Borrowed-visit cases perform the same orientation-sensitive checksum and enforce the same stack-count bound.
  5. Verify benchmark helpers. Integration tests compare each weighted and unweighted structural builder against the compact implementation after every complete trace.
  6. Label stress cases as stress cases. Broad fan-out collapse and other adversarial shapes remain valuable regression tests, but they are not presented as typical parser workloads.
  7. Do not derive throughput from represented alternatives for compressed operations. A constant-time operation over a compact language may represent exponentially many stacks; dividing by that denotation produces impressive but misleading rates.

Baselines

Explicit stack-to-weight map

FxHashMap<Vec<Symbol>, Weight>

This directly implements the documented finite-map semantics. It reserves capacity when input size is known. Merge clones the larger operand and inserts the smaller, joining weights on key collision. Push, pop, and selection transform complete concrete stacks.

It is the primary semantic and performance baseline, not a deliberately slow straw man.

Weight-partitioned stack sets

FxHashMap<Weight, FxHashSet<Vec<Symbol>>>

This benchmark-only ablation asks what happens when sharing is allowed inside each weight class but not across weights. The same concrete stack may occur in several buckets, so materialisation must join coincident weights. It requires hashable weights, unlike the public API.

Explicit unweighted stack set

FxHashSet<Vec<Symbol>>

This is compared with Gss<S> = WeightedGss<S, ()>. It isolates persistent graph sharing from nontrivial weight handling.

Workloads

construction

construction/from_owned_single_stack measures taking ownership of one complete stack at several depths.

construction/from_explicit_entries measures conversion from already enumerated inputs:

  • 128 stacks sharing a bottom segment;
  • all 1,024 paths of a depth-10 binary language;
  • one, two, eight, and 32 weight classes;
  • two stacks sharing up to 20,000 top symbols.

These are valid import benchmarks but are deliberately not used as the primary scaling evidence.

construction/structural_binary_growth starts from an empty stack language and performs the same repeated public trace on both implementations:

value = merge(push(value, left_symbol), push(value, right_symbol))

After d rounds the value denotes 2^d stacks. The suite measures both one homogeneous weight and two stable weight classes at depths 4, 8, 12, and 16.

operations

  • push and pop on one linear stack at several depths;
  • disjoint, half-overlapping, and completely overlapping merges;
  • independently constructed values with common top segments up to 20,000 symbols;
  • structural_binary_pop, operating on values built through the structural trace;
  • retain_top over increasingly broad frontiers;
  • persistent forks from one immutable source;
  • stress/wide_fanout_collapse_pop, where many independently weighted top branches collapse simultaneously.

materialization

  • owned_output: complete concrete outputs from to_stacks, explicit-map snapshots, and weight-partitioned materialisation;
  • borrowed_visit: bounded visits with equivalent top-first checksumming work;
  • limit_rejection: failure before callbacks when the distinct-stack limit is too small.

Materialisation is inherently proportional to concrete output. It is kept separate from compact graph operations.

unweighted

The unweighted target mirrors flat import, structural binary growth, push, pop, materialisation, structural pop, and merge against an explicit stack set.

Running benchmarks

Run everything and record environment metadata:

./scripts/run-benchmarks.sh -- --noplot

Run one target or group:

cargo bench --bench construction -- structural_binary_growth
cargo bench --bench operations -- structural_binary_pop
cargo bench --bench operations -- stress/wide_fanout_collapse_pop

Criterion baselines can compare adjacent commits on the same machine:

cargo bench -- --save-baseline main
# switch commits without changing machine configuration
cargo bench -- --baseline main

Interpreting results

There is no single “GSS speed” number. Record at least the commit, dirty state, toolchain, CPU, operating system, competing load, exact workload, input shape, and whether construction or materialisation is included.

Do not use absolute timing gates on shared GitHub-hosted runners. CI compiles and smoke-executes the benchmarks; performance decisions should use adjacent runs on the same isolated machine.

The historical GLRMask/CFA timing bracket remains application-level evidence. It answers whether the API supports one demanding parser workload, not how the standalone structure scales in isolation.

See Benchmark methodology audit — 2026-07-28 for the redesign rationale and a clean recorded run.