perf(scan): scanner micro-optimizations — shuffle structural detection + adaptive reserve + SmallVec

[membphis]

Context

Three small scanner tweaks that fit together; all in README's Deferred list since PR #3. Bundled because each individually is low-impact and they touch the same area.

B1 — shuffle-based structural set check

structural_mask_chunk (src/scan/avx2.rs) currently does 7 × _mm256_cmpeq_epi8 + 7 × _mm256_movemask_epi8 per chunk half (one per char in {}[]:,"). A single _mm256_shuffle_epi8 against a 16-byte LUT plus one cmpeq can do the same set-membership test in 2-3 ops per half.

Only affects non-fast-path chunks. For string-heavy workloads ~5% of chunks hit this path; for object-heavy workloads up to 100%.

C1 — adaptive out.reserve

out.reserve(buf.len() / 6) is calibrated for object-heavy JSON. On string-heavy multimodal payloads the actual emit rate is <1 structural per KB, so we over-reserve by 100×+. Mainly a memory hygiene concern (mmap'd pages stay lazily faulted) but reduces alloc cost on smaller buffers.

Proposal: start at max(64, buf.len() / 128) and let Vec grow naturally. Standard amortized-doubling handles the rare growth case.

C2 — SmallVec for documents < 4 KB

For tiny payloads the indices Vec heap allocation is a meaningful fraction of total parse time. Switch indices to SmallVec<[u32; N]> for some inline N (e.g. 64). Heap alloc only triggers for documents with more than N structurals.

Estimated impact

	est. speedup
B1 (string-heavy)	~2–5%
B1 (object-heavy)	~15–25%
C1	<2% across the board
C2 (small docs only)	~10–20%

Validation plan

• All existing tests + 2000-case proptest
• make bench median before/after per item separately (so each one's contribution is attributable)
• Memory: confirm C1's smaller initial reserve doesn't trigger excessive Vec regrowth on object-heavy inputs

Notes

• Validation semantics unchanged
• Implement in one PR but with separate commits per item so individual revert is possible

[membphis]

Background

The NEON scanner (src/scan/neon.rs) currently performs structural-character detection with structural_mask64, which does 7 × vceqq_u8 per 16-byte vector (one per char in {, }, [, ], :, ,, ") — 28 compare instructions per 64-byte chunk. It also calls byte_mask64 twice more to build the \ and " masks needed for escape detection and the inside-string PMULL prefix-XOR. Total detection work per non-fast-path chunk is roughly 400 NEON ops (~315 structural + ~44 \ + ~44 ").

Issue #8 B1 proposed a shuffle-based set-membership check for AVX2 (_mm256_shuffle_epi8). ARM64 has the equivalent primitive vqtbl1q_u8 (16-byte single-table lookup), and — crucially — has enough bits per tag byte (8) to fuse all three masks (structural / " / \) into a single table-lookup pass, eliminating both byte_mask64 calls. This three-in-one fusion is NEON-specific because the tag fits in one byte; the AVX2 lane layout does not enable the same trick as cleanly.

Proposal

Nibble dual-LUT classifier

Construct two static 16-byte tables. For each byte vector:

hi  = vshrq_n_u8(c, 4)                 // 0..15
lo  = vandq_u8(c, vdupq_n_u8(0x0F))    // 0..15
tag = vandq_u8(vqtbl1q_u8(HI_LUT, hi), vqtbl1q_u8(LO_LUT, lo))

Tag bit assignment:

char	bit
" 0x22	0
, 0x2C	1
: 0x3A	2
[ 0x5B	3
] 0x5D	4
{ 0x7B	5
} 0x7D	6
\ 0x5C	7

Tables (all other indices = 0):

HI_LUT[2]=0x03  HI_LUT[3]=0x04  HI_LUT[5]=0x98  HI_LUT[7]=0x60
LO_LUT[2]=0x01  LO_LUT[A]=0x04  LO_LUT[B]=0x28  LO_LUT[C]=0x82  LO_LUT[D]=0x50

After the lookup, derive the three per-char u64 masks using vtstq_u8 (single-instruction (a & b) != 0, returns 0xFF/0x00 per lane — directly feeds the existing movemask16):

quote_mask     = movemask( vtstq_u8(tag, splat(0x01)) )    // bit 0
backslash_mask = movemask( vtstq_u8(tag, splat(0x80)) )    // bit 7
struct_mask    = movemask( vtstq_u8(tag, splat(0x7F)) )    // bits 0..6

The downstream pipeline (find_escape_mask_with_carry, inside_string_neon via PMULL, emit_bits) is unchanged.

Correctness — exhaustive verification

For all 256 byte values, HI_LUT[byte>>4] & LO_LUT[byte&0x0F] ≠ 0 ⇔ byte ∈ {}[]:,"\. Worked through manually for each structural char and for adjacent non-structural neighbors that share a nibble:

byte	hi & lo	result
* 0x2A	0x03 & 0x04	0 ✓
+ 0x2B	0x03 & 0x28	0 ✓
- 0x2D	0x03 & 0x50	0 ✓
; 0x3B	0x04 & 0x28	0 ✓
< 0x3C	0x04 & 0x82	0 ✓
= 0x3D	0x04 & 0x50	0 ✓
Z 0x5A	0x98 & 0x04	0 ✓
r 0x72	0x60 & 0x01	0 ✓
z 0x7A	0x60 & 0x04	0 ✓
| 0x7C	0x60 & 0x82	0 ✓
any byte ≥ 0x80	HI_LUT[8..F] = 0	0 ✓

Cross-contamination check on shared low-nibble C: , (0x2C) yields 0x02 only (bit 1, comma) and \ (0x5C) yields 0x80 only (bit 7, backslash) — neither contaminates the other because their respective hi-rows lack the other's bit. An exhaustive 256-byte unit test will guard this in CI.

Estimated impact

Per non-fast-path 64-byte chunk:

Stage	Current	Proposed
byte_mask64('\\')	~44 ops	merged
byte_mask64('"')	~44 ops	merged
structural_mask64 (7 chars × 4 quarter-vectors)	~315 ops	—
LUT classify + 3× vtstq_u8 + 3× movemask	—	~140 ops
escape mask + PMULL + emit_bits (unchanged)	~30 ops	~30 ops
total per non-fast-path chunk	~433 ops	~170 ops

~2.5× speedup on non-fast-path chunks. End-to-end gain depends on the in-string fast-probe hit rate (existing neon.rs:103 short-circuit that skips classification when in_string && (backslash | quote) == 0):

Workload	Fast-path hit rate	Expected end-to-end
object-heavy (small_api.json, config JSON)	~0%	15–25%
mixed (medium_resp.json)	~40%	8–12%
string-heavy (multimodal base64)	~80%	3–6%

These estimates run slightly higher than the original #8 B1 figure because the fused three-in-one classification removes the two byte_mask64 calls that #8 B1 does not address.

Validation plan

• cargo test --release — NEON gate
• cargo test --release --no-default-features — scalar unchanged (control)
• cargo test --release --features test-panic — FFI panic barrier intact
• Existing tests/scanner_crosscheck.rs proptest passes (≥ 2000 cases)
• New exhaustive test nibble_lut_classifies_all_256_bytes_correctly
• make bench 3-run median, before vs after, on small_api.json and medium_resp.json — report per-fixture delta separately

Implementation notes

• Lives entirely in src/scan/neon.rs. ~150 LOC. AVX2 and scalar paths untouched.
• HI_LUT / LO_LUT as module-level static. Verify vld1q_u8 is hoisted out of the chunk loop (inspect with cargo asm if in doubt).
• vqtbl1q_u8 is 1-cycle latency / 2 IPC throughput on Apple M1/M2/M3. Older Cortex-A cores have higher latency, but instruction-count reduction alone still wins.
• The in-string fast-probe path stays as-is and continues to skip classification entirely on plain-string chunks.
• Once landed, structural_mask64 and the dual-purpose byte_mask64 become dead in neon.rs and should be removed. AVX2 keeps its own copies (separate file).

References

• Related: perf(scan): scanner micro-optimizations — shuffle structural detection + adaptive reserve + SmallVec #8 (AVX2 shuffle-structural — same idea, different ISA)
• Related: perf(scan): validate_brackets fusion in AVX2 and NEON scanners #25 (validate_brackets fusion — orthogonal; can stack on top)
• Control gate: scalar scanner — unaffected

[membphis]

Closing after evaluating all three items against the current codebase and fixtures. Summary of findings:

B1 — AVX2 shuffle structural detection

Targets structural_mask_chunk in src/scan/avx2.rs:93. The estimated 15-25% gain is for the function's internal op count on object-heavy input, but that function is one stage of a multi-stage chunk pipeline (escape mask, inside-string mask, emit). Realistic end-to-end scanner gain: ~5-10% on object-heavy chunks, and PR #12's in-string fast-probe already short-circuits the pure-string chunks where this matters less.

The NEON scanner (structural_mask64 at src/scan/neon.rs:53) has the same shape but uses a different SIMD vocabulary; B1 as scoped doesn't cover ARM64.

No fixture exercises this well. The only object-heavy fixture is small_api.json (2 KB), and PR #18 measured ±3.5% noise on it — a 5-10% scanner gain doesn't survive that noise floor.

C1 — Adaptive out.reserve

Author-estimated <2%. Primary effect is memory hygiene on string-heavy multimodal payloads (60 KB doc reserves ~10000 u32 slots for ~74 actual emits). Since malloc lazy-faults, unused capacity isn't resident.

Risk: smaller initial reserve triggers Vec regrowth memcpys on object-heavy inputs that today fit in the initial allocation.

C2 — SmallVec for small docs

The 10-20% estimate assumed eliminating an indices malloc gives that fraction back. Reality: Document is already heap-allocated via Box::leak in qjd_parse, so SmallVec just collapses 2 mallocs to 1 (not 1 to 0). On Apple M4 a small malloc is ~20-40 ns; PR #18 measured 1.6 µs per 2 KB parse → saved fraction is ~2%, not 10-20%. Plus scratch and skip are also lazy Vecs — fixing only indices is a partial win.

The N=64 inline threshold also doesn't match measured structural-char distribution: small_api.json has ~280 structurals and would spill anyway.

Decision

All three are below the noise floor on the current benchmark suite, and the codebase already has a "measured wins only" precedent from PR #14 (reverted pooling). Closing without merge.

Reopen if/when:

• A real x86 object-heavy hot workload appears (B1)
• Memory residency on string-heavy payloads becomes a profiled concern (C1)
• A representative small-payload fixture (e.g. API gateway header parse) demonstrates malloc as a hot path (C2)