Retrospective: M3 (framework extraction, conformance kit, 0.1 API freeze)

Status: complete (2026-09-29), review fixes done (2026-09-30), acceptance fixes done (2026-09-30) on the branch m3-framework (from main at 019ef13, the merge of pull request #2 with M1a, M1b, M2 and M4), pending the orchestrator’s pull request into main. M3 was done in five steps, each by one implementer; a sixth step fixed the findings of the independent review and a seventh the findings of the acceptance review. This page was written in step 5 from the steps’ records (parity/results/M3.md, docs/developer/framework.md, docs/developer/conformance.md, ADRs 0022-0024) and updated in steps 6 and 7.

What was built

Step	Commits	What
1. framework	099a73d..f664f96	cpp/src/framework/: problem_base (CRTP hooks whose defaults return not_provided, so an unimplemented hook is never called and gets no stage), families fixed_point / aggregate_delta, update_enactor (before-commit half: normalize, prepare, before_apply, the aggregate-delta count on G_t; after-commit half: identify_affected, seed, loop or count, finalize, or enact_fused; a device-error check ends each half), static_enactor, old_view / new_view (I1, version-checked in Debug), context, policies, internal_frontier, budgets with allocation and host-sync counters (I9, DYNG_DEBUG_BUDGETS), the compile-time conformance checks, problem_participant / update_one / make_participant over the M1a run_update. Tests with two fake problems and six compile-fail tests. docs/developer/framework.md
2. migrate-sssp	ff39e6b..b8c3794	sssp onto the enactors one backend per commit (sequential, OpenMP, CUDA as Tier B around the verbatim host side of MOSP-CUDA’s kernels), with a temporary per-backend switch removed in the last commit; perf_ab.py run --baseline-exe (dynG against an earlier dynG build); the stage-order test
3. migrate-cycle	1dfb381..47c9e18	cycle_count onto the enactors, the same way (count overloaded on the old and new view, ownership::min_member; CUDA Tier B for update and compute); note_host_sync() at every direct cudaStreamSynchronize; the multi-result dyng::update over two framework problems (C10’s first test); a harness fix (--baseline-exe on the cuda backend)
4. kit-scaffold	9f891c6..725dec6	the conformance kit C0-C12 (cpp/tests/conformance/, registry-driven), the public registry <dyng/core/registry.hpp>, scripts/regen.py, scripts/new_algorithm.py with cpp/src/algorithms/_template, ci/scaffold_check.sh; budget refinements the kit needed (reservations, container work); the kit’s finding in the OpenMP sssp hot path (list_gather); welcome.yml skips members; ADR 0022
5. api-freeze	09abf17..cadf7a2	the 0.1 API review and its fixes, the public-API listing and its check, the reviewed sketches, the “Add an algorithm” outline, ADR 0023, the full gate suites on the final code (parity/results/M3.md section 4), this retrospective
7. acceptance fixes	ed6e2da..(the acceptance commits)	the acceptance review’s findings (below, “The acceptance review”): cycle_count on CUDA reads the framework’s normalized lists instead of copying them; subset builds link (sssp added); the heap-layout and process-mode findings and ADR 0024 (--layouts, parity/ab_modes.py); every suite re-measured on the final code (parity/results/M3.md section 6)
6. review fixes	0a98429..(the review commits)	the confirmed findings of the independent review (below, “The review”): the budgets counted per thread with strict budgets for the kit, the engine chosen before the commit, a backend-aware engine::automatic, both halves of an update budgeted; dyng::update() dispatching through participant_of; the API amendments A1-A11 of ADR 0023; the tooling and kit fixes; the device-memory readings, the corrected readings against 019ef13 and their diagnosis, all re-measured on the final code (parity/results/M3.md section 5)

Acceptance criteria

#	Criterion	Evidence	Status
1	The framework in cpp/src/framework (problem_base, enactors, fixed hook order with one stage per hook, update_stats, device error flags, views, context, workspace, policies, budgets, run_update composition, conformance static_asserts); operators only when both algorithms use them; Tier B hosts the verbatim kernels	step 1; framework.md (with the differences from PLAN 4.5); cpp/src/operators/ is not created: no operator has two users yet (both algorithms keep their frontiers and loops in their own folders)	met
2	sssp and cycle_count through the enactor on every backend, in small commits, parity unchanged	steps 2 and 3, one commit per backend; sssp 495 / 495, cycle_count 72 / 72 (CPU) and 72 / 72 (CUDA) after every commit, on the code of step 5 (section 4) and on the final code after the review fixes (section 5.2 of parity/results/M3.md)	met
3	Performance unchanged: the full gate suites against the originals, and no regression > 2 % against 019ef13 on a gated region (explained otherwise)	parity/results/M3.md section 6 (the final code; sections 4 and 5 are earlier code)	met. Every PLAN 8.6 gate holds on the final code (section 6.6: timing 0.33-1.02x, device memory 0.81-0.86x and 1.000x). Against 019ef13, read over heap layouts and process modes (ADR 0024, section 6.5): 166 gated regions, every unimodal median at most 1.015, every mode of a bimodal region within 1.6 %, and the only significant mode-fraction shifts in the final build’s favour. The acceptance review’s reproduction, cycle_count’s CUDA DD update (1.017 / 1.023x), was a real 2 % in the first update: a redundant host copy removed in ed6e2da (now 0.989-0.998x). The fixed-layout readings above 1.02 are recorded and explained (section 6.3: the same binaries read 0.99 or 1.10 depending on the length of a file name). The earlier rows called these readings noise (step 5) and then left them to the author as code placement (step 6); neither located what decides them
4	The kit C1-C12 for both algorithms on every backend, incl. C10, C11, C12, and C8 in a budgets build	step 4: sssp 32 / 35 tests (host / CUDA), cycle_count 42 / 46; C4 skipped for both (no backend with two engines in 0.1), its body exercised on a fake two-engine algorithm (review); C8 under strict budgets, covering both halves of an update (review)	met (C4 on real algorithms deferred to 0.2 by ADR 0022)
5	new_algorithm.py + template green on the first build (checked by a throwaway algorithm); regen.py and its CI check	step 4: ci/scaffold_check.sh (CTest scaffold.new_algorithm, cpu.yml job scaffold), regen.py --check in pre-commit, ci/check.sh and lint.yml; since the review the scaffold also writes its API page and the check runs github_meta_check and the docs steps on it	met
6	The 0.1 API review as an ADR, accepted under delegation; the headers frozen with a CI-checked baseline; reviewed sketches; header self-containment	ADR 0023 with its amendments A1-A11 (review) and the GOVERNANCE.md rows; cpp/tests/api/api_snapshot/public_api.txt checked by ci/docs.sh, now with the detail contract, macros and the umbrella’s includes; docs/design/sketches/ (corrected); cpp/tests/api (now also rejecting CUDA headers)	met
7	framework.md, the “Add an algorithm” outline, welcome.yml, CHANGELOG, this retrospective; a fresh clone passes ci/check.sh --parity, ci/gpu_local.sh, ci/docs.sh	step 1 (framework.md, updated in the review), docs/how_to/add_an_algorithm.md, step 4 (welcome.yml), CHANGELOG; a fresh clone passes ci/check.sh --parity, ci/gpu_local.sh and ci/docs.sh at 38122bb (parity/results/M3.md section 4.3), after the review fixes at 9bd842c (section 5.6) and after the acceptance fixes at 1870b09 (section 6.7)	met

The review (step 6)

Independent reviewers found 28 confirmed problems (two pairs were the same defect). Every one was fixed in this milestone except the reading of the 2 % bar (item 5), which step 6 left to the author as open item 1b and step 7 closed:

Area	Findings	Resolution
Budgets (I9)	process-wide counters charged other threads’ calls and the profiler’s sync_stages synchronizations to an update, and the check threw after the commit, poisoning correct results in every Debug build (two findings); the half before the commit, where cycle_count’s delete phase runs, was not measured	per-thread counters (OpenMP workers share a tally), an instrumentation_scope for the profiler, a log in Debug builds and a throw only under strict budgets (the kit’s C8, the framework tests, DYNG_STRICT_BUDGETS=1); both halves measured against one budget (cycle_count on CUDA: 4 syncs); tests with concurrent threads and sync_stages (0a98429, 8d7c14f)
Engine choice	chosen after the commit, so a not_supported_error changed the graph and poisoned the result; automatic picked a fused engine on every backend	chosen and checked in before_commit (also fallback_recompute without recompute), visible through context::chosen_engine(); a fused_available(ctx) hook and a static_assert for problems with both tiers (8d7c14f)
Tooling	CODEOWNERS lines of long names; a scaffold red in the docs CI; the documented baseline command (two findings); names that cannot compile; --remove of any algorithm, losing the planned entry; a manifest that drops a backend	fixed, with tests and a docs step in ci/scaffold_check.sh (29479ed, 249926e, 89f48b4, 776ba05)
The kit	C4 never ran and registration had no compile-fail tests; the “sequential backend” rule was checked at run time only, unrecorded	C4 on a fake two-engine problem; conformance.registration.*; ADR 0022 records the placement of the rule (776ba05)
API (ADR 0023 A1-A11)	update() could not reach a later container; sssp’s link errors and unconstrained distance_t; missing to_string; guarantees and strong builders; to_vector; the snapshot’s blind spots; the profiler race; thread-safety docs; field order, update_each, argument checks; plan references and inaccurate docs	fixed (a8adc03, e9d9819, bc9d22b)
Sketches	mosp stage names the profiler rejects; hyper_sssp’s impossible strong guarantee; triad_count’s rationale; undefined hypergraph types	fixed (26a771c, a8adc03)
Measurement	the OpenMP local10k medians against 019ef13 dismissed as mode noise with a mis-cited comparison; the within-mode cost attributed to enactor bookkeeping; no device-memory reading	re-measured and diagnosed (parity/results/M3.md section 5: code placement of the near-far loop, 0.6-1.2 % with aligned functions); perf_ab.py memory and the memory gate for both algorithms (2cfa347); the 4.1 / 4.2 conclusions corrected

The acceptance review (step 7)

The independent acceptance verifier passed criteria 1, 2 and 4-7 with its own evidence and failed criterion 3: it reproduced cycle_count’s CUDA DD 25K + 25K update at 1.017x / 1.023x of 019ef13, and this record itself called the 2 % bar “not met as measured”, pending an author decision. A minor finding: PLAN 9.4’s -DDYNG_ALGORITHMS=dynamic_kcore did not link.

Finding	Resolution
DD CUDA update above 2 %	located stage by stage (parity/experiments/cycle_count_stage_ab.py): the framework’s Step 0 (unchanged code) 1.02-1.03x in the first update of a process only, and the hook’s copy of the normalized lists into the workspace (0.08 ms), which the device engine never read. The copy is gone on CUDA (ed6e2da); the update reads 0.989-0.998x
The 2 % bar “not met as measured” on the short OpenMP sssp updates and the apply regions	the readings depend on the heap layout (the length of the --timing file name moves the same pair between 0.99 and 1.10) and on per-process modes whose fractions sit near one half; ADR 0024 (accepted under delegation) reads a refactor over heap layouts and mode by mode; the whole bar re-measured under it: met (parity/results/M3.md sections 6.3 and 6.5). The fixed-layout readings are kept
Subset build without sssp does not link	sssp is added to every subset (8d59221; ADR 0022 amendment); ci/scaffold_check.sh builds every target of a probes-only subset

Deviations from the plan

Each is a pragmatic choice with the plan’s intent, recorded where it was made.

1. The framework’s shape differs from the PLAN 4.5.2 sketch in the places listed in framework.md, “Differences from PLAN 4.5”: no reserve hook (ADR 0015’s leases size the workspaces), no translate hook yet (no 0.1 user; hyper_sssp and mosp bring it), prepare reads the old view, a normalize hook, finalize takes the stats, count is overloaded on the view type, the static Tier B hook is compute_fused, lifecycle members carry the validation of PLAN 4.8, and run_update keeps the type-erased participants of M1a with a typed adapter on top. File names follow the task (views.hpp, budgets.hpp).

2. Temporary migration switches. Both migrations used a per-backend switch between the old participant and the new problem for their first two commits (the backend is only known in before_apply); each was removed in the CUDA commit.

3. Stage rows. Under set semantics cycle_count.normalize is called twice per update; on CUDA cycle_count’s own stages sit inside a new cycle_count.enact_fused row. The gated regions read the same stages as before (parity/results/M3.md section 2.3).

4. Errors from the fused engines are raised through the context’s device-error word and thrown by the enactor (the same types and messages).

5. The “before” builds of the migration steps were f664f96 and b8c3794 (each the end of the previous step), not 019ef13; the final reading against 019ef13 itself is section 4.

6. The kit lives in cpp/tests/conformance/ (not cpp/tests/support/); “the registry” is two generated C++ registries (the public one and the kit’s), the Python one waits for M5; C4 is skipped; the scaffold writes graphs on the host backends only (ADR 0022).

7. The budgets gained reservations and container work, so that “once reserved” in I9 is precise (ADR 0022).

8. The API freeze is a committed declaration listing from the Doxygen XML, not an ABI dump (most of the API is templates; abidiff joins at 1.0, PLAN 5.9); io/*, generators/* and testing/* are tracked but frozen only in M5 (ADR 0023).

9. Measurement. Several refactor readings used dynG-against-dynG A/B runs (--baseline-exe) at 21-41 rounds, because the original’s side was too noisy on OpenMP to resolve a 2 % change; the gate readings against the originals follow the approved protocol.

10. Invariant I9 after the review measures both halves of an update (PLAN names only the phase after the commit), counts per calling thread, and throws only under strict budgets (a Debug build logs an excess); the engine is chosen before the commit and engine::automatic is backend-aware through a new fused_available hook (framework.md).

11. dyng::update()’s dispatch is the class template detail::participant_of with a static run(), not a qualified detail::run_update() call, so the hypergraph can join (ADR 0023, amendment A1).

12. Records. Two CUDA JSON records of step 3 are compacted to the repository’s 256 KB limit (the full ones are in $DYNG_SCRATCH); performance records made while documentation was being written carry +dirty (the binaries are those of the named commit).

13. The refactor bar’s reading (step 7, ADR 0024, accepted under delegation): a dynG-against-dynG A/B cycles its rounds through heap layouts and reads bimodal regions mode by mode; the plan’s protocol (one layout, medians) stays the gates’ reading and the fixed-layout refactor readings stay recorded. Subset builds always include sssp (ADR 0022 amendment), where PLAN 9.4 implies a build of one algorithm alone.

Lessons

1. Extracting a framework from two opposite, working ports was the right order. Every hook of the template has a real user, and the two families were exercised by the first two algorithms; nothing in the framework is speculative. The rule of two kept cpp/src/operators/ empty for now, which is honest: the two algorithms share the pipeline, not their loops.

2. Name the stages first, then move the code. Pinning each algorithm’s stage sequence in a test before its migration (TheEnactorsOpenTheStagesOfTheTimedRegions) made “the timed regions are unchanged” a checked property instead of a claim.

3. dynG against dynG is the refactor’s measurement. Against the original, the OpenMP side moves by up to 24 % between rounds; against the previous dynG build in the same session the noise mostly cancels. The harness option (--baseline-exe) paid for itself in the first migration.

4. Short OpenMP batches are bimodal per process. Every local10k run of both builds, and of the original, lands in one of two modes 8-10 % apart, chosen when the process starts; a median over 21 or 41 rounds follows the mode mix, which changes between sessions of the same binaries. Reading a 2 % refactor bar on such regions needs a mode-aware comparison (split at the gap, compare mode by mode), which M3 did by hand; the harness should report it (open item 9).

5. Code placement is a real effect on this CPU. Unchanged code (the CSR text reader, graph.build) moved by 5-20 % between builds when unrelated code grew, and padding branches off 32-byte boundaries (-Wa,-mbranches-within-32B-boundaries, the Cascade Lake jump-conditional-code erratum) removed the difference every time. A 2 % refactor bar on end-to-end regions cannot be read on such a machine without controlling layout; the gates against the originals (5-10 % bars) are not affected in practice. Whether the parity preset should pad branches is a protocol question for the author (open item 1).

6. The conformance kit found real problems on its first run (a heap allocation per gather in the OpenMP sssp engine, and a charge of the graph’s own upload to cycle_count’s budget), which the ports’ own suites could not see. Generic checks across algorithms are worth their cost.

7. An API freeze needs a mechanical check, or it is only a statement. The listing is cheap (it reuses the Doxygen XML) and shows the API diff next to the code in every pull request. The review showed where it was blind (the detail types the public signatures name, ungrouped macros, the umbrella’s includes); a check is only as good as what it lists.

8. A diagnostic that throws after the commit is a correctness bug. The budget check was meant to catch regressions and instead poisoned correct results in every Debug build with a second thread or sync_stages. Checks that run after the point of no return must report, and only a test harness should make them fatal.

9. Do not explain a measurement you have not located. Step 5 attributed a 1-2 % difference to “enactor bookkeeping” that runs outside the timed stages, and called medians noise with a comparison of the wrong pair. The review’s stage-by-stage A/B with an idle parent located the difference in unchanged code within an hour, and aligning the functions of both builds showed what decides it. Measure the stage, bisect, and control the suspected variable before writing the cause down.

10. A reading can depend on a file name. The same two binaries read 0.99x or 1.10x of each other on a short OpenMP update depending only on the length of an argument the program keeps on its heap; the harness fixed that length, so every session read one heap layout, and three rounds of review read the outcome as code. Before a small difference is attributed to the code or to “placement”, vary what the process sees (arguments, environment, layout) with the binaries fixed, and read bimodal samples mode by mode: the median of a half-and-half mixture jumps by the gap between the modes.

Open items

For the author:

1. Layout control in the parity preset. The end-to-end readings of the host engines (and single update regions near the 2 % bar) move with code placement on the Xeon Gold 6258R (sections 1.4, 2.4, 3.3 and 4 of parity/results/M3.md). Options: (a) accept, and read refactors dynG-against-dynG on the gated update regions only, as M3 did; (b) add -Wa,-mbranches-within-32B-boundaries (or -falign-jumps=32) to the parity preset for both the originals and dynG, which changes the measurement protocol of ADRs 0018/0021 and needs the author’s decision. The recommendation is (a) for 0.1 and a measured proposal for (b) before the 0.2 gates. 1b. (Closed in step 7.) Criterion 3 no longer waits on an author decision: the 2 % bar is met when a refactor is read over heap layouts and process modes (ADR 0024, accepted under delegation; parity/results/M3.md section 6.5), and the one reading with a single mode above the bar, cycle_count’s CUDA DD update, was a redundant copy, removed. Item 1 (layout control for the gates against the originals, before the 0.2 gates) stays the author’s; ADR 0024’s layouts are one of its options.

2. The API review (ADR 0023) was accepted under delegation; the author may want to read its findings table and the sketches before M5 binds the API to Python.

For the review of M3, M5 and later:

3. C4 (fused equals operators) waits for a backend with two engines (the sssp operators engine, M7).

4. The scaffold writes no CUDA backend and no hypergraph container (0.2).

5. profiler moves behind a pimpl before 1.0 (ADR 0023, finding 10); io/*, generators/*, testing/* are reviewed and frozen in M5; the Python binding notes of ADR 0023.

6. The api-check.yml workflow (the api-change label check and griffe) in M5; until then the reviewers check the label by hand when the baseline changes.

7. The CI job and CTest of the scaffold need network access for GoogleTest when the CPM cache is cold.

8. The reference builds of this milestone under $DYNG_SCRATCH (m3-final/: 019ef13, 47c9e18 and the two padded builds, about 90 MB) are kept for the acceptance and deleted after it; the earlier m3-sssp/base and m3-cycle/base were deleted in step 5. Step 7’s full records and experiment trees are in $DYNG_SCRATCH/m3-fix (the experiment builds are deleted).

9. (Done in step 7 as a separate reader.) parity/ab_modes.py reports bimodal regions mode by mode; perf_ab.py itself still prints medians only. The CUDA harness of cycle_count has no --layouts yet (its regions are GPU-bound and unimodal); add it when a CUDA refactor needs it. What puts a process in the slow mode (the heap layout for the short OpenMP updates; for the host apply of large graphs something per process, possibly huge-page availability) is not located.

10. (Corrected in the review.) The within-mode 1-2 % of step 5 is not the enactor’s bookkeeping, which runs outside the gated stages: it is in the near-far loop stage, whose code is unchanged, and it follows the code placement (parity/results/M3.md section 5.4).

11. The review’s reference and experiment builds under $DYNG_SCRATCH/review/m3fix-diag (aligned builds of 019ef13 and the final code, the bisect points) and m3-review/runs (the uncompacted records) are kept for the author’s decision and deleted after it.

Re-estimate of the roadmap

Measured. M3 was estimated at 2-4 days of focused work (the M2b retrospective) and took one long day of wall-clock time for its five steps (about 8.5 hours for steps 1-4 by the commit times, and about half a day for step 5, most of it the gate suites: sssp 4 graphs x 3 batches on two backends against the originals and against 019ef13, and cycle_count’s M2a and M2b case lists on two backends, about four to five hours of exclusive lock time). As in M1-M2 the independent review is still to come and has found real defects every time (about half a day of fixes).

What this changes. The framework and the kit make the next ports more mechanical (a port is now a problem class plus traits, checked by C1-C12 from day one), but M5 is not a port: it is packaging (nanobind, scikit-build-core, stubs, the first TestPyPI release candidate), where the unknowns are in tools, not in the library.

Milestone	Plan (working weeks)	M2b re-estimate (focused)	Now: focused effort, incl. review and fix	Calendar incl. author gates	Main risk
M3 framework + kit + API freeze	2-3	2-4 days	done (about 1.5 days of wall-clock time), its review fixes (about 7 hours) and its acceptance fixes (about 8 hours, most of it measurement)	the pull request	the layout question for the gates (open item 1)
M5 Python CPU wheel, CLI, docs	2-3	2-4 days	2-4 days	1-2 weeks	nanobind + scikit-build-core, the stubs, the first TestPyPI release candidate on a clean machine; binding the variadic dyng::update (ADR 0023)
0.1.0	12-17 (from M0)	about 1-2 weeks	about 1 week from now	about 2-4 weeks	the release approval (checkpoints), the first hosted runs of every workflow
0.1.x (M6)	4-6	4-7 days	4-7 days	2-3 weeks	the GPU runner decision (O11); CUDA wheel sizes; checkpoint A4
0.2.0 (M7-M9)	8-12	1.5-2.5 weeks	1.5-2 weeks	4-6 weeks	the sssp operators engine within 1.05x of the fused one (and C4); the staged CBST merge; memory <= 1.05x; the layout question of open item 1 for the 5 % gates
0.3.0 (M10-M11)	8-12	1.5-2.5 weeks	1.5-2.5 weeks	4-6 weeks	DynLP’s calibrated tolerances (the kit’s reference oracle kind is in place but unexercised), slotted/slack rows, the translate hook
Up to 0.3.0	about 32-47	about 5-8.5 weeks	about 4.5-7.5 weeks	about 12-19 weeks

The review step (measured). The fixes of the 28 findings took about 7 hours of wall-clock time on 2026-09-29/30: about 4 hours of code and documents (the framework, API and tooling changes with their tests), about 1 hour for the diagnosis of the OpenMP readings, and about 2 hours of gate suites, parity replays and memory readings on the final code, plus the fresh-clone checks. That is more than the half day estimated above, because the review reopened measurements, not only code; later reviews should budget the re-measurement of the gates as part of the fix step.

The acceptance fixes (measured). About 8 hours on 2026-09-30: under an hour of code (the cycle_count copy, the subset build, the harness option and the reader), about 2 hours locating the layout effect, and about 5 hours of suites (the full gate suites against the originals and 019ef13, the 17-layout suite and the 85-layout readings; roughly 4 hours of exclusive lock). A 2 % refactor bar on this shared machine costs a day of measurement per milestone; M7-M9’s operators engine should plan for it, or the author should settle open item 1 first.

Recommended order now: the pull request of m3-framework into main; the decision on open item 1 before the 0.2 gates; then M5.