ADR 0013: Parity and goldens#

  • Status: Proposed (draft, M1a); accepted with the 0.1 release, after the CUDA port (M1b) and cycle_count (M2) have used it

  • Date: 2026-09-27

  • Deciders: S M Shovan (lead maintainer)

Context#

Every algorithm of dynG is a port of a research repository, and the promise of the library is that a port computes exactly what the original computes (PLAN Sections 6.3 and 8.3). That promise is only worth something if the evidence can be reproduced later, by someone else, on a clean machine: the originals keep changing on their own branches, local tags do not travel, scratch directories of a session disappear, and results that exist only in CI logs are lost (risk R22). The originals also must not be touched: they are the authors’ research artifacts, and a build inside them (or a stray patch) would change the thing that is being compared against.

M1a is the first use: sssp on the CPU against MOSP-OpenMP@c352151, plus the one-off cross-check of MOSP-CUDA@e220ee2 against MOSP-OpenMP.

Decision#

  1. Pinned references. parity/references.toml lists each original with its full commit SHA, the SHA of its local baseline-2026-09 tag, its location, upstream remote, build command, run environment, smoke test, gitlinks, external inputs and toolchain. The port must match the pinned commit; the baseline SHA documents what the papers measured.

  2. Scratch builds only. parity/build_reference.sh exports the pinned commit with git archive into the persistent work area $DYNG_SCRATCH/ref/<name>@<commit7>/ (never a session temporary directory, never the repository), in two variants:

    • unpatched: the archive as is; performance baselines come only from it;

    • patched: the archive plus additive export tools (parity/export_patches/<repo>/, sources in parity/exporters/); no original file is modified. Goldens come from it. The script verifies that every tracked file of a copy still equals the archive (content, type, executable bit), that the original repository’s HEAD and status are unchanged after the build, and writes the archive-build check (gitlinks left out, local-only inputs, absolute paths, external inputs). It is idempotent.

  3. Goldens outside the repository, manifest inside. parity/export_goldens.py writes the golden sets to $DYNG_SCRATCH/goldens/<set>/ (for sssp: 495 cases, 184 MB) using only the original’s own tools and test programs to create inputs (the group noncanonical perturbs the tie parents of mospPrep init trees in the export script, seeded by the case name, and records what mosp computes from them). Each set has a MANIFEST.sha256 of every file; the committed parity/goldens.toml records the manifest’s SHA-256 and one digest per case. Small cases stay committed as test fixtures under cpp/tests/data (< 1 MB in total). Paper-scale inputs (roadNet-CA etc.) are regenerated by the original’s mospPrep and recorded by the SHA-256 of every input file in the performance record. The release-asset path of PLAN Section 8.3 (goldens-vN.tar.zst, fetch_goldens.py) is added when CI needs the goldens (M4).

  4. Cross-check the originals first. Before a golden is written, every original implementation that computes the same thing must agree byte for byte (for MOSP-OpenMP: mosp, parallelSOSPUpdate, sequentialSOSPUpdate, mospPrep expected; on non-canonical initial trees only mosp and parallelSOSPUpdate compute the same tree, and Dijkstra the same distances, see ADR 0006 “Tie rule of sssp”); where two original repositories compute the same thing (MOSP-CUDA vs MOSP-OpenMP) they are compared once on the whole corpus before any port is blamed for a difference.

  5. Exact comparison. parity/compare.py first re-verifies the goldens against the manifest, then replays every case through the drop-in driver (tools/compat) on every backend and thread count and compares bytes. The tolerance rules are those of PLAN Section 8.3 (none for sssp, mosp, cycle_count, triad_count, hyper_sssp; calibrated only for label_propagation). Comparisons are never loosened to make a port pass. CTest runs the replay under the label parity (skipped when the goldens are absent).

  6. Honesty checks. Goldens are exported twice from two fresh archive copies and must have the same manifest; a recorded mutation must make the replay fail; a changed golden byte must be detected.

  7. Performance records. parity/perf_ab.py alternates the unpatched original and the port (A/B/A/B, median of at least 5 runs and at least 20 when a gated region of the original is below 10 ms, under $DYNG_SCRATCH/perf.lock, 28 threads pinned for OpenMP) on the regions defined by parity/timed_regions/<algo>.toml, written before the port; the script loads the map and refuses a region it cannot measure. It checks once per batch that both write identical outputs and in every timed round that the deterministic counters are equal, times only a parity-preset build of the port, and records the builds of both sides.

    • Each gate is read as PLAN Section 8.6 defines it. For sssp that is one comparison per objective (PLAN 6.4.2); a sum over the objectives is reported for orientation only and is never a gate reading.

    • Moved costs are counted where the original pays them. When the port does work outside the timed region that the original does inside it (the first touch of the frontier lists: MOSP’s objective 0 pays it; each dynG result pays it when it is created), the record shows the region both as measured and with that cost added, and the gate verdict uses the second.

    • The region map is complete on both sides. When an original’s timer contains more than the mapped port stages (MOSP’s prepare also copies the trees and reserves the workspace; its end-to-end timer includes the combined graph of mosp), the map adds the port’s equivalent stages or subtracts the original’s extra timer, and its notes say what remains.

  8. The parity certificate is committed. Each milestone writes parity/results/<milestone>.md with the JSON records next to it (reference and port commits, toolchains, presets, the golden manifest SHA-256, the case x backend matrix, tolerances, the performance table). From the first release, parity/certify.py writes benchmarks/results/<version>/parity.json in the same format (PLAN Section 10.3).

Consequences#

  • Parity evidence can be regenerated from three inputs: the original repository at the pinned SHA, the dynG commit, and $DYNG_SCRATCH (or a fresh one: every artifact in it is rebuilt by the scripts, except the prepared dataset CSR files, which come from the SuiteSparse downloads and are identified by their SHA-256 in the performance record).

  • The work area needs space (M1a: 26 MB + 30 MB of reference copies, 144 MB of goldens, 160 MB of benchmark inputs); the repository stays small (the manifest is 52 KB).

  • An export patch that is not purely additive, or a golden that needs a patched timing path, is a change of this ADR and must be recorded.

  • Until the goldens are published as a release asset (M4), the parity CTest label is run on the author’s machine only (ci/check.sh --parity, which fails rather than skips when the goldens are missing); CI runs the committed fixture subset (cpp/tests/data, 121 KB: the apply, mtx2csr and sssp fixtures, compared byte for byte in ctest -L cpu).

Open M1b blocker (recorded after the M1a review)#

The per-objective OpenMP gate of sssp (<= 1.05x per objective, PLAN 6.4.2) is not met in M1a: objective 0 is 1.07-1.09x on the 50K batches (1.44x on the local batch) once its moved first-touch cost is counted, and objectives 1 and 2 are close to the limit (1.02-1.04x in the final record, up to 1.063x in earlier runs) (parity/results/M1a.md, section 5). The cause is known: each sssp::result owns its workspace, where MOSP shares one across the K objectives (ADR 0006). M1b must decide how results on one graph share scratch memory, re-measure per objective with the first-touch cost counted, and meet the gate before the CUDA gate is read. Reading the gate on the sum over the objectives is not an option (it would hide the slower objectives behind objective 0).

Resolved in M1b (ADR 0015, parity/results/M1b.md): results share the pooled workspace of their resources handle, so both sides pay objective 0’s first touch inside its region and every objective is compared as measured (no moved cost, no “first touch counted” reading). The gate is read per objective on roadNet-PA, roadNet-CA, rgg_n_2_20_s0 and road_usa (safe, unsafe and local batches) and recorded in parity/results/M1b.md.