perf(api): import normalization is 13% of validate at exactly one effective core

[DecisionNerd]

Execution prerequisite (#1478 rev 13): blocked by #1477 in native issue relationships. This issue owns the normalization/input-overlap experiment that precedes #1448's decomposition. Its result must be evaluated before that dependent implementation; success is not presumed.

Summary

normalize_import_node_chunk / normalize_import_edge_chunk are 13.0% of import-session validate at S18 rung scale, running at 1.01 effective cores — perfectly serial, on a 16-thread host.

Measured on real S18 Graph500 data, release build, quiet host, validate wall 36.14 s:

stage	wall	% of validate	eff. cores
shaping	19.88 s	55.0%	0.93
canonical_encoding	6.50 s	18.0%	0.88
normalization	4.69 s	13.0%	1.01
append	4.23 s	11.7%	0.87
parquet decode + residual	~0.84 s	2.3%	—

97.7% of validate accounted. Normalization is the third-largest stage, larger than every region inside shaping except after_chain (16.5%) and chunk_loop (14.7%).

Why this one is worth doing

Nobody had measured it. Every previous analysis of the ingest path — including my own on #1464 — divided up shaping and treated the rest as overhead. It is not overhead; it is a stage.

And unlike most of the serial path, this work has no ordering dependency. assign_surrogates is sequential because surrogates are a running counter in global order; finish_optional's consume is sequential because a linear digest authenticates the output. Normalization is per-batch over independent input chunks, and it is serial because nothing made it otherwise, not because it must be.

Where the work is

crates/graphforge-api/src/bulk_construction/normalization.rs:1305, called per batch from the staging loop in import_session.rs. For edges it builds a BulkNodeRow per candidate endpoint — roughly 8.4 million at S18 (4.19M edges x 2) — before normalize_bulk_edges runs.

Two independent axes, either of which is worth measuring alone:

1. Within a batch. Row-wise validation over a RecordBatch with no cross-row dependency beyond within-chunk duplicate detection.
2. Across batches. epic(storage): stop maintaining a hand-rolled dataflow engine; reuse Arrow/DataFusion where determinism and durability allow #1456's implementation item 3 already proposes overlapping input preparation with append, "preserving batch order, replay identifiers and manifest semantics", with the queue governed by bytes rather than batch count. Perfect overlap of normalization with append caps at min(4.69, 4.23) — about 11.6% of validate — so the two axes compose rather than substitute.

Acceptance

• Normalization's effective cores rise above 1.0, measured with the region instrument (observe(storage): wire the region instrument to a caller, and fix the spec that would break it (#1387 D4) #1477; replaces observe(storage): nothing measures the serial fraction of ingest, and #1387 budgets against it #1462's incomplete instrument) at rung scale, not on a small fixture — a 131k-identity fixture is dominated by fixed per-run cost and its ratios do not transfer (see perf(storage): break the surrogate-assignment serial chain with a prefix sum — target unverified, measured at ~9% of shaping #1464).
• validate wall falls, measured on a quiet host across at least three runs.
• Output identical: the four fixed-width run digests and every published artifact byte-for-byte unchanged, per ADR 0038's boundary.
• Within-chunk duplicate detection and every existing validation refusal preserved — this is a parallelisation, not a relaxation.
• Batch order, replay identifiers and manifest semantics unchanged, so recovery and resume behave identically.

Context that should temper expectations

This is one stage of nine, and the whole path measures 0.92 effective cores with nothing above 1.16. Fixing normalization alone moves validate by at most ~13%, and #1387's floor is 9.2x away. It is worth doing because it is the cleanest available parallelism in the path and it is measured, not because it closes the gap.

Related: #1387, #1456 (implementation item 3), #1464 (where the rung-scale attribution is recorded).

[DecisionNerd]

The serial stages share one structure, and work item 5 already names the fix — it was just aimed at the smallest instance

Having attributed the whole path, the stages that measure at approximately 1.0 effective cores turn out to be the same shape:

stage	eff. cores	% of validate	the sequential structure
normalize_import_*_chunk	1.01	13.0%	running ordinal, accumulating observed duplicate set, error ordinals order-sensitive
validate_staged_details	1.00	3.3%	running nodes / edges counters over a while let scan
assign_surrogates	0.82	0.8%	running node_tail / edge_tail counters

Every perfectly-serial stage in the ingest path is a sequential scan carrying a running counter. Some also carry an accumulating set. That is not three unrelated problems; it is one pattern occurring three times, and it explains why the whole path sits at 0.92 effective cores rather than having one hot spot.

What that means for work item 5

This epic's item 5 says:

Shorten the dependency chain. For surrogate assignment: count per canonical range, prefix-sum the starting IDs, then assign ranges concurrently.

The technique is right. The target was the smallest instance of it. assign_surrogates is 0.8% of validate; the same decomposition applied to normalize reaches 13.0%, and to validate_staged_details another 3.3%.

The general form, which is what item 5 should be re-scoped to:

1. Running counters → count per range, prefix-sum the starting values, emit ranges concurrently. Identical to item 5's prescription.
2. Accumulating sets (observed, known_nodes) → merge commutatively per range, with one cross-range duplicate pass. The same move feat(storage): worker-local partition loads with coordinator-owned evidence (#1456 item 1) #1459 made for evidence counters, where plain sums and per-partition maxima merge in any order.
3. Order-sensitive error ordinals → the awkward part, and worth stating rather than discovering. A parallel scan finds a failing row, not the first one. Either the ordinal is recomputed once a failure is known, or the contract changes. This is a decision, not an implementation detail, because refusal messages are part of what callers see.

Why this is the useful framing

Rev 8 sequenced "1c: surrogate prefix sum" as the critical path and treated it as one item. Measured, it is 0.8%. But the technique it names is the one lever that applies across the serial stages, and applying it three times reaches roughly 17% of validate instead of 0.8%.

That is still not the floor — the path is nine stages at about one core each, and #1387 is 9.2x away — but it converts "nine separate parallelisation projects" into "one decomposition applied nine times", which is a materially different piece of work to plan and staff.

Filed the normalization instance as #1472. Recommend re-scoping item 5 from "surrogate assignment" to the pattern, with assign_surrogates demoted to its smallest and least valuable instance.

[DecisionNerd]

The remaining normalize/append overlap question now has an explicit measured-bound no-go disposition, recorded in #1478 §5. This preserves the distinction that #1472 implemented bounded parallel normalization, not overlap. Quiet S19 unchanged-work optimistic bounds remain below F5’s 1.1× criterion even if all validate work outside append and seal disappears. No overlap implementation or measured overlap speedup is claimed; #1387 still owns the integrated baseline and throughput floor.

[DecisionNerd]

Evidence relocated from the docs tree (#1625). The 2 file(s) below were committed under docs/development/ as measurement evidence for this issue. They are removed from the tree by #1628 (the #1625 pull request); the repository keeps method and content digests, results live here. Every file remains available at its permalink on commit 29a7b34ebe44, and its SHA-256 is recorded next to it.

Files (2 total, 711 lines)

• docs/development/evidence/parallel-normalization-1472.json sha256:be71f25493ce977a97abaca189c53106b4060f39bd76d450b9dfa509f940b04c
• docs/development/evidence/parallel-normalization-1472.md sha256:7429b6e4f4e98b58fbc77ad81b966e494958b60569d96ce6c6fe0df8a5b32edd