AVX2 8-wide ksuid_string_batch kernel (follow-up to #5)

[justinjoy]

Status

This is the follow-up to the partial closure of #5 in PR #12. That PR landed:

• the ksuid_string_batch public API (libksuid/ksuid.h),
• the scalar reference (libksuid/encode_batch.c::ksuid_string_batch_scalar),
• the libsodium-style atomic-pointer dispatch trampoline (race-free, allocation-free),
• the contract-pinning test suite (tests/test_string_batch.c).

The AVX2 8-wide kernel itself is the slot the dispatcher resolves into when the host advertises AVX2 + OS-saves-YMM. That kernel does not yet exist. Until it does, every host resolves to the scalar path with one acquire-load + one indirect call of overhead per call.

This issue tracks the kernel's implementation as its own architect + critic + reviewer cycle. The dispatch infrastructure is already in place, so this is a self-contained "plug in the kernel" change — no public API churn, no rework of the trampoline, no re-litigation of #5's design decisions.

Acceptance criteria

Functional

1. libksuid/encode_avx2.c (NEW) defines ksuid_string_batch_avx2(const ksuid_t *, char *, size_t) matching the prototype in libksuid/encode_batch.h.
2. meson.build adds the file to core_sources under host_cpu == 'x86_64' AND the new option('avx2_batch', type: 'feature', value: 'auto') is enabled (default auto).
3. meson.build defines KSUID_HAVE_AVX2_BATCH=1 so the dispatcher in encode_batch.c resolves to the AVX2 kernel when CPUID + XGETBV pass.
4. The kernel processes 8 KSUIDs per outer-loop iteration via SoA-internal lane layout (5 × __m256i limbs, each holding 8 lanes of u32).
5. The tail (n % 8) falls through to the scalar path inside the kernel.

Performance

6. Measured throughput on an AVX2-capable x86_64 host is >= 4x the scalar path for n >= 256, with 4-6x being the design target.
7. The AVX2 TU contributes <= 4 KB to the stripped library's .text section (Critic risk register R8). Enforced post-build by a CI step that runs size --format=sysv build/libksuid.so.* | awk before and after, fails if delta > 4096 bytes. If exceeded, default avx2_batch to disabled and document the decision.

Parity

8. tests/test_string_batch.c gains a differential test that explicitly invokes ksuid_string_batch_scalar AND ksuid_string_batch_avx2 (when present at runtime) on the same input and asserts byte-for-byte equality across:
   • n ∈ {0, 1, 7, 8, 9, 16, 17, 64, 257, 1024} for tail-boundary coverage,
   • the pinned corners KSUID_NIL, KSUID_MAX, all-0xff, all-0x00,

   • = 2^20 random KSUIDs to catch off-by-one in the divide-by-62 reciprocal-multiplication magic constant,

   • eight distinct KSUIDs with non-trivial high limbs to catch lane-swap bugs in the transpose step,
   • ksuid_sequence_t-generated runs (consecutive payloads at one timestamp).

Critic risk register (carry-over from #5)

The reviewer + meta-reviewers in PR #12 explicitly carried these forward as the implementer's pre-commit checklist:

R3 — AVX-SSE transition penalty

Failure mode: 100+ cycle stall on Sandy/Ivy Bridge whenever AVX2 code returns to surrounding SSE2 code (e.g. base62_sse2.c, compare_sse2.c).
Mitigation: AVX2 kernel lives in its OWN translation unit compiled with -mavx2 only (mirror the existing base62_sse2.c / compare_sse2.c registration). End the kernel with _mm256_zeroupper() before returning. Verify with objdump -d build/libksuid.so.* | grep -c "vex" that no VEX encoding leaks into non-AVX2 TUs.

R4 — Tail handling overrun

Failure mode: 8-wide loop reads ids[n..n+7] past caller's array; SEGV on guard page.
Mitigation: explicit size_t bulk = n & ~(size_t)7; for (i=0; i<bulk; i+=8) avx2_kernel(...); for (; i<n; ++i) ksuid_format(...);. Never use masked loads for the tail — use the scalar path. Add a fuzzer test for n in 0..23.

R5 — Divide-by-62 reciprocal-multiplication magic constant

Failure mode: SIMD encode disagrees with scalar at one specific 5-limb input. AVX2 has no 64-bit divide; the SIMD long-division-by-62 must use _mm256_mul_epu32 + _mm256_srli_epi64 to compute quotient = (value * M) >> N for divisor 62.
Mitigation: derive M ≈ 0x4ec4ec4ec4ec4ec5 from Hacker's Delight 10-9 OR libdivide. Document the derivation in a comment block at the top of encode_avx2.c. Pin parity against the scalar reference over >= 2^20 random KSUIDs plus the corner cases listed in acceptance criterion 8.

R6 — Lane transpose / output-byte mapping

Failure mode: AVX2 encode produces correct base62 digits but writes them to wrong output offsets across the 8 KSUIDs. Scalar writes right-to-left out[--n] = digit; the SIMD version emits 8 digits per outer iteration for 8 distinct KSUIDs, requiring a transpose at store time.
Mitigation: structure the kernel as SoA-internal (5 limbs × 8 IDs in 5 __m256i), emit one __m256i of 8 digits per iteration, and store with strided per-lane writes (out[i*27 + col]). The 8-distinct-KSUID parity test (acceptance criterion 8) is the regression detector.

R8 — Footprint budget

Failure mode: AVX2 TU bloats libksuid.so past the +4 KB cap silently — nobody notices for two releases.
Mitigation: meson postbuild step described in acceptance criterion 7. CI gate must fail the build if the AVX2 TU's contribution exceeds 4 KB. Local builds print a summary.

R11 — KSUID_FORCE_SCALAR env var

Failure mode: env-var read on every ksuid_string_batch call → getenv is not lock-free under glibc.
Mitigation: read KSUID_FORCE_SCALAR once inside the trampoline before resolving the pointer. If set (any non-empty value), the resolved pointer is &ksuid_string_batch_scalar. Document as "captured at first call, not reread." Useful for benchmarking + debugging without rebuilding.

Implementation plan (architect carry-over from #5)

Single PR with a 3-commit split:

Commit	Purpose
1	encode: AVX2 8-wide bulk-encode kernel + first-call atomic dispatch — new libksuid/encode_avx2.c, meson avx2_batch option, __attribute__((target("avx2"))) annotation OR per-TU c_args : ['-mavx2']. The dispatch resolver in encode_batch.c swaps &ksuid_string_batch_scalar for &ksuid_string_batch_avx2 when CPUID + XGETBV pass.
2	tests: SIMD parity matrix covering bulk-encode tail boundaries + degenerate inputs — extends tests/test_string_batch.c with a KSUID_TESTING-gated ksuid_string_batch_scalar / _avx2 direct extern, drives both implementations on the inputs in acceptance criterion 8.
3	ci: footprint gate for AVX2 bulk encode + KSUID_FORCE_SCALAR env override — meson postbuild check + R11 env var.

KSUID_FORCE_SCALAR could land in commit 1 alongside the dispatcher swap; the split keeps each commit independently reviewable.

Cross-platform considerations

• Linux GCC + Clang on x86_64: primary target, full CI coverage.
• macOS Clang on x86_64: AVX2 paths are present in older Intel Macs; Apple Silicon runners do not exercise this code (host_cpu == aarch64 → KSUID_HAVE_AVX2_BATCH undefined → scalar path).
• Windows MSVC: __attribute__((target("avx2"))) is not available; use /arch:AVX2 only on the AVX2 TU via per-target c_args in meson. The CPUID + XGETBV path in encode_batch.c already has the MSVC branch (__cpuidex + _xgetbv) from PR compare: SSE2/NEON 20-byte compare + bulk-encode public API (AVX2 kernel deferred) #12.
• Hosts without AVX2 (older Atom, Steam Deck running x86_64 baseline, etc.): the dispatch resolver simply keeps &ksuid_string_batch_scalar and the AVX2 TU's symbols stay unreferenced → linker discards via --gc-sections if PIC. Verify the AVX2 TU is referenced ONLY through the function-pointer assignment, never through a direct call from another TU, so non-AVX2 hosts incur zero runtime cost.

Verification

The dispatch scaffolding from PR #12 already satisfies R1 (race-free dispatch), R2 (__builtin_cpu_init + _xgetbv), R7 (n/a — compare-side), R9 (NOLINT pattern available), R10 (parity test infrastructure exists), R12 (n==0 early-out). This issue inherits those guarantees without re-litigation.

The wipe-fallback CI lane (PR #10) and the auto-build disasm gate (PR #10 + PR #11) must continue to pass; they are orthogonal to the AVX2 path.

Out of scope

• AVX-512 / VBMI bulk encode (separate follow-up if ever justified).
• AVX2 bulk parse (the issue body originally noted "same API for parse if a benchmark justifies it"; benchmark first, then file).
• Compare path AVX2 acceleration (compare is fixed at 20 bytes; SSE2 already handles the head, AVX2 buys nothing).

Labels

enhancement, simd, x86_64, performance, follow-up

[justinjoy]

Pre-implementation finding — three reviewers all derived the wrong magic constant

When this issue was promoted from a follow-up note to an active design exercise, fresh architect + critic personas were spawned with focused prompts on the implementation specifics (algorithm, intrinsics, lane layout). Both reports returned with concrete pseudocode, and both pinned the divide-by-62 magic constant for Granlund-Möller reciprocal multiplication. Three sources, three different values:

Source	Cited M	Derivation
Original architect plan in #5	0x4ec4ec4ec4ec4ec5	"⌈2^64 / 62⌉ via Hacker's Delight"
Fresh architect (this issue)	0x4ec4ec4ec4ec4ec5	"libdivide libdivide_u64_gen(62)"
Critic "correction"	0x4210842108421085	"the cited constant divides by 13, not 62; recompute"
Python ((1 << 64) + 61) // 62	0x0421084210842109	direct ceiling division

Verification:

ceil(2^64 / 62) = 0x0421084210842109 = 297528130221121801
0x0421084210842109 * 62 = 2^64 + 46    ✓ (just above 2^64, as expected for ceiling)

0x4ec4ec4ec4ec4ec5 * 62 = much larger than 2^64   ✗
0x4210842108421085 * 13 = 2^64 + 6                ✗ (this divides by 13)

0x4ec4ec4ec4ec4ec5 is in fact ⌈2^64 / 13⌉ × 4 + small offset, a copy-paste artifact that propagated across two independent architect cycles citing two different sources (Hacker's Delight and libdivide). Both citations were inaccurate. The Critic caught the original error but produced a third wrong number.

What this means for issue #13

R5 (divide-by-62 magic constant correctness) is no longer a "watch out for off-by-one" risk. It is load-bearing: the implementer cannot derive M by hand and trust visual inspection or a single peer review, because every reviewer in the chain has already gotten it wrong. Without an external tool that generates the constant from d = 62, the implementation will silently corrupt a fraction of inputs.

This is exactly the failure mode R5 named: "off-by-one in magic constant silently corrupts ~1 in 2^32 inputs". The fact that it was nearly committed to source (the architect's pseudocode used the wrong M throughout) is the strongest possible evidence that the parity test against >= 2^20 random KSUIDs is non-negotiable, AND that the magic constant must come from a programmatic source, not a hand-derivation.

Updated acceptance criteria (additions)

The original acceptance criteria stand. Add:

M1 — Magic constant must be generated, not hand-derived

The M constant in libksuid/encode_avx2.c MUST come from one of:

1. subprojects/libdivide.wrap + libdivide_u64_gen(62).magic value extracted at build time (libdivide is a single header, MIT-licensed, ~2 KB).
2. Build-time Python script (tools/derive-magic.py 62 64) emitting a generated libksuid/divisor_magic.h checked in alongside the source for reviewability + reproducibility.
3. Either path supplemented by a _Static_assert in the AVX2 TU verifying M * 62 - (1ULL << 64) <= 61 (the ceiling-of-2^64-over-62 constraint, <= d - 1).

The _Static_assert is mandatory regardless of the M source — it catches a regression where someone "improves" the constant by hand.

M2 — Differential parity test seed must be reproducible

The >= 2^20 random KSUIDs parity test in tests/test_string_batch.c extension must use a seeded LCG (matching the existing test patterns). A failing input found in CI must be reproducible locally by re-running with the same seed.

M3 — Pre-merge benchmark gate

Per Critic C10, the AVX2 kernel must beat scalar by >= 3x on a Skylake or Zen3 host before merge. If it doesn't, the pre-existing dispatch infrastructure means callers gain nothing and lose the +4 KB footprint — defaulting option('avx2_batch') to disabled is the right answer until the kernel is fast enough.

Implementation plan (updated)

The original 3-commit split stands, but commit 1 grows a sub-step:

Commit	Purpose
1a	Add subprojects/libdivide.wrap (or tools/derive-magic.py) + generated divisor_magic.h + _Static_assert of M's correctness. No SIMD code yet. Verify tests/test_compare_parity.c-style sanity check that scalar value / 62 and (value * M) >> 64 (with G-M correction) agree on >= 2^20 random value inputs.
1b	encode_avx2.c AVX2 kernel using the verified M, mulhi64 via 4× mul_epu32, lane transpose, scalar tail.
2	Differential parity test extending tests/test_string_batch.c.
3	CI footprint gate + KSUID_FORCE_SCALAR env var.

The 1a/1b split is non-trivial because it isolates the magic-constant correctness from the SIMD complexity. A reviewer who only audits commit 1a can prove M is correct without reading any AVX2 intrinsics; a reviewer of 1b can take M as a given and focus on the SIMD code.

What also gets stronger

The Critic's other findings (C1 underflow check, C2 mid-term overflow in mulhi64, C3 mul_epu32 lane positioning, C4 limb register swap, C5 aliasing, C6 fallback-build TU exclusion, C7 footprint blow-out, C8 differential test, C9 zeroupper placement, C10 compiler lowering, C11 all-zero parity, C12 register pressure) all stand. The magic-constant finding adds M1-M3 above without weakening any of them.

The persona pipeline did its job: spawning fresh architect + critic on a tight implementation prompt surfaced an error that the implementer would have copy-pasted otherwise. The failure mode (silent ~1-in-2^32 corruption) would have escaped every CI gate that doesn't run differential parity against scalar over a large random corpus, including the +5 surviving wipe-call disasm gate, the lint phase, and the build matrix.

Disposition

Issue #13 stays open. The next implementation attempt should start with commit 1a (libdivide subproject + generated magic + scalar verification) before any AVX2 intrinsics are written. The work is not blocked on external review beyond the libdivide license check (MIT, compatible with LGPL-3.0+), and the architect + critic plans in this issue's earlier comments + the hidden review threads still apply for steps 1b onward.