[PERF] Fuse matches-tape validation into kernel row loops

[samukweku]

Brief description

Remove the extra whole-input passes used to validate flat matches tape widths in aggregation, comparison, and index-builder kernels, while preserving the existing deterministic ValueError behavior for undersized tapes.

The current ensure_tape_width helper is O(1), but its callers first compute expected_matches_width by scanning every row's start/end range. There are currently 49 such prepass sites across 27 source files. The kernel then traverses the same row metadata again to do the actual work.

This is most likely to matter for sparse workloads, zero-width rows, or otherwise cheap per-row operations, where the validation pass can become a material fraction of total runtime.

ELI5

Before processing the tickets, the code reads every ticket once to count how much tape will be needed. It then starts over and reads all the tickets again to do the work. Instead, each ticket can check that enough tape remains immediately before using its own section.

Proposed direction

1. Prototype fused validation in one representative *_matches core with existing benchmark coverage.
2. For each row, derive its validated tape width using the same range/index rules as the processing loop.
3. Before indexing matches, use checked arithmetic to verify that the row's required end position is within matches.len().
4. Return the same clear Python ValueError when the tape is too short; do not replace validation with panics, unchecked indexing, silent truncation, or a caller-only contract.
5. If benchmarks show a meaningful improvement or neutrality, extract a small shared helper and roll the pattern out to the remaining aggregation, comparison, and index-builder sites without obscuring their hot loops.

Acceptance criteria

• Valid-call output, ordering, dtype behavior, sentinel handling, and null-mask behavior remain unchanged.
• A tape that is too short still raises a deterministic ValueError before any out-of-bounds access.
• Checked addition prevents n + row_width overflow.
• Tests cover exact-length, longer-than-required, one-element-short, invalid/sentinel ranges, zero-width rows, and a malformed row followed by a valid row.
• Benchmarks compare the current prepass and fused-validation implementations for dense, sparse, and zero-width-heavy fixtures at small and large row counts.
• The change is rolled out beyond the prototype only if benchmarks are neutral or positive.
• cargo test --no-default-features, clippy, formatting, and benchmark compilation pass.

Scope notes

• Keep O(1) metadata checks such as ensure_equal_lengths and comparison-op decoding unchanged.
• reorder_index validation and allocation work remains under [MAINT] Harden and simplify conditional-join index builders #25.
• Binary-search/comparison improvements already scoped to [PERF] Improve retained binary-search and comparison kernels #24 should not be reopened or coupled to this work unless a tape-width prepass is directly involved.

[samukweku]

Investigation result

The proposed fused matches-tape validation was prototyped in sum_rev/sum_starts_ends_matches.rs for both integer and float kernels. The prototype validates each row immediately before consuming its tape segment:

1. checked_range validates the row boundary.
2. Checked addition computes the next tape cursor.
3. The kernel verifies the complete row segment fits before indexing matches.
4. The cursor advances once for every candidate, including zero-valued match flags.
5. A final exact-length check preserves the existing contract.

Adversarial coverage passed for exact-length, longer, one-element-short, invalid/sentinel, zero-width, malformed-row-followed-by-valid-row, and cursor-overflow cases.

Benchmark results

A dedicated benchmark compared the existing whole-input width prepass with row-local fused validation across sparse, dense, and zero-width-heavy fixtures at 100 and 100,000 rows. On macOS arm64:

Fixture	Rows	Prepass	Fused
sparse	100	~26.6 ns	~57.4 ns
dense	100	~33.0 ns	~57.6 ns
zero-heavy	100	~26.4 ns	~33.1 ns
sparse	100,000	~27.2 us	~50.3 us
dense	100,000	~27.6 us	~49.9 us
zero-heavy	100,000	~27.1 us	~32.7 us

These isolate validation overhead. Fused validation is approximately 2x slower for sparse/dense inputs and approximately 21% slower for zero-heavy inputs. It does not provide evidence of a net win once the actual aggregation work is included.

Decision

Do not roll this pattern out to the remaining aggregation, comparison, or index-builder kernels. The per-row checked cursor update costs more than the removed width-summing pass in the measured validation workload, and the issue acceptance criteria require neutral or positive benchmark evidence before rollout. The existing prepass remains the better design for now.

The prototype is preserved in branch issue-66-fuse-matches-validation at commit 5571fa2 as a reference if future kernel changes make the trade-off worth revisiting.